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

PageRank让链接来投票

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

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

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

換句話說,根據鏈出總數平分一個頁面的PR值。

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

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

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

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

所以,這個等式如下:

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

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

Image Title

python程序模拟

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

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) = 0PR(A) + 0PR(B) + PR(C) PR(B) = 0.5PR(A) + 0PR(B) + 0PR(C) PR(C) = 0.5PR(A) + PR(B) + 0*PR(C)

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)

import numpy as np
# 第二个例子:引入漏洞
M = np.matrix([[0, 1, 1],[0, 0, 0],[0,0,0]])  
PR= np.matrix([1, 1, 1]).transpose()

for i in range(1,101):
  PR = M*PR print str(i)+'\n', PR

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

Image Title

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

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):
  PR = 0.15/3 + 0.85*M*PR
  print str(i)+'\n', PR

# 第一个例子采用pagerank算法重新计算的结果

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 = 0.15/3 + 0.85*M*PR
  print str(i)+'\n', PR

可以将以上计算的结果和networkx的pagerank函数得到的结果做比较:

nx.pagerank(G)