python - 使用 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()