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 Fractionnp.set_printoptions(formatter={'all': lambda x: str(Fraction(x).limit_denominator())})  # 格式化 保留分数，不至于精度丢失def PageRank(M, R0):  # 定义一个迭代函数，直至MR=R时，输出RRN = {}while (True):RN = np.dot(M, R0)if ((RN == R0).any()):  # 判断两个数组是否相等breakelse: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)  # 初始R0R_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.算法优缺点

优点：

1. 是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；
2. 有效减少在线查询时的计算量，极大降低了查询响应时间。

缺点：

1. 人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低。
2. 旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。

其他实验（我是芒果酱点一个关注吧(σ′▽‵)′▽‵)σ）

• k-Means聚类算法 HNUST【数据分析技术】(2024)-CSDN博客
• PageRank Web页面分级算法 HNUST【数据分析技术】(2024)-CSDN博客
• KNN分类算法 HNUST【数据分析技术】(2024)-CSDN博客
• Apriori关联规则算法 HNUST【数据分析技术】(2024)-CSDN博客