网页排序算法PageRank

计算PageRank,之前直接用NetworkX的API nx.pagerank求的,大概知道PageRank是怎么回事,但对算法细节并不了解。现在想进一步了解PageRank的细节。

1. 直观理解

1.1 基本思想

PageRank是以Google创始人Larry Page的姓命名的,于1999被提出来,用于测量网页的相对重要性(对网页进行排序),学术论文如下:

Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab. [PDF]

PageRank的设计受到学术论文引用启发(两人的父亲都是大学教授)。衡量一篇学术论文质量高与否,最重要的一个指标是引用次数,高引用量的论文通常意味着高质量。同理,如果一张网页被引用(以超链接的形式)多了,那么这张网页就比较重要。总结起来,PageRank的核心思想有两点(结合图1说明):

  • 越多的网页链接到一个网页(可以理解成投票,D --> BDB投了一票),说明这个网页更加重要,如图1的B。(一篇论文被很多论文引用)
  • PageRank高的网页链接到一个网页,说明这张网页也很重要。如图1,尽管C只有一张网页B链接到它,但C的重要性高于E,尽管E有一堆小罗罗给它投票。(论文被大牛引用了,说明这篇论文很有价值)(也可以从话语权角度理解,重要的人说话份量重)

Wikipedia-PageRanks-Example
Fig. 1: PageRanks for a simple network (image from Wikipedia)

整个万维网(World Wide Web)可以抽象成一张有向图,节点表示网页,连线\(p_i \rightarrow p_j\)表示网页\(p_i\)包含了超链接\(p_j\)(\(p_i\)指向了\(p_j\))。如果能对图中每个节点重要性量化,那么就能对网页进行排序了。PageRank提出之初就是为了对网页进行排序。

搜索引擎的工作原理可以简化为:输入关键词,返回与该关键词相关的网页(一个集合,相当于得到一张子图),在该子图上计算每个节点的PageRank值,PR值高的网页排在前面,低的就排在后面。

1.2 如何计算

接下来的问题是,如何计算每个节点的PageRank。想要知道一个网页\(p_i\)的PR值,需要知道:

  • 有多少网页链接到了\(p_i\)
  • 这些网页的PR值是多少

其他网页的PR值又很可能是依赖于\(p_i\),这就陷入了“先有鸡还是先有蛋”的循环,要想知道\(p_i\)的PR值,就得知道链向\(p_i\)所有网页的PR值,而要知道其他网页的PR值,又得先知道\(p_i\)的PR值。

为了打破这个循环,佩奇和布林采用了一个很巧妙的思路, 即分析一个虚拟用户在互联网上的漫游过程。 他们假定:虚拟用户一旦访问了一个网页,下一步将以相同的概率访问被该网页所链接的任何一个其它网页[3]。比如,网页\(p_i\)包含\(N\)个超链接,那么虚拟用户访问这\(N\)个页面中的任何一个的概率是\(1/N\)。那么,网页的排序就可以看成一个虚拟用户在万维网漫游了很长时间,页面被访问的概率越大,其PR值就越高,网页排名也越靠前。

先从简化的PageRank说起,以PageRank论文的例子为例,看看PageRank是怎么计算的,如下:

simplified_pagerank_calculation
Fig. 2: Simplified PageRank calculation (image from [1])

每个节点初始化或者指定一个PageRank值(如PR(A)=0.4),网页A包含两个超链接,分别指向BC(或者说A投票给BC),0.4拆分成两份,每份0.2,所以PR(B)=0.2AB同时给C投票,所以PR(C)=0.2+0.2=0.4。如此,不断地迭代,最后每个节点的值会趋于稳定(或者说收敛),这样就求得了所有节点的PR值。事实上,在这个例子中,PageRank已收俭。

每个页面将其当前的PageRank值平均分配到本页面所有出链上,一个页面将所有入链的PR值累加起来就构成了该页面新的PR值。如此迭代下去,最后得到一个稳定值。用数学公式表达,如下:

$$
PR(A)= \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}+\,\cdots
$$

更一般化地(\(B(p_i)\)表示所有链向网页\(p_i\)的集合),

$$
PR(p_i) = \sum_{p_j \in B(p_i)} \frac{PR(p_j)}{L(p_j)}
$$

但这样算存在两个问题:

  • 对于没有forward links (outedges)的网页,即只有别人给她投票,她从不给别人投票,那么她的PageRank每次迭代都会增加。
  • 对于没有blacklinks (inedges)的网页,即没人给她投票,其PageRank永远等于0。

对于第一个问题,给等式乘以一个小于1的常数\(d\)(damping factor,翻译成阻尼因数?);对于第二个问题,给等式加上一个常数。新的等式如下(\(N\)表示网页总数,或者节点数目):

