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 –> B,D给B投了一票),说明这个网页更加重要,如图1的B。(一篇论文被很多论文引用)

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

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

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

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

1.2 如何计算

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

有多少网页链接到了pipi

这些网页的PR值是多少

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

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

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

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

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

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

PR(A)=PR(B)L(B)+PR(C)L(C)+PR(D)L(D)+⋯PR(A)=PR(B)L(B)+PR(C)L(C)+PR(D)L(D)+⋯

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

PR(pi)=∑pj∈B(pi)PR(pj)L(pj)PR(pi)=∑pj∈B(pi)PR(pj)L(pj)

但这样算存在两个问题:

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

对于没有blacklinks (inedges)的网页,即没人给她投票,其PageRank永远等于0。

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

PR(pi)=1−dN+d∑pj∈B(pi)PR(pj)L(pj)PR(pi)=1−dN+d∑pj∈B(pi)PR(pj)L(pj)

其中,

B(pi)B(pi):链接到网页pipi的集合(a set of pages link to pipi)

L(pj)L(pj):从pjpj链出去的网页数目(the number of outbound links)

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

1.3 一个简单实例

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

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−6PR′(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初始值类似,dd的取值也会影响算法效率。根据Page的论文,dd通常设为0.85。

2. PageRank计算方法

(1) 迭代方法

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

(2)代数方法

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

(3)Power Method

待续。

3. 用NetworkX求PageRank

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

pagerank(…)

pagerank_numpy(…)

pagerank_scipy(…)

详细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.

https://www.jianshu.com/p/b97ba1e1940d

电击文库:零境交错下载
「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论