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

- Bob

Answer 1

免责声明：我是下面介绍的这个包的作者。

很惊讶竟然没有一个库能够高效地执行此功能，因此我构建并开源了一个Python包。它使用C++编写，并使用并行化进行最大限度的加速。在几秒钟内，它可以生成数百万条随机游走路径。

import walker

walks = walker.random_walks(G, n_walks=15, walk_len=10)

这将为您的图G中的每个节点创建长度为10的15个随机游走。

如果您只想从单个节点开始创建一个随机游走：

node = 42
walks = walker.random_walks(G, n_walks=1, walk_len=10, start_node=[node])

通过指定 p 和 q 参数，您还可以创建 node2vec-biased 随机游走。

安装需要 pybind11 以允许 C++ 绑定：

pip install pybind11
pip install graph-walker

- Kerighan

---

这真的非常快！我在一个有2万个节点和10万个边的图上运行它，返回了1百万个长度为20的步行，不到一秒钟。干得好！ - fratajcz

Answer 2

最简单的方法是使用转移矩阵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))

- AlessioX

---

你可能不想反转那个对角矩阵或进行完整的矩阵乘法。考虑使用类似dinv = 1./numpy.sum(A, axis=0)的方法。然后循环遍历每一行并应用dinv的每个元素。 - Bill

虽然看起来很美，但我认为从邻接矩阵 $A$ 中获取转移矩阵 $T$ 只是将每行除以其总和的简单问题。这基本上意味着取图的每条边的可能性相等。实际上，我们可以引入任何加权方案，并在邻接矩阵中除以边权重的总和。 - lericson

@lericson 这确实是真的。你的第一个观察是正确的，因为我示例中的邻接矩阵是二进制的（即，如果节点_i和_j之间有一条边，则在位置_i，j上有一个1）。然而，众所周知，邻接矩阵可以在位置_i，j上评分，以链接节点_i和_j的边的权重。因此，度矩阵D将不包含“连接到给定节点的节点数”，而是涉及给定节点的边的权重之和。因此，你的结论：在构建T时，需要除以权重之和。 - AlessioX

Answer 3

最有效的方法是使用CSR稀疏格式的图形转移矩阵，当然，有一个很棒的软件包可以做到这一点：csrgraph（pip install csrgraph）。以下是操作步骤：

import csrgraph as cg
import numpy as np

G = cg.csrgraph(G, threads=12) 
node_names = G.names
walks = G.random_walks(walklen=10, # length of the walks
                epochs=100, # how many times to start a walk from each node
                start_nodes=None, # the starting node. It is either a list (e.g., [2,3]) or None. If None it does it on all nodes and returns epochs*G.number_of_nodes() walks
                return_weight=1.,
                neighbor_weight=1.)

结果是一个大小为 (epochs*number_of_nodes, walklen) 的数组。可以在 此处 找到有关该函数及其参数的更多信息。

在具有 2,130 个节点和 36,560 条边的图上，使用上述代码片段生成长度为 20 的 213,000 条路径仅需 0.5 秒。

>>> array([[   0,    4, 1678, ...,   48,  728,   30],
       [   1,   57,  102, ...,  947,  456,  240],
       [   2,  156,  177, ...,  175, 1363,  539],
       ...,
       [2127, 1655, 1656, ..., 1655, 1656, 2127],
       [2128,    4, 1432, ...,  111,   32,  162],
       [2129,    4,  521, ..., 1280,  180,  608]], dtype=uint32)

walks.shape
>>> (213000, 20)

节点名称可以使用下面的代码段或其他类似的方法映射回其原始格式：

walks = np.vectorize(lambda x: node_names[x])(walks) # map to original node names

注意：此包不仅限于随机游走，您可能需要查看它们在GitHub上的存储库这里

- pegah

Answer 4

为了进一步解释@AlessioX的答案：

设A为邻接矩阵，即当顶点i和j之间存在边时，A_ij为1.0；当不存在边时，A_ij为0.0。（但请注意，下面的方法即使在加权邻接矩阵中也适用。）

>>> A
array([[1, 0, 1],
       [1, 1, 1],
       [0, 0, 1]])

然后，我们可以通过将每一行除以其总和来找到转移矩阵T，如下所示：

>>> A / A.sum(axis=1, keepdims=True)
array([[0.5       , 0.        , 0.5       ],
       [0.33333333, 0.33333333, 0.33333333],
       [0.        , 0.        , 1.        ]])

- lericson

Answer 5

你可以使用邻接矩阵。然后，您可以将其归一化，使得行的总和等于1，并且每行是节点跳转到另一个节点的概率分布。 如果行走者跳转到随机节点，则还可以具有跳转概率。

M = nx.adjacency_matrix(g) #obtain the adj. matrix for the graph
#normalise the adjacency matrix
for i in range(M.shape[1]):
    if (np.sum(M[i]) > 0):
    M[i] = M[i]/np.sum(M[i])
p = generate a random number between 0 and 1
if p < restart_prob:
    #do restart
else:
    #choose next node

然后您可以随机选择一个节点，然后以概率1-restart_prob选择下一个节点，或以概率restart_prob重新启动行走器。

为了更好地理解算法，您可以查看PageRank的工作原理。

- Ash