随着互联网的发展,网络上已有的网页数量庞大,并且每天都会有很多网页发布,如何权衡这些重要度的排名是一个很重要的问题。我们今天就来了解一下PageRank算法。

首先我们要来了解一下图的概念,请看图1。

我眼中的PageRank算法详解-LMLPHP

图1中,A/B/C/D成为节点,e1/e2/e3/e4/e5成为边。指向某个节点的边成为该节点的入度,从该节点指出的边成为该节点的出度。比如对接点B来说,e1是唯一指向B的边,我们可计算出B节点的入度为1;e3是B节点唯一指向其它节点的边,我们可以算出B节点的出度为1。对于网络上的网页之间的关系也可以用上述模型来模仿。对某一个特定网页来说,网络上存在很多网页指向它,并且这个网页内也包含很多指向其它网页的超链接。比如:有很多网页指向百度搜索、百度百科,百度页面内有指向其它网页的超链接。

我们可以用图1中的A/B/C/D表示四个网页,网页与网页之间的边我们成为链接。比如对网页D来说,网络上有一个网页(B)指向它,它包含两个超链接(e4、e5),一个链向网页A,一个链向网页C。在计算机中,图结构可以用二维矩阵来表示:如果网页A到网页B有一条边(连接),那么矩阵中第A行第B列的元素不为0(可以表示为w,w表示权重,但本文都表示为1)。那么,图1所对应的二维矩阵可以表示为图2的形式。

我眼中的PageRank算法详解-LMLPHP

我们采用行存储,例如:A到B有一条边,在矩阵中可表示为第A行第B列的元素为1。

那么,我们现在来考虑一下:什么样的网页重要?可以想象,某种程度上,1)网页入度越多,其重要度越高;2)高质量的网页指向的网页也是高质量的。PageRank就是基于这两点来进行计算的,其数学表达形式如式1所示。我眼中的PageRank算法详解-LMLPHP  式1

假设每个页面的初始重要度都为1,包含的超链接数为N,那么它向每个页面传递的重要度为1/N。按照这个思想构造超链接矩阵H,如式2所示。

我眼中的PageRank算法详解-LMLPHP  式2

由于初始重要度都为1,所以初始向量如式3所示。

我眼中的PageRank算法详解-LMLPHP

通过式1,其计算过程可表示为我眼中的PageRank算法详解-LMLPHP,直到我眼中的PageRank算法详解-LMLPHP.

在面对实际网络时,有三个问题需要考虑:1,I是否会收敛?2,I的收敛是否与初始值无关?3,满足前两条的情况下得到的数据是否可以作为重要度的排名?现在按照H计算,对这三个问题的回答都是No。需要进行随机调整(Stochasticity Adjustment)保证必须收敛,再进行素矩阵调整(Primitivity Adjustment)保证收敛的元素都为正,即:重要度都是大于0的。

05-11 22:21