数据分析之图算法: 基于Spark和Neo4j

路径查找算法和图搜索算法

｜

61

4.8

　随机游走算法

随机游走算法提供了图中某条随机路径上的一个节点集合。

1905

年，

Karl Pearson

在给

《自然》杂志的一封题为“

The Problem of the Random Walk

”的信中首次提到这个术语。虽

然这一概念可以追溯到更早，但是直到最近，随机游走算法才被应用于网络科学中。

有时也将随机游走描述为类似于一个醉汉穿行城市。他知道自己要到达的方向或终点，但

路线可能会非常迂回。

该算法从某个节点开始，带有点随机性地沿着某个关系前进——向前或向后，到达邻节

点，然后从当前节点开始执行相同操作，以此类推，直到达到设定路径长度为止。（之所

以说“带有点随机性”，是因为节点的关系数量及其邻节点的关系数量会影响经过该节点

的概率。）

4.8.1

　何时使用随机游走算法

当需要随机生成一组相互连接的节点时，可以将随机游走算法作为其他算法的一部分或数

据管道使用。

示范用例如下。

•

在

node2vec

算法和

graph2vec

算法中用于创建节点嵌入。这些节点嵌入可以用作神经网

络的输入。

•

在

Walktrap

和

Infomap

社团发现算法中使用。如果随机游走算法重复返回一个较小的节

点集合，则表明该节点集合可能具有社团结构。

•

在机器学习模型的训练过程中使用，参见

David Mack

的论文“

Review Prediction with

Neo4j and TensorFlow

”。

还可以阅读由

N. Masuda

、

M. A. Porter

和

R. Lambiotte ...