Relative Node Influence

[federico vaggi]

Hi everyone,

not a networkx specific question as such, but I wanted some advice.  I have a directed, weighted graph, and for every node in the graph, I wanted to calculate the node that 'influences it' the most - does anyone have a suggestion if there is a suitable index that measures that?  Alternatively, is there a way of calculating the flow across the network and measuring the edge through which the highest amount of flow is coming?

I am sorry if this is a somewhat generic question - suggestions are welcome though.

Federico

[Payne, Benjamin]

Hello,

 

It sounds like Page Rank

https://en.wikipedia.org/wiki/PageRank

would apply to this. Is that valid? If not, why not?

 

If the graph is really big, you can use the “random surfer” trick.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[Nicholas Dronen]

Hi, Benjamin:

The thing is, "influence" is ambiguous; its meaning depends on the process being modeled.  Are the nodes exchanging messages?  Are they bargaining pairwise over a limited resource?  So any of a number of a measures could apply to Frederico's question.  PageRank is a good suggestion, but without more information from Frederico, it's hard to be sure.  Frederico, can you explain what you're trying to do?

Regards,

Nick

[Federico Vaggi]

Hi,

Thanks for the replies.  The network that I am studying is a gene transcriptional network, where edges between genes represent a gene regulating the transcription of another gene.  What I am looking for is a measure of how much a given gene's expression levels are a function of another gene, as a function of both the direct and the indirect connections.

I am aware of PageRank, but as I understood it, PageRank would tell you which node would influence all other nodes the most.  I am interested in the inverse problem - given a specific node, obtaining a sorted list of all nodes that affect its expression.

Federico

[Dan Schult]

This sounds like maybe the HITS algorithm (precursor to pagerank) is what you want where each node has a "hub" score and an "authority" score. I'm guessing the authority score is what you are looking for (how much other nodes point to you). But I'm not sure if the analogy applies directly.
https://en.wikipedia.org/wiki/HITS_algorithm

> To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/FAlRBgrWNjAJ.

[Nicholas Dronen]

Hi, Frederico:

The crucial question seems to be this: what is the process whereby a gene regulates the transcription of another (possibly but not necessarily adjacent) gene?

Regards,

Nick

To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/FAlRBgrWNjAJ.

[Federico Vaggi]

It's simply indirect regulation - so:

Gene A regulates gene B, and gene B regulates gene C - so gene A influences gene C through gene B.  In the case of a linear cascade - it's all very simple.  Where it gets complicated is when you have a complex wiring of multiple genes, and a mix of positive and negative interactions, so figuring out the net effect that gene A has on gene C requires propagating its influence through all paths connecting the two genes.

Also - I am also assuming all regulations are completely linear.

[Martin]

Hi Federico,

Algorithm by Kai Wang and Califano explores this question as modulators

http://www.nature.com/nbt/journal/v27/n9/abs/nbt.1563.html

Please take a look if it helps your problem.

Best,

Martin

To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/izWA0-MR83AJ.