手把手图文并茂教你掌握 PageRank 算法

手把手图文并茂教你掌握 PageRank 算法

引用

CSDN

1.

https://blog.csdn.net/weixin_40431584/article/details/105561398

PageRank算法是Google创始人Larry Page在斯坦福大学读书期间提出的一种用于计算网页重要性的算法。该算法通过分析网页之间的链接关系，为每个网页分配一个PageRank值，从而优化搜索引擎的搜索结果。本文将详细介绍PageRank算法的基本概念、算法公式、Dead Ends和Spider Traps问题及其解决方案，以及代码实战和优缺点分析。

一、基本概念

1.1 背景介绍

PageRank算法由Google创始人Larry Page在斯坦福读大学时提出，又称PR，佩奇排名。主要针对网页进行排名，计算网站的重要性，优化搜索引擎的搜索结果。PR值是表示其重要性的因子。

1.2 算法中心思想

1. 数量假设

当在网页模型图中，一个网页接受到的其他网页指向的入链（in-links）越多，说明该网页越重要。

2. 质量假设

当一个质量高的网页指向（out-links）一个网页，说明这个被指的网页重要。

3. 出链入链

二、算法和公式

2.1 PageRank公式

• PR(Ti)：其他节点的（指向 a 节点）PR值
• L(Ti)：其他节点的（指向 a 节点）出链数
• i：循环次数

举例：

初始化的PR值为 1/N = 1/4 。

2.2 矩阵化表达：使用转移概率矩阵/马尔科夫矩阵

从A将跳转到 B 或 C 的概率为 1/2。

从D将跳转到 A 的概率为 1。（矩阵的列表示出链）

2.3 通过矩阵化表达，快速计算 PR 值

（第一次迭代得到的 PR 值）

2.4 两种方式的关系

三、Dead Ends 问题

3.1 Dead Ends 的产生

B没有任何出链（out-links）这就是 Dead Ends，Dead Ends 会导致网站权重变为 0。

举例：

使用转移概率矩阵快速计算PR值：

按照这个规律，我们在多次循环之后，会发现这个模型中所有的 PR 值都会归于 0。

3.2 解决方法：Teleport

修正M：

• a = [a0, a1,..., an]，当有一列全为时（即该节点无出链），ai = 1，其他时候 ai = 0
• e：由 1 填满的列矩阵
• n：M 矩阵的行数/列数

3.3 Dead Ends 问题修正公式

• a = [a0, a1,..., an]，当有一列全为时（即该节点无出链），ai = 1，其他时候 ai = 0
• e：由 1 填满的列矩阵
• n：M 矩阵的行数/列数
• V：PR 值的矩阵

四、Spider Traps 问题

4.1 Spider Traps 的产生

A 节点与其他节点之间无 out-links，这就是 Spider Traps，这将会导致网站权重变为向一个节点偏移。

举例：

按照这个规律，我们在多次循环之后，会发现这个模型中 A 的 PR 值都会归于 1，其他归为 0。

4.2 解决方法

修正M：

，n 为 M 的行数/列数。

• ：跟随出链（out-links）打开网页的概率，一般设为 0.8 ~0.9 之间
• ：随机跳到其他网页的概率，例如：浏览 a 的时候，有一定概率会打开 b 或 c
• ：有 1 填满的 n × n 矩阵

4.3 Spider Traps 问题修正公式

• ：跟随出链（out-links）打开网页的概率，一般设为 0.8 ~0.9 之间
• ：随机跳到其他网页的概率，例如：浏览 a 的时候，有一定概率会打开 b 或 c
• ：有 1 填满的 n × n 矩阵
• V：PR 值的矩阵

五、代码实战

# 导包
import networkx as nx
import matplotlib.pyplot as plt
import random

Graph = nx.DiGraph()
Graph.add_nodes_from(range(0, 100))
for i in range(100):   
    j = random.randint(0, 100)
    k = random.randint(0, 100)
    Graph.add_edge(k, j)

# 绘图
nx.draw(Graph, with_labels=True)
plt.show()  

# 打印全部点的 PR 值
pr = nx.pagerank(Graph, max_iter=100, alpha=0.01)
print(pr)    

# 最大的 PR 值
print(max(pr.values()))  

import operator
# 最大 PR 值的点
print(max(pr.items(), key=operator.itemgetter(1))[0])
# PR 值之和
print(sum(pr.values()))  

六、PageRank 优缺点

PageRank 优点

1. 通过网页之间的链接来决定网页的重要性，一定程度消除了人为对排名的影响。
2. 离线计算 PageRank 值，而非查找的时候计算，提升了查询的效率。

PageRank 缺点

1. 存在时间就网站，PageRank 值会越来越大，而新生的网站，PageRank 值增长慢。
2. 非查询相关的特性，查询结果会偏离搜索内容。
3. 通过“僵尸”网站或链接，人为刷 PageRank 值。