重启随机游走算法Random Walk with Restart

最近找了一下RWR算法的介绍，发现中文的blog全是互相抄的，讲的不是很清楚。最后发现medium上面有个博文写的还不错，下面抄了一点。
https://medium.com/@chaitanya_bhatia/random-walk-with-restart-and-its-applications-f53d7c98cb9

问题描述

最基本的随机游走：给定一个连接图，以及图中每个节点的转移概率，目的就是找到从某个起点开始随机走动，最终停在每个点的概率。
重启随机游走的区别就是在每次游走之后有一定概率回到起点。

先看一下公式：

的大小在0,1之间，为转移概率矩阵，是从节点到节点的概率。是起点向量，i为起点则。r是终点向量。
下面来解释这个公式

公式解释

当e为起点，下次移动的落点为的概率可以用下面这个公式得到：

为的第i行。所以如果没有重启机制的话，k次移动之后的落点为的概率是：

如果有重启机制就只能用递推公式：

如果假定随着移动次数增加，最终会收敛（事实也是如此），递推公式就可以写成最开始给出的那个公式：

解法

暴力一点就是迭代直到收敛。
或者求逆矩阵

得到

有啥用呢？

感觉基本上都是把落点概率作为一种相似度度量。
Image segmentation
图像分割中，每个像素作为图中的节点，转移概率为像素之间的相似度，以某个像素为起点游走，落点概率高的可以作为一个cluster。
类似的应用还有Community detection， Recommender Systems等。