使用NetworkX计算2个节点之间的命中时间

Question

我想知道我是否可以NetworkX用来实现击球时间？基本上我想计算图表中任意2个节点之间的点击时间.我的图表没有加权和无向.如果我理解正确的时间,它与PageRank的想法非常相似.

知道如何使用NetworkX提供的PageRank方法实现点击时间？

我可以知道是否有任何良好的起点可以合作？

我已经检查过:MapReduce,Python和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()