Рассчитать время простоя между двумя узлами с помощью NetworkX

Question

Я хотел бы знать, могу ли я использовать NetworkX для реализации времени удара? В принципе, я хочу рассчитать время удара между любыми двумя узлами на графике. Мой график невзвешен и неориентирован. Если я правильно понял время удара, это очень похоже на идею PageRank.

Любая идея, как я могу реализовать время удара, используя метод PageRank, предоставляемый NetworkX?

Могу ли я узнать, есть ли хорошая отправная точка для работы?

Я проверил: MapReduce, Python and NetworkX , но не совсем уверен, как это работает.

Answer 1

Для решения этой проблемы вам не нужно networkX, numpy может это сделать, если вы понимаете математику за ней. Неориентированный, невзвешенный график всегда может быть представлен матрицей смежности [0,1]. nth полномочия этой матрицы представляют количество шагов от (i,j) после n шагов. Мы можем работать с марковской матрицей, которая является нормированной по строкам формой adj. матрица. Полномочия этой матрицы представляют собой случайное блуждание по графу. Если график невелик, вы можете взять полномочия матрицы и посмотреть на интересующий вас индекс (start, end). Сделайте последнее состояние поглощающим, когда прогулка попадает туда, куда он не может убежать. При каждой мощности n вы получите вероятность того, что вы рассеетесь от (i,j). Время удара может быть вычислено из этой функции (как вы знаете точный время удара для дискретных шагов).

Ниже приведен пример с простым графиком, определяемым списком краев. В конце я рисую эту функцию времени удара. В качестве точки отсчета, это график используется:

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()