graph - 随机游走如何在图上工作？？？为什么人们使用它？

Question

我是一名在图挖掘领域工作的博士生。人们在遍历和计算图中节点之间的相似度时，已经在图中使用了随机游走的概念。谁能告诉我随机游走如何在图表上工作？特别是，当它被用来测量图中任意两个节点/顶点时......？？？等待有效且内容丰富的回复... :roll:

Answer 1

粗略地说，如果两个节点之间有很多可能的路径，那么与另一对节点之间可能路径很少的节点相比，这两个节点之间更有可能发生随机游走。从这个意义上说，两个节点之间随机游走的概率将相似关系扩展到图中未连接的节点。

有两个方面比较重要。首先，人们通常考虑一个特定的随机图，即通过将所有从节点传出的边（弧）权重归一化为总和为1而获得的图。还有一些方法使用原始边缘权重执行一些采样过程，但我发现显式构造更有用。这导致了一个马尔可夫图，它可以被认为是一个马尔可夫矩阵。其次，这种归一化方法改变了边权重的含义，因为异常值可能突然变得靠近其他节点。也就是说，如果节点 A 以相似度 10 和 40 连接到节点 B 和 C（并且没有其他节点），并且节点 Z 以相似度 1 和 4 连接到节点 B 和 C（并且没有其他节点），那么 A和 Z 将分别以 0.2 和 0.8 转移到 B 和 C 的概率结束。

这种方法的一个优点是可以自然地考虑边缘权重。更高的边缘权重将转化为更高的概率，并且长度大于 1 的步行的概率非常自然地作为马尔可夫矩阵的乘积而下降。相比之下，在没有随机游走标准化步骤的情况下计算的两个节点之间的路径总数（或其加权版本）可能会很快爆炸，并且会因边缘或三角形密度的局部变化而严重偏斜。

使用这种公式的一种算法是聚类算法 MCL。另一个应用是随机游走介数，它可以再次应用于使用聚类。标签传播方法似乎使用了类似的想法。