CODEWITHSUNDEEP
pythonnetworkxgraph-theorycomplex-networks
Elif Sahin
Elif Sahin

Reputation: 75

Growing affect of a single node in a directed dynamic graph

I have a program that generates a directed graph with Networkx every time there is a change in the target data source, a dynamic network. I utilize these graphs by putting together the interactions and analyzing newly added or deleted edges. But I would like to also extract another information:

Say that, for t = 0, I have a node that is directed towards another node:

N1 -> N2

For t = 1, a new edge appears between N2 and N3:

N1 -> N2 -> N3

For t = 2, a new node appears between N2 and N3:

N1 -> N2 -> N4 -> N3

And so on. I do not know the correct way to give a name to N1 but maybe a seed? Because I want to get nodes like N1 that have a growing reach, like disease spread. But I only want to be able to return these nodes, not simulate a spread. If this node gets access to more and more nodes at each t time, what can I call this node and what algorithm can I use to detect it? I thought maybe a growing betweenness centrality could be measured however if there is an existent algorithm on this, I would rather rely on someone else's insight, other than my noob gut feeling.

I think Networkx doesn't support a lot of algorithms for temporal graphs but I have seen libraries that do; pathpy, DyNetx.

I will appreciate any response, thank you in advance.

Upvotes: 0

Views: 179

Answers (1)

ravenspoint
ravenspoint

Reputation: 20492

I want to get nodes like N1 that have a growing reach

I am not entirely clear on what you mean by this.

Guessing: You want a list of all nodes that existed at t, but which can reach more modes at T+1?

This seems so straightforward, I doubt that it is really what you meant.

However:

Get t graph
Get t+1 graph
LOOP N over nodes in t+1
   IF N not in t
       CONTINUE to next node
   CALCULATE Kt number of nodes reachable from N ( Dijsktra will do this ) in t
   CALCULATE Kt+1 number of nodes reachable from N  in t+1
   IF Kt+1 > Kt
       Add N to output

Another possibility occurs to me: The graph is a "forest of trees" and you want a list of all the root nodes of trees that have grown in size.

Get t graph
Get t+1 graph
LOOP N over nodes in t+1
   IF N not in t
       CONTINUE to next node
   IF N is not root ( i.e. has out-edges but no in-edges )
       CONTINUE to next node
   CALCULATE Kt number of nodes reachable from N ( Dijsktra will do this ) in t
   CALCULATE Kt+1 number of nodes reachable from N  in t+1
   IF Kt+1 > Kt
       Add N to output

Upvotes: 0

Related Questions