PageRank的基本原理以及个性化PageRank在推荐系统的应用

阅读LBSN中的位置推荐的一些文献时，遇到了一种用个性化PageRank算法来进行位置推荐的算法，虽然之前也大致了解过PageRank算法，但不细致，这次特意做一个整理总结。

PageRank算法

一、什么是PageRank

PageRank，中文一般叫佩奇排名或网页排名，是利用网页简单的超链接来计算网页的分值，从而给网页进行排名的一种算法，以Google公司创办人Larry Page之姓来命名。Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。

它的思想是模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个网页上呆了几分钟后，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳来跳去，PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。

二、简单的PageRank模型

互联网的网页可以看作是一个有向图，其中网页是结点，如果网页A有链接到网页B，则存在一条有向边A-->B，下面是一个简单的示例：

这个简单的网络中只有四个网页，如果当前在A网页，由于A有3条出链，则上网者将会各以1/3的概率跳转到B、C和D。所以如果一个网页有$k$条出链，那么该网页跳转到任意一个出链上的概率时1/k，同理D到B、C的概率各为1/2，而B到C的概率为0 。访问一个网页的概率由链接到它的所有网页的概率来决定，例如网页A由B、C两个网页链接，则：

$$P(A)=P(C)+\frac{P(B)}{2}$$

每个网页的访问概率可以用一个向量进行表示，则所有网页的跳转概率可以用户一个用转移矩阵来表示，当一个网络中有n个网页结点时，则转移矩阵M是一个$n\times n$的方阵。因此上面示例图对应的转移矩阵如下：

初始时，假设上网者在每一个网页的概率都是相等的，即$\frac{1}{n}$，于是初始的概率分布就是一个所有值都为1/n的n维列向量$V_0$，用$V_0$去右乘转移矩阵，就可以得到下一步对每个网页的访问概率$V_1$：

之后的过程就是一个不断的迭代过程，用得到的网页访问概率去右乘转移矩阵，直到达到一个收敛的状态。可以发现，这是一个马尔科夫过程，即当前的状态仅由它前一个状态来决定。

三、终止点问题

我们知道，要满足马尔科夫过程的收敛性，需要具备一个条件，即图要是强连通的。

而互联网上的网页不满足强连通的特性，因为有一些网页不指向任何网页，所以当上网者到达这类网页时，他将没法跳转到其他的网页，因此一直迭代下去，会导致所有网页的访问概率都为0；

如上所示，网页C不指向任何一个网页，其对应的转移矩阵为：

用初始的访问概率右乘转移矩阵，然后一直迭代下去，则最终所有的访问概率都变为0：

四、 陷阱问题

另外一个问题是陷阱问题，即有些网页不存在指向其他网页的链接，但存在指向自己的链接，如图所示：

我们可以发现，当上网者跑到C网页后，就像跳进了陷阱，再也不能从C中出来了，这将导致概率分布值全部转移到C网页上来，其对应的转移矩阵为：

用初始的访问概率右乘转移矩阵，然后一直迭代下去，则所有的概率都会转移到网页C：

五、 解决终止点问题和陷阱问题

上述的问题只是特殊的情况，为了更好的理解PageRank算法的原理而已。实际上Google提出的PageRank算法分为两部分，另一部分是由一定的概率跳转到一个随机的网页，这样就能避免终止点问题和陷阱问题。

其中$\alpha$一般取为0.85，现在我们来计算带陷阱问题的网络的概率分布：

重复迭代下去，得到：

六、复杂度问题

上述的网络只有四个结点，直接用矩阵乘法进行是十分快捷的。但是真实的网络中有上千万个网页结点，如果还是直接用矩阵乘法进行计算，时间复杂度就太高了。因此很多有关PageRank算法的博客都提到了Map-Reduce的计算，这里后续进行补充...

个性化PageRank算法

个性化PageRank算法的目标是要计算所有节点相对于用户u的相关度。从用户u对应的节点开始游走，每到一个节点都以1-d的概率停止游走并从u重新开始，或者以d的概率继续游走，从当前节点指向的节点中按照均匀分布随机选择一个节点往下游走。这样经过很多轮游走之后，每个顶点被访问到的概率也会收敛趋于稳定，这个时候我们就可以用概率来进行排名了。

个性化PageRank的计算可以用bookmark-coloring算法，参考文献[2]

具体的算法原理后期补充...

参考内容：

1. http://blog.jobbole.com/71431/
2. Bookmark-coloring algorithm for personalized PageRank.