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

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

可以用rand()产生随机数，然后模4，结果为0，1，2，3四种情况，分态凯别代表向前，后，左，右走一步。每次都是随机的，所以总体圆闭迟也是随机行走。

代码如下：

#include<iostream>

#include<ctime>

using namespace std

int main()

{

int x=0,y=0,i

int step

cout<<"初始位置为(0,0)"<<endl

srand(time(NULL))

for(i=1i<100i++)

{

step=rand()%4

if(step==0)

{

x++

cout<<"第"<<i<<"步向前走"<<endl

cout<<"当前位置为("<<x<<","<<y<<")"<<endl

}

else if(step==1)

{

x--

cout<<"第"<<i<<"步向后走"<<endl

cout<<"当前位置为("<<x<<","<<y<<")"<<endl

}

else if(step==2)

{

y--

cout<<"第"<<i<<"步向左走"<<endl

cout<<"当前位置为("<<x<<","<<y<<")"<<橘李endl

}

else if(step==3)

{

y++

cout<<"第"<<i<<"步向右走"<<endl

cout<<"当前位置为("<<x<<","<<y<<")"<<endl

}

}

}

这个早姿…芹茄…设置一个1到4的随机数（假定游走的空间是二维的），如果随机数结果为1，就向上走一个单位，如果为2，向左走陆首绝一个单位，如果为3，向下走一个单位，如果为4，向右走一个单位，每走一个单位，重复一遍上面的过程。

---