PageRank 算法学习及使⽤
⽂章⽬录
在七年前读硕⼠时就听导师和其他的师兄在说⽤pagerank算法。。。。。，但是⼀直过没有搞明⽩算法的真正原理。今天，就好好学习⼀下该算法。
⼀、前⾔
这个要从搜索引擎的发展讲起。最早的搜索引擎采⽤的是 分类⽬录的⽅法，即通过⼈⼯进⾏⽹页分类并整理出⾼质量的⽹站。那时Yahoo 和国内的 hao123 就是使⽤的这种⽅法。用什么洗脸可以美白
后来⽹页越来越多，⼈⼯分类已经不现实了。搜索引擎进⼊了 ⽂本检索 的时代，即计算⽤户查询关键词与⽹页内容的相关程度来返回搜索结果。这种⽅法突破了数量的限制，但是搜索结果不是很好。因为总有某些⽹页来回地倒腾某些关键词使⾃⼰的搜索排名靠前。 于是⾕歌的两位创始⼈，当时还是美国斯坦福⼤学 (Stanford University) 研究⽣的佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对⽹页排序问题的研究。他们的借鉴了学术界评判学术论⽂重要性的通⽤⽅法， 那就是看论⽂的引⽤次数。由此想到⽹页的重要性也可以根据这种⽅法来评价。于是PageRank的核⼼思想就诞⽣了。思想⾮常简单：
1、如果⼀个⽹页被很多其他⽹页链接到的话说明这个⽹页⽐较重要，也就是PageRank值会相对较⾼
2、如果⼀个PageRank值很⾼的⽹页链接到⼀个其他的⽹页，那么被链接到的⽹页的PageRank值会相应地因此⽽提⾼
梦到亲人死了⼆、算法原理
PageRank算法总的来说就是预先给每个⽹页⼀个PR值（下⾯⽤PR值指代PageRank值），由于PR值物理意义上为⼀个⽹页被访问概率，所以⼀般是，其中为⽹页总数。另外，⼀般情况下，所有⽹页的PR值的总和为1。如果不为1的话也不是不⾏，最后算出来的不同⽹页之间PR值的⼤⼩关系仍然是正确的，只是不能直接地反映概率了。
预先给定PR值后，通过下⾯的算法不断迭代，直⾄达到平稳分布为⽌。
以投票机制的观点来看，⼀个⽹页的得票数由所有链向它的⽹页的得票数经过递归算法来得到，有到⼀个⽹页的超链接相当于对该⽹页投了⼀票。互联⽹中的⽹页可以构成⼀个有向图。
为了便于理解，考虑以下情形：1）如上左图，假设⼀个只由4个⽹页组成的集合：A、B、C和D，如果⽹页B、C、D都链向⽹页A，且⽹页B、C、D均没有链出，那么⽹页A的PR值将是⽹页B、C、D的PR值之和:
2）如上右图，继续假设在上述情境下，⽹页B有链接链向⽹页C，⽹页D有链接链向⽹页A、B、C，⼀个⽹页不能多次投票，所以⽹页B投给它链向的⽹页1/2票，⽹页D投给它链向的⽹页1/3票，计算此情境下⽹页A的PR值为：
即，在⼀个⽹页为其他⽹页投票时，根据链出总数平分该⽹页的PR值，将其作为该⽹页为其链向⽹页所投票数，即：
N 1
N PR (A )=PR (B )+PR (C )+PR (D )
PR (A )=+2PR (B )+1PR (C )3
PR (D )
PR (A )=+L (B )PR (B )+L (C )PR (C )L (D )
PR (D )
然⽽我们再考虑⼀种情况：互联⽹中⼀个⽹页只有对⾃⼰的出链，或者⼏个⽹页的出链形成⼀个循环圈。那么在不断地迭代过程中，这
⼀个或⼏个⽹页的PR值将只增不减，显然不合理。如下图中的C⽹页就是刚刚说的只有对⾃⼰的出链的⽹页：
为了解决这个问题。我们想象⼀个随机浏览⽹页的⼈，当他到达C⽹页后，显然不会傻傻地⼀直被C⽹页的⼩把戏困住。我们假定他有⼀个确定的概率会输⼊⽹址直接跳转到⼀个随机的⽹页，并且跳转到每个⽹页的概率是⼀样的。于是则此图中A的PR值可表⽰为：
3）再抽象⼀下，建⽴⼀个简化模型，对于任意的⽹页，它的PR值可以表⽰如下：参数说明：：⽹页i的PR值：⽹页j的PR值：所有链接到⽹页i的⽹页集合：⽹页j的对外链出数: 是⽹页总数
:⼀般取0.85
根据上⾯的公式，我们可以计算每个⽹页的PR值，在不断迭代趋于平稳的时候，即为最终结果。具体怎样算是趋于平稳，我们在下⾯的PR值计算⽅法部分再做解释。
三、算法证明
是否存在？
如果极限存在，那么它是否与的选取⽆关？
PageRank算法的正确性证明包括上⾯两点。为了⽅便证明，我们先将PR值的计算⽅法转换⼀下。
PR (A )=α()+2PR (B )4
(1−α)
i PR (i )=α+j ∈B i ∑L (j )PR (j )N
1−α折纸简单又漂亮
PR (i )PR (j )B i L (j )N αlim P n →∞n P 0
仍然拿刚刚的例⼦来说:
我们可以⽤⼀个矩阵来表⽰这张图的出链⼊链关系，表⽰ ⽹页没有对 ⽹页的出链：
取为所有分量都为 1 的列向量，接着定义矩阵：
则PR值的计算如下，其中为第n次迭代时各⽹页PR值组成的列向量：
于是计算PR值的过程就变成了⼀个 Markov 过程，那么PageRank算法的证明也就转为证明 Markov 过程的收敛性证明：如果这个Markov 过程收敛，那么存在，且与的选取⽆关。
若⼀个 Markov 过程收敛，那么它的状态转移矩阵A需要满⾜：
1、A为随机矩阵
2、A是不可约的
第⼀点，随机矩阵⼜叫概率矩阵或 Markov 矩阵，满⾜以下条件：显然我们的A矩阵所有元素都⼤于等于0，并且每⼀列的元素和都为1。
第⼆点，不可约矩阵：⽅针A是不可约的当且仅当与A对应的有向图是强联通的。有向图是强联通的当且仅当对每⼀对节点对，存在从到的路径。因为我们在之前设定⽤户在浏览页⾯的时候有确定概率通过输⼊⽹址的⽅式访问⼀个随机⽹页，所以矩阵同样满⾜不可约的要求。
第三点，要求A是⾮周期的。所谓周期性，体现在Markov链的周期性上。即若A是周期性的，那么这个Markov链的状态就是周期性变化的。因为是素矩阵（素矩阵指⾃⾝的某个次幂为正矩阵的矩阵），所以是⾮周期的。
⾄此，我们证明了PageRank算法的正确性。
四、PR 值计算⽅法
1、幂迭代法
⾸先给每个页⾯赋予随机的PR值，然后通过不断地迭代PR值。当满⾜下⾯的不等式后迭代结束，获得所有页⾯的PR 值：
2、特征值法
S =ij 0j i S =⎝⎜⎜⎛0
1/31/31/31/2001/20000
01/21/20⎠⎟⎟⎞e A =αS +ee N (1−α)
T
P n P =n +1AP n
lim P n →∞n P 0令a 为矩阵A 中第i ⾏第j 列的元素，则∀i =ij 1...n ,j =1...n ,a ≥ij 0，且∀i =1...n ,a =∑j =1n ij 1
G =(V ,E )u ,v ∈V u v A A A P =n +1AP n P −P <∣n +1n ∣ϵ
当上⾯提到的Markov链收敛时，必有：
3、代数法
相似的，当上⾯提到的Markov链收敛时，必有：
俏小龙
五、python 代码（利⽤pygraph 包实现）
# -*- coding: utf-8 -*-备孕吃什么叶酸
from pygraph .class .digraph import digraph
class PRIterator :
__doc__ = '''计算⼀张图中的PR 值'''
def __init__(lf , dg ):
lf .damping_factor = 0.85 # 阻尼系数，即α
lf .max_iterations = 100 # 最⼤迭代次数
lf .min_delta = 0.00001 # 确定迭代是否结束的参数，即ϵ
lf .graph = dg
def page_rank (lf ):
# 先将图中没有出链的节点改为对所有节点都有出链
for node in lf .graph .nodes ():
if len (lf .graph .neighbors (node )) == 0:
for node2 in lf .graph .nodes ():
digraph .add_edge (lf .graph , (node , node2))
nodes = lf .graph .nodes ()
化妆师资格证graph_size = len (nodes )
if graph_size == 0:
return {}
page_rank = dict .fromkeys (nodes , 1.0 / graph_size ) # 给每个节点赋予初始的PR 值
damping_value = (1.0 - lf .damping_factor ) / graph_size # 公式中的(1−α)/N 部分
flag = Fal
for i in range (lf .max_iterations ):
心脏病急救change = 0
for node in nodes :
rank = 0
for incident_page in lf .graph .incidents (node ): # 遍历所有“⼊链”的页⾯
P =AP ⇒P 为矩阵A 特征值I 对应的特征向量
（随机矩阵必有特征值I ，且其特征向量所有分量全为正或全为负）
P =AP P =(αS +ee )P
N (1−α)
T ⼜因为e 为所有分量都为1的列向量，P 的所有分量之和为1
⇒P =αSP +e
N (1−α)
⇒(ee −T αS )P =e
N (1−α)
⇒P =(ee −T αS )e
−1N (1−α)
for incident_page aph.incidents(node):# 遍历所有“⼊链”的页⾯
rank += lf.damping_factor *(page_rank[incident_page]/ighbors(incident_page)))
rank += damping_value
change +=abs(page_rank[node]- rank)# 绝对值
page_rank[node]= rank
print("This is NO.%s iteration"%(i +1))
print(page_rank)
if change < lf.min_delta:
flag =True
break
if flag:
print("finished in %s iterations!"% node)
el:
print("finished out of 100 iterations!")
法式美甲图片return page_rank
if __name__ =='__main__':
dg = digraph()
dg.add_nodes(["A","B","C","D","E"])
dg.add_edge(("A","B"))
dg.add_edge(("A","C"))
dg.add_edge(("A","D"))
dg.add_edge(("B","D"))
dg.add_edge(("C","E"))
dg.add_edge(("D","E"))
dg.add_edge(("B","E"))
dg.add_edge(("E","A"))
pr = PRIterator(dg)
page_ranks = pr.page_rank()
print("The final page rank is\n", page_ranks)
PS：⼀开始直接pip安装了pygraph，发现不⾏，将pygraph卸载（pip uninstall pygraph）；然后在github上下载下来解压，⽤python tup.py install 安装，程序可以运⾏。（希望对⼤家有帮助）
六、使⽤networkx库中的pagerank函数
当然，⾸先得先安装networkx第三⽅库： pip install networkx
