最近找了一下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等。
网友评论