PageRank算法原理与实现 - 好文

正文共835个字，8张图，预计阅读时间6分钟。

1、PageRank

1.1.简介

PageRank，又称网页排名、谷歌左侧排名，是一种由搜索引擎根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，以Google公司创办人拉里·佩奇（Larry
Page）之姓来命名。Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。

假设一个由4个网页组成的群体：A，B，C和D。如果所有页面都只链接至A，那么A的PR（PageRank）值将是B，C及D的Pagerank总和。

重新假设B链接到A和C，C只链接到A，并且D链接到全部其他的3个页面。一个页面总共只有一票。所以B给A和C每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。

1.2.公式

对于一个页面A，那么它的PR值为：

*
PR(A) 是页面A的PR值

*
PR(Ti)是页面Ti的PR值，在这里，页面Ti是指向A的所有页面中的某个页面

*
C(Ti)是页面Ti的出度，也就是Ti指向其他页面的边的个数

*
d 为阻尼系数，其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率，

该数值是根据上网者使用浏览器书签的平均频率估算而得，通常d=0.85

还有一个版本的公式：

N为页面的总数

1.3.具体实例

三个页面A、B、C

为了便于计算，我们假设每个页面的PR初始值为1，d为0.5。

*
页面A的PR值计算如下：

*
页面B的PR值计算如下：

*
页面C的PR值计算如下：

下面是迭代计算12轮之后，各个页面的PR值：

那么什么时候，迭代结束哪？一般要设置收敛条件：比如上次迭代结果与本次迭代结果小于某个误差，我们结束程序运行；比如还可以设置最大循环次数。

2、代码实现

1import numpy as np
2from scipy.sparse import csc_matrix
3
4def pageRank(G, s=.85, maxerr=.0001):
5"""
6Computes the pagerank for each of the n states
7Parameters
8----------
9G: matrix representing state transitions
10Gij is a binary value representing a transition from state i to j.
11s: probability of following a transition. 1-s probability of teleporting
12to another state.
13maxerr: if the sum of pageranks between iterations is bellow this we will
14    have converged.
15"""
16n = G.shape[0]
17# 将 G into 马尔科夫 A
18A = csc_matrix(G, dtype=np.float)
19rsums = np.array(A.sum(1))[:, 0]
20ri, ci = A.nonzero()
21A.data /= rsums[ri]
22sink = rsums == 0
23# 计算PR值，直到满足收敛条件
24ro, r = np.zeros(n), np.ones(n)
25while np.sum(np.abs(r - ro)) > maxerr:
26ro = r.copy()
27for i in range(0, n):
28    Ai = np.array(A[:, i].todense())[:, 0]
29    Di = sink / float(n)
30    Ei = np.ones(n) / float(n)
31    r[i] = ro.dot(Ai * s + Di * s + Ei * (1 - s))
32 # 归一化
33 return r / float(sum(r))
34 if __name__ == '__main__':
35 # 上面的例子
36 G = np.array([[0, 0, 1],
37          [1, 0, 0],
38          [1, 1, 0]])
39 print(pageRank(G, s=0.85))
40 # 结果：
41 [0.51203622 0.19313191 0.29483187]

3、参考资料

1、Pagerank Algorithm
Explained（https://www.slideshare.net/jdhaar/pagerank-algorithm-explaned）

2、【大创_社区划分】——PageRank算法的解析与Python实现（https://blog.csdn.net/gamer_gyt/article/details/47443877）

3、浅入浅出：PageRank算法（https://www.letiantian.me/2014-06-10-pagerank/）

4、PageRank（https://en.wikipedia.org/wiki/PageRank）

原文链接：https://www.jianshu.com/p/6af90342c3ba

查阅更为简洁方便的分类文章以及最新的课程、产品信息，请移步至全新呈现的“LeadAI学院官网”：

www.leadai.org

请关注人工智能LeadAI公众号，查看更多专业文章

大家都在看

<http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247483755&idx=2&sn=a162898c963c3475c06165b0bdc0f38b&chksm=eadba8b6ddac21a0c9f0d26dcab47abc7ef2516bf5a349aae6cd7941c479b46e4036ac511557&scene=21#wechat_redirect>

LSTM模型在问答系统中的应用
<http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484578&idx=3&sn=38654576f40c7c086fbe32d2b12c9862&chksm=eadbad7fddac246979cf49802a01c3136b1b0f79e6bfb3e9ace2172cfff4ed63be89f23b0f64&scene=21#wechat_redirect>

基于TensorFlow的神经网络解决用户流失概览问题
<http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484570&idx=4&sn=d22e41ff43460c040aae136b78f5c807&chksm=eadbad47ddac2451057b1c6975191f1044988fe9612e1fc248852fe2490052dd791c42770d96&scene=21#wechat_redirect>

最全常见算法工程师面试题目整理（一）
<http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484530&idx=1&sn=462931eb9fd0dd1ac41f2e3f987fa51c&chksm=eadbadafddac24b91389d1bcea23be2668a0efbd425150e836d1ee5ba6d182b0a2f3cf6000dc&scene=21#wechat_redirect>

最全常见算法工程师面试题目整理（二）
<http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484551&idx=3&sn=a481218ee3f5f4d766a48dca5f8c4c61&chksm=eadbad5addac244c9a9516376add6168ff1a415ba26994ede28c1613dfcc54222959c56a365f&scene=21#wechat_redirect>

TensorFlow从1到2 | 第三章深度学习革命的开端：卷积神经网络
<http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484516&idx=1&sn=40e8928353dbc29f17c8e22cd27944f4&chksm=eadbadb9ddac24af5943085537922db2f982f088f34ce20262eea314dbf5741dcefbc4a74404&scene=21#wechat_redirect>

装饰器 | Python高级编程
<http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484476&idx=1&sn=503166979eeff5c974de3e3ce0d4b12e&chksm=eadbade1ddac24f70b22b22cb81a070fdab2e4dafc02c596eb3aa5acba83a9d1051e122258e2&scene=21#wechat_redirect>

今天不如来复习下Python基础
<http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484452&idx=1&sn=c1cf5f55330a5ef89f0bce7faeda4c98&chksm=eadbadf9ddac24ef6e87ee35cc017d42a9ade6e47522b8a041a4b01227161bb17ce6102eafe0&scene=21#wechat_redirect>

热门工具换一换