Python: PageRank算法浅介

python scott 238℃ 0评论

PageRank算法是互联网发展过程中的一个里程碑,斯坦福大学的两个博士生凭借这一发现构建了谷歌搜索,对整个互联网产生了巨大影响。

PageRank让链接来”投票>”

一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。

假設一個由4個頁面組成的小團體:A,B,C和D。如果所有頁面都鏈向A,那麼A的PR(PageRank)值將是B,C及D的Pagerank總和。

$$PR(A)= PR(B) + PR(C) + PR(D)$$繼續假設B也有連結到C,並且D也有連結到包括A的3個頁面。一個頁面不能投票2次。所以B給每個頁面半票。以同樣的邏輯,D投出的票只有三分之一算到了A的PageRank上。

$$PR(A)= \frac{PR(B)}{2}+ \frac{PR(C)}{1}+ \frac{PR(D)}{3}$$換句話說,根據鏈出總數平分一個頁面的PR值。

$$PR(A)= \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}$$最後,所有這些被換算為一個百分比再乘上一個係數d。由於「沒有向外連結的頁面」傳遞出去的PageRank會是0,所以,Google通過數學系統給了每個頁面一個最小值(1 – d)/N。其逻辑是对于网页A, 用户以d的概率随机选择这个网页A浏览;而以剩下的(1 – d)/N的概率从每一个网页跳转到这个网页A,具体如下:

$$PR(A)=\left( \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}+\,\cdots \right) d + \frac{1 – d}{N}$$

采用d概率来刻画两种浏览行为有着更为实际的原因:防止投票泄露现象。d称之为阻尼系数(Damping factor)。在共振时,阻尼可能限制稳定振动的振幅。d在这里也可以起到平衡两种机制的作用。

這個方程式引入了隨機瀏覽的概念,即有人上網無聊隨機打開一些頁面,點一些連結。一個頁面的PageRank值也影響了它被隨機瀏覽的機率。為了便於理解,這裡假設上網者不斷點網頁上的連結,最終到了一個沒有任何鏈出頁面的網頁,這時候上網者會隨機到另外的網頁開始瀏覽。

為了處理那些「沒有向外連結的頁面」(這些頁面就像「黑洞」會吞噬掉用戶繼續向下瀏覽的機率)帶來的問題,d=0.85(這裡的d被稱為阻尼係數(damping factor),其意義是,在任意時刻,用戶到達某頁面後並繼續向後瀏覽的機率。1-d=0.15(就是用戶停止點擊,隨機跳到新URL的機率)的算法被用到了所有頁面上,估算頁面可能被上網者放入書籤的機率。

所以,這個等式如下:

$${\rm PageRank}(p_i) = \frac{1-d}{N} + d \sum_{p_j \in M(p_i)} \frac{{\rm PageRank} (p_j)}{L(p_j)}$$

$p_1$, $p_2$, …, $p_N$是被研究的頁面,$M(p_i)$是鏈入$p_i$頁面的集合,$L(p_j)$ 是 $p_j$ 鏈出頁面的數量,而N是所有頁面的數量。

PageRank值是一個特殊矩陣中的特徵向量。這個特徵向量為

python程序模拟

首先生成一个简单地网络:

1
2
3
4
5
6
7
8
import  networkx  as  nx
G  =  nx . DiGraph ()
G . add_edge ( 'A' , 'B' )
G . add_edge ( 'A' ,  'C' )
G . add_edge ( 'B' , 'C' )
G . add_edge ( 'C' , 'A' )
pos = nx . spring_layout ( G )  #设置网络的布局
nx . draw ( G ,  pos ,  node_color  =  'orange' ,  with_labels  =  True )

我们用PR表示网页排名(page rank, pr)。

PR(A) = PR(C)

PR(B) = PR(A)/2

PR(C) = PR(A)/2 + PR(B)

对于整个例子可以得到:PR(A) = PR(C) = 2*PR(B)

设A、B、C的初始的重要性均为1,通过上面的方程组进行迭代,每次迭代后会更新A、B、C的重要性。为了方面,先把方程组转换为矩阵运算。

PR(A) = 0*PR(A) + 0*PR(B) + PR(C)

PR(B) = 0.5*PR(A) + 0*PR(B) + 0*PR(C)

PR(C) = 0.5*PR(A) + PR(B) + 0*PR(C)

1
2
3
4
5
6
7
import  numpy  as  np
#第一个例子:无漏洞
M  =  np . matrix ([[ 0 ,  0 ,  1 ],[ 0.5 ,  0 ,  0 ],[ 0.5 , 1 , 0 ]])
PR =  np . matrix ([ 1 ,  1 ,  1 ]) . transpose ()
for  i  in  range ( 1 , 101 ):
PR  =  M * PR
print  str ( i ) + ' \n ' ,  PR

但是这种简单地迭代有一个局限,就是当流量随着迭代不断流入一些节点时,这些流量不会再流出的时候,就会出现少数节点占有所有网页排名,其它节点排名为0的情况出现。一个极端的例子是:

PR(A) = PR(B) + PR(C)

1
2
3
4
5
6
import  numpy  as  np
M  =  np . matrix ([[ 0 ,  1 ,  1 ],[ 0 ,  0 ,  0 ],[ 0 , 0 , 0 ]])
PageRank =  np . matrix ([ 1 ,  1 ,  1 ]) . transpose
for  i  in  range ( 1 , 101 ):
PageRank  =  M * PageRank
print  str ( i ) + ' \n ' ,  PageRank

此时,最终收敛的结果是:PR(A) = PR(B) = PR(C) = 0

如上图中,最终所有的投票都集中在ABC三个节点上,其它节点收到的投票为0。随着迭代进行全部节点的得票都是0。因而,需要有一个平衡的调节机制,将那些只索取不奉献的节点的PageRank取一部分平均分配。

1
2
3
4
5
6
import  numpy  as  np
M  =  np . matrix ([[ 0 ,  1 ,  1 ],[ 0.5 ,  0 ,  0 ],[ 0.5 , 0 , 0 ]])
PR  =  np . matrix ([ 1 ,  1 ,  1 ]) . transpose ()
for  i  in  range ( 1 , 101 ):
PR  =  0.15 / 3  +  0.85 * M * PR
print  str ( i ) + ' \n ' ,  b

参考资料

http://www.letiantian.me/2014-06-10-pagerank/

http://www.letiantian.me/2014-12-01-text-rank/

http://zh.wikipedia.org/wiki/PageRank

http://michaelnielsen.org/blog/using-your-laptop-to-compute-pagerank-for-millions-of-webpages/

Page, Lawrence and Brin, Sergey and Motwani, Rajeev and Winograd, Terry (1999) The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab.http://ilpubs.stanford.edu:8090/422/

Date: 2015-05-18; Category:模型算法; Tags:

原文:http://www.computational-communication.com/post/mo-xing-suan-fa/2015-05-18-pagerank

转载请注明:osetc.com » Python: PageRank算法浅介

喜欢 (0)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址