Calculate downtime between two nodes using NetworkX

Question

I would like to know if I can use NetworkX to implement hit time? Basically, I want to calculate the impact time between any two nodes on the graph. My schedule is unweighted and disoriented. If I understood the time of the strike correctly, this is very similar to the idea of ​​PageRank.

Any idea how I can implement beat time using the PageRank method provided by NetworkX?

Can I find out if there is a good starting point for work?

I checked: MapReduce, Python, and NetworkX but not quite sure how this works.

Answer 1

You do not need networkX to solve the problem, numpy can do this if you understand the math behind it. An undirected, unweighted graph can always be represented by an adjacency matrix [0,1]. nth degrees of this matrix represent the number of steps from (i,j) after steps n . We can work with a Markov matrix, which is the row normalized form adj. matrix. The authority of this matrix is ​​a random walk on the graph. If the graph is small, you can take the strength of the matrix and see the index you are interested in (start, end) . Make the last state absorbing as soon as the walk gets to where it cannot escape. For each power n you get the probability that you will dissipate from (i,j) . Impact time can be calculated from this function (as you know the exact impact time for discrete steps).

Below is an example with a simple graph defined by a list of edges. In the end, I draw this hit time function. As a control point, this graph is used:

 from numpy import * hit_idx = (0,4) # Define a graph by edge list edges = [[0,1],[1,2],[2,3],[2,4]] # Create adj. matrix A = zeros((5,5)) A[zip(*edges)] = 1 # Undirected condition A += AT # Make the final state an absorbing condition A[hit_idx[1],:] = 0 A[hit_idx[1],hit_idx[1]] = 1 # Make a proper Markov matrix by row normalizing A = (AT/A.sum(axis=1)).T B = A.copy() Z = [] for n in xrange(100): Z.append( B[hit_idx] ) B = dot(B,A) from pylab import * plot(Z) xlabel("steps") ylabel("hit probability") show()