python - 从networkX中的随机游走中获取节点列表

Question

我是 networkX 的新手。我创建了一个图表，如下所示:

G = nx.read_edgelist(filename,
                     nodetype=int,
                     delimiter=',',
                     data=(('weight', float),))

其中边为正，但总和不等于 1。

是否有一个内置方法可以从某个节点随机游走k步并返回节点列表？如果不是，最简单的方法是什么(节点可以重复)？

伪代码:

node = random
res = [node]
for i in range(0, k)
    read edge weights from this node
    an edge from this node has probability weight / sum_weights
    node = pick an edge from this node 
    res.append(node)

Answer 1

最简单的方法是使用转移矩阵T，然后使用普通马尔可夫随机游走(简而言之，该图可以被视为有限状态马尔可夫链)。

设A和D分别为图G的邻接矩阵和度矩阵。转移矩阵T定义为T = D^(-1) A。
令 p^(0) 为状态向量(简而言之，第 i 个分量表示位于节点 i 的概率)步行开始时，第一步(步行)可计算为 p^(1) = T p^(0)。
迭代地，第 k 个随机游走步骤可以计算为 p^(k) = T p^ (k-1)。

用简单的 Networkx 术语来说......

import networkx
import numpy
# let's generate a graph G
G = networkx.gnp_random_graph(5, 0.5)
# let networkx return the adjacency matrix A
A = networkx.adj_matrix(G)
A = A.todense()
A = numpy.array(A, dtype = numpy.float64)
# let's evaluate the degree matrix D
D = numpy.diag(numpy.sum(A, axis=0))
# ...and the transition matrix T
T = numpy.dot(numpy.linalg.inv(D),A)
# let's define the random walk length, say 10
walkLength = 10
# define the starting node, say the 0-th
p = numpy.array([1, 0, 0, 0, 0]).reshape(-1,1)
visited = list()
for k in range(walkLength):
    # evaluate the next state vector
    p = numpy.dot(T,p)
    # choose the node with higher probability as the visited node
    visited.append(numpy.argmax(p))