$$
PR(p_i) = \frac{1-d}{N} + d \sum_{p_j \in B(p_i)} \frac{PR(p_j)}{L(p_j)}
$$

其中,

  • \(B(p_i)\):链接到网页\(p_i\)的集合(a set of pages link to \(p_i\))
  • \(L(p_j)\):从\(p_j\)链出去的网页数目(the number of outbound links)

这样,就确保所有节点的PR值加起来等于1。

1.3 一个简单实例

以一个很简单的例子(A < --> B)来看PageRank是怎么收俭的。

simple_example_pagerank_a_b
Fig. 2: An illustration of PageRank calculation.

假设他们的初始PR值为1,第一次迭代后,PR(A)和PR(B)的值为:

PR(A) = 0.15/2 + 0.85*1.0                   = 0.9249999999999999
PR(B) = 0.15/2 + 0.85*0.9249999999999999    = 0.8612499999999998

写个简单的Python脚本,得到每次迭代后的值,部分如下:

  1: A=0.925000     B=0.861250  
  2: A=0.807062     B=0.761003  
  3: A=0.721853     B=0.688575  
  4: A=0.660289     B=0.636245  
  5: A=0.615808     B=0.598437  
  6: A=0.583672     B=0.571121  
  7: A=0.560453     B=0.551385  
  8: A=0.543677     B=0.537126  
  9: A=0.531557     B=0.526823  
 10: A=0.522800     B=0.519380  
 11: A=0.516473     B=0.514002  
 12: A=0.511902     B=0.510116  
 13: A=0.508599     B=0.507309  
 14: A=0.506213     B=0.505281  
 15: A=0.504489     B=0.503815  
 16: A=0.503243     B=0.502757  
 17: A=0.502343     B=0.501992  
 18: A=0.501693     B=0.501439  
 19: A=0.501223     B=0.501040  
 20: A=0.500884     B=0.500751
 ...
 42: A=0.500001     B=0.500001  
 43: A=0.500001     B=0.500000  
 44: A=0.500000     B=0.500000  
 45: A=0.500000     B=0.500000

可见,随着迭代次数的增加,PageRank越来越接近收俭值0.5。Python源代码如下:

def pagerank_ab():
    """
    Calculate PageRank for A <--> B
    """
    pr = {'A':1.0, 'B':1.0}
    max_iter = 50

    for idx in range(1, max_iter+1):
        pr['A'] = 0.15/2 + 0.85*pr['B']
        pr['B'] = 0.15/2 + 0.85*pr['A']

        s = '{:3d}: A={:<10f}\tB={:<10f}'.format(idx, pr['A'], pr['B'])
        print(s)

1.4 迭代次数

迭代次数越多,结果越准确,但花费时间也越长。出于效率考虑,在实际应用中,当PR值落在误差允许范围内(PR值跟前一次比较,如\(PR'(A)-PR(A)<1.0e-6\),想想浮点数在计算机的存储),就可以返回结果了。Python实现的nx.pagerank`相关源代码如下:

# check convergence, l1 norm
err = sum([abs(x[n] - xlast[n]) for n in x])
if err < N*tol: # tol=1.0e-6
    return x

当然,对于超大型网络来说,有更复杂的计算方法,比如分布式。

1.5 PR初始值

不管节点PR初始值怎么设置,最后节点的PR值都一样,但收俭速度不一样。可以修改上面Python代码的PR初始值,运行代码,自行感受下。NetworkX的pagerank实现是将PR值初始化为1/N

1.6 Damping factor

跟PR初始值类似,\(d\)的取值也会影响算法效率。根据Page的论文,\(d\)通常设为0.85。

2. PageRank计算方法

(1) 迭代方法

详情见另一篇博文《迭代方法求PageRank》。

(2)代数方法

详情见另一篇博文《代数方法求PageRank》。

(3)Power Method

待续。

3. 用NetworkX求PageRank

NetworkX提供3个求PageRank的API,如下:

详细API如下:

pagerank(G, alpha=0.85, personalization=None, max_iter=100, tol=1e-06, nstart=None, weight='weight', dangling=None)

pagerank_numpy(G, alpha=0.85, personalization=None, weight='weight', dangling=None)

pagerank_scipy(G, alpha=0.85, personalization=None, max_iter=100, tol=1e-06, weight='weight', dangling=None)

本文涉及到的源代码已经分享到我的GitHub,pagerank目录下的simple_examples.py.

References:
[1] Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab. [PDF]
[2] PageRank Centrality by Massimo Franceschet
[3] 谷歌背后的数学 by 卢昌海
[4] Wikipedia: PageRank
[5] The Google Pagerank Algorithm and How It Works

专题: 网页排序算法PageRank (1/3)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

One thought on “网页排序算法PageRank