1.理论知识
算法原理PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级。
Google 把从 A 页面到 B 页面的链接解释为A页面给B页面投票， Google 根据投票来源（甚至来源的来源， 即链接到A页面的页面）和投票目标的等级来决定新的等级。
PageRank 算法的思想简单的说，一个高等级的页面可以使其他低等级页面的等级提升。如果A页面有一个链接指向B页面，那就可以看作是A页面对B页面的一种信任或推荐。所以，如果一个页面的反向链接越多，再根据这些链接的价值加权越高，那搜索引擎就会判断这样的页面更为重要，页面等级 (PageRank)也就越高。
图4.1 PageRank加权传递图
传递计算公式：
2.算法流程图
3.关键代码
import numpy as np
from fractions import Fraction
np.set_printoptions(formatter={'all': lambda x: str(Fraction(x).limit_denominator())}) # 格式化 保留分数，不至于精度丢失
def PageRank(M, R0): # 定义一个迭代函数，直至MR=R时，输出R
RN = {}
while (True):
RN = np.dot(M, R0)
if ((RN == R0).any()): # 判断两个数组是否相等
break
else:
R0 = np.copy(RN)
return sorted(RN)
if __name__ == '__main__':
Map = [
[0, 1 / 2, 1, 0],
[1 / 3, 0, 0, 1 / 2],
[1 / 3, 0, 0, 1 / 2],
[1 / 3, 1 / 2, 0, 0]
]
# 根据有向图
M = np.array(Map)
# 转移矩阵
num = len(Map)
R0 = np.array([1 / num, 1 / num, 1 / num, 1 / num]).reshape(4, 1) # 初始R0
R_1 = PageRank(M, R0)
print('------------------------------------------------------')
print("有向图:")
print("\n".join(str(x) for x in Map))
print('------------------------------------------------------')
print("PageRank计算结果为:")
print("\n".join(str(x) for x in R_1))
print('------------------------------------------------------')
4.测试数据
表4.1 PageRank有向矩阵
A |
B |
C |
D |
|
A |
0 |
1/2 |
1 |
0 |
B |
1/3 |
0 |
0 |
1/2 |
C |
1/3 |
0 |
0 |
1/2 |
C |
1/3 |
1/2 |
0 |
0 |
5.实验结果与分析
图 4.2 PageRank计算结果
6.算法优缺点
优点：
- 是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；
- 有效减少在线查询时的计算量，极大降低了查询响应时间。
缺点：
- 人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低。
- 旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。