Calcular tiempo de golpeo entre 2 nodos usando NetworkX

Question

Me gustaría saber si puedo usar NetworkX para implementar el tiempo de golpeo? Básicamente quiero calcular el tiempo de golpe entre 2 nodos en un gráfico. Mi gráfico no está ponderado ni dirigido. Si entiendo el tiempo de golpear correctamente, es muy similar a la idea de PageRank.

¿Alguna idea de cómo puedo implementar el tiempo de golpe utilizando el método PageRank proporcionado por NetworkX?

¿Puedo saber si hay algún buen punto de partida para trabajar?

He comprobado: MapReduce, Python and NetworkX pero no estoy seguro de cómo funciona.

Answer 1

No necesita networkX para resolver el problema, numpy puede hacerlo si comprende las matemáticas que lo respaldan. Un gráfico no ponderado no ponderado siempre se puede representar mediante una matriz de adyacencia [0,1]. nth poderes de esta matriz representan el número de pasos desde (i,j) después de n pasos. Podemos trabajar con una matriz de Markov, que es una fila normalizada del adj. matriz. Los poderes de esta matriz representan un recorrido aleatorio sobre el gráfico. Si el gráfico es pequeño, puede tomar los poderes de la matriz y mirar el índice (start, end) que le interese. Haga que el estado final sea absorbente, una vez que la caminata golpea el punto no puede escapar. En cada potencia n obtienes la probabilidad de que hayas difuminado desde (i,j). El tiempo de ejecución se puede calcular a partir de esta función (como conoce el exacto tiempo de ejecución para pasos discretos).

A continuación se muestra un ejemplo con un gráfico simple definido por la lista de bordes. Al final, trazado esta función de tiempo de golpe. Como punto de referencia, este es el gráfico utilizado:

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 += A.T 

# 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 = (A.T/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()