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

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

6 голосов
/ 08 марта 2012

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

Есть идеи, как реализовать время удара, используя метод PageRank, предоставленный NetworkX?

Могу ли я узнать, есть ли хорошая отправная точка для работы?проверил: MapReduce, Python и NetworkX , но не совсем уверен, как это работает.

1 Ответ

14 голосов
/ 08 марта 2012

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

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

enter image description here

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

enter image description here

...