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

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

PageRank算法

一、什么是PageRank

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

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

二、简单的PageRank模型

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

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

这个简单的网络中只有四个网页,如果当前在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$的方阵。因此上面示例图对应的转移矩阵如下:

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

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

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

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

三、终止点问题

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

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

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

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

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

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

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

四、 陷阱问题

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

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

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

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

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

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

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

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

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

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

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

重复迭代下去,得到:

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

六、复杂度问题

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


个性化PageRank算法

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

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

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

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


参考内容:

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

相关推荐