使用NetworkX计算两个节点之间的相遇时间

Question

我想知道是否可以使用NetworkX来实现Hitting Time？基本上，我想计算图中任意两个节点之间的Hitting Time。我的图是无权重且无向的。如果我正确地理解Hitting Time，它与PageRank的思想非常相似。

请问如何使用NetworkX提供的PageRank方法来实现Hitting Time？

能否得知一些适合入门的好的起点？

我已经查看了此链接：MapReduce, Python and NetworkX，但并不确定它的工作原理。

- DjangoRocks

Answer 1

你不需要使用 networkX 来解决问题，只要你理解背后的数学原理，numpy 就可以做到。一个无向、无权图可以用 [0,1] 邻接矩阵来表示。这个矩阵的 nth 次幂表示从 (i,j) 出发经过 n 步所需的步数。我们可以使用马尔科夫矩阵，它是邻接矩阵的行标准化形式。该矩阵的幂表示在图上进行随机游走。如果图很小，你可以对矩阵进行幂运算，并查看你感兴趣的索引 (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()    

- Hooked

---

哇，你的回答太酷了。所以我猜在执行命中时间算法之前，我需要使用Google矩阵（或将我的图形转换为矩阵）？ - DjangoRocks

networkX内置了PageRank方法：http://networkx.lanl.gov/reference/algorithms.link_analysis.html - EdChum

@EdChum，由于我不太熟悉PageRank算法，它与平均首次通过时间有什么关系（我认为OP所说的是命中时间）？我提出这个解决方案是为了帮助任何人通用地解决问题。如果您能展示使用networkx库直接解决问题的正确方法，请发布该解决方案，以便我可以看到。 - Hooked

@DjangoRocks 将您的图转换为矩阵很简单，事实上我知道networkX有一个输出到边缘的函数：http://networkx.lanl.gov/reference/generated/networkx.convert.to_edgelist.html?highlight=edge%20list#networkx.convert.to_edgelist 和一个输出到numpy矩阵的函数：http://networkx.lanl.gov/reference/generated/networkx.convert.to_numpy_matrix.html?highlight=matrix#networkx.convert.to_numpy_matrix - Hooked

实际上，这可能与思考无关，因为PageRank包括一个传输因子，计算您将逃离没有出站链接的页面的概率，这不是您在此处想要的，因为您的最终状态是吸收状态。@DjangoRocks，您为什么认为PageRank在这里相关？另外，MapReduce只是一种在网络节点间并行计算任务的技术，它取决于您的算法是否可以独立执行任务，对于您正在尝试的内容是否正确？ - EdChum

@EdChum 好的，这可能听起来很蠢，但我的教授用PageRank解释了击中时间的概念。所以我认为击中时间与PageRank有关。 - DjangoRocks