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

问题描述

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

I am new to networkX. I created a graph as follows:

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

边为正，但不等于1.

where the edges are positive, but do not sum up to one.

是否有内置方法可以从某个特定节点随机进行k个步骤，并返回节点列表?如果不是，最简单的方法是什么(节点可以重复)?

Is there a built-in method that makes a random walk of k steps from a certain node and return the node list? If not, what is the easiest way of doing it (nodes can repeat)?

伪代码:

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)

推荐答案

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

The easiest way of doing it is by using the transition matrix T and then using a plain Markovian random walk (in brief, the graph can be considered as a finite-state Markov chain).

让 A 和 D 分别为图 G 的邻接矩阵和度矩阵.过渡矩阵 T 定义为 T = D ^(-1) A .
设 p ^(0)为状态向量(简而言之，第 i 个分量表示在节点 i 处的概率)步行开始时，第一步(步行)可以评估为 p ^(1)= T p ^(0).
迭代地，第 k 个随机行走步可以评估为 p ^(k)= T p ^ (k-1).

Let A and D be the adjacency and degree matrices of a graph G, respectively. The transition matrix T is defined as T = D^(-1) A.
Let p^(0) be the state vector (in brief, the i-th component indicates the probability of being at node i) at the beginning of the walk, the first step (walk) can be evaluated as p^(1) = T p^(0).
Iteratively, the k-th random walk step can be evaluated as p^(k) = T p^(k-1).

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

In plain Networkx terms...

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

这篇关于从networkX中的随机游走中获取节点列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！