PageRank 是由 Larry Page 和 Sergey Brin 在 1998 年提出的链接分析算法， 用于衡量网页的重要性。它是 Google 搜索引擎的核心算法之一，也是现代链接分析的基石。
PageRank 的核心思想：一个网页的重要性取决于指向它的其他网页的数量和质量。 被重要网页链接的网页也会变得重要。
O(n) - 存储所有网页的排名
O(k × m) - k次迭代，边数m
通常 d = 0.85
想象一个随机上网的用户：
PageRank 就是这个用户在稳定状态下访问各个网页的概率分布。
示例：4个网页的PageRank分布
PageRank 的核心递归公式：
PR(A) = (1 - d) / N + d × Σ (PR(B) / L(B))
其中：
• PR(A) = 网页A的PageRank值
• d = 阻尼因子 (通常 0.85)
• N = 网页总数
• PR(B) = 指向A的网页B的PageRank值
• L(B) = 网页B的出链数量
将所有网页的PageRank表示为向量形式：
R = d × M × R + (1-d)/N × 1
其中：
• R = PageRank向量 [PR(1), PR(2), ..., PR(n)]ᵀ
• M = 转移矩阵，M[i][j]表示从j到i的概率
• 1 = 全1向量
这等价于求解特征值问题：
R = Mᵀ × R (当 d=1)
PageRank是转移矩阵主特征值1对应的特征向量
对于网页链接图，转移矩阵 M 的定义：
M[i][j] = 1/L(j) 如果网页j有链接指向i
M[i][j] = 0 如果网页j没有链接指向i
示例：
A→B, B→A/C, C→B/D, D→A/C 的转移矩阵
假设有4个网页：A→B→A, B→C, C→B/D, D→A/C
PR(A) = PR(B) = PR(C) = PR(D) = 0.25
PR(A) = 0.15/4 + 0.85 × (PR(B)/2 + PR(D)/2) = 0.0375 + 0.85 × (0.125 + 0.125) = 0.2375PR(B) = 0.15/4 + 0.85 × (PR(A)/1 + PR(C)/2) = 0.0375 + 0.85 × (0.25 + 0.125) = 0.35625PR(C) = 0.15/4 + 0.85 × (PR(B)/1 + PR(D)/2) = 0.0375 + 0.85 × (0.25 + 0.125) = 0.35625PR(D) = 0.15/4 + 0.85 × (PR(C)/1) = 0.0375 + 0.85 × 0.25 = 0.25
PR(A) = 0.2375, PR(B) = 0.35625, PR(C) = 0.35625, PR(D) = 0.25
class PageRank {
constructor(dampingFactor = 0.85, maxIterations = 100, minDelta = 0.0001) {
this.d = dampingFactor;
this.maxIterations = maxIterations;
this.minDelta = minDelta;
}
calculate(graph) {
const nodes = Object.keys(graph);
const n = nodes.length;
// 初始化PageRank为1/N
const ranks = {};
nodes.forEach(node => {
ranks[node] = 1.0 / n;
});
// 构建转移矩阵的稀疏表示
const outgoingLinks = {};
nodes.forEach(node => {
outgoingLinks[node] = graph[node] || [];
});
// 迭代计算
for (let iter = 0; iter < this.maxIterations; iter++) {
const newRanks = {};
let maxChange = 0;
nodes.forEach(node => {
let rankSum = 0;
// 收集所有指向当前节点的网页的贡献
nodes.forEach(source => {
const links = outgoingLinks[source];
if (links.includes(node) && links.length > 0) {
rankSum += ranks[source] / links.length;
}
});
// PageRank公式
newRanks[node] = (1 - this.d) / n + this.d * rankSum;
maxChange = Math.max(maxChange, Math.abs(newRanks[node] - ranks[node]));
});
// 更新排名
nodes.forEach(node => {
ranks[node] = newRanks[node];
});
// 检查收敛
if (maxChange < this.minDelta) {
console.log(`在第 ${iter + 1} 次迭代后收敛`);
break;
}
}
return ranks;
}
// 使用矩阵幂迭代法（更高效）
calculateWithMatrix(graph) {
const nodes = Object.keys(graph);
const n = nodes.length;
const nodeIndex = {};
nodes.forEach((node, i) => {
nodeIndex[node] = i;
});
// 构建转移矩阵
const M = Array(n).fill(null).map(() => Array(n).fill(0));
nodes.forEach(source => {
const links = graph[source];
const i = nodeIndex[source];
if (links && links.length > 0) {
links.forEach(target => {
const j = nodeIndex[target];
M[j][i] = 1.0 / links.length;
});
} else {
// 悬空节点：均匀分布到所有节点
for (let j = 0; j < n; j++) {
M[j][i] = 1.0 / n;
}
}
});
// 初始化向量
let r = Array(n).fill(1.0 / n);
const oneMinusD = (1 - this.d) / n;
// 迭代计算
for (let iter = 0; iter < this.maxIterations; iter++) {
const newR = Array(n).fill(oneMinusD);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
newR[i] += this.d * M[i][j] * r[j];
}
}
// 检查收敛
let maxChange = 0;
for (let i = 0; i < n; i++) {
maxChange = Math.max(maxChange, Math.abs(newR[i] - r[i]));
}
r = newR;
if (maxChange < this.minDelta) {
break;
}
}
// 返回节点-排名映射
const result = {};
nodes.forEach((node, i) => {
result[node] = r[i];
});
return result;
}
}
// 测试
const graph = {
'A': ['B', 'C'], // A链接到B和C
'B': ['A', 'C'], // B链接到A和C
'C': ['A', 'B', 'D'], // C链接到A、B、D
'D': ['C'] // D链接到C
};
const pagerank = new PageRank(0.85, 100, 0.0001);
const ranks = pagerank.calculate(graph);
console.log('PageRank计算结果：');
Object.entries(ranks)
.sort((a, b) => b[1] - a[1])
.forEach(([node, rank]) => {
console.log(`${node}: ${rank.toFixed(4)}`);
});
class PageRank:
def __init__(self, damping_factor=0.85, max_iterations=100, min_delta=0.0001):
self.d = damping_factor
self.max_iterations = max_iterations
self.min_delta = min_delta
def calculate(self, graph):
nodes = list(graph.keys())
n = len(nodes)
# 初始化PageRank为1/N
ranks = {node: 1.0 / n for node in nodes}
# 迭代计算
for _ in range(self.max_iterations):
new_ranks = {}
max_change = 0
for node in nodes:
rank_sum = 0
# 收集所有指向当前节点的网页的贡献
for source in nodes:
links = graph.get(source, [])
if node in links and len(links) > 0:
rank_sum += ranks[source] / len(links)
# PageRank公式
new_ranks[node] = (1 - self.d) / n + self.d * rank_sum
max_change = max(max_change, abs(new_ranks[node] - ranks[node]))
# 更新排名
ranks = new_ranks
# 检查收敛
if max_change < self.min_delta:
break
return ranks
# 使用矩阵幂迭代法（更高效）
def calculate_with_matrix(self, graph):
nodes = list(graph.keys())
n = len(nodes)
node_index = {node: i for i, node in enumerate(nodes)}
# 构建转移矩阵
M = [[0.0] * n for _ in range(n)]
for source in nodes:
links = graph.get(source, [])
i = node_index[source]
if links:
for target in links:
j = node_index[target]
M[j][i] = 1.0 / len(links)
else:
# 悬空节点：均匀分布到所有节点
for j in range(n):
M[j][i] = 1.0 / n
# 初始化向量
r = [1.0 / n] * n
one_minus_d = (1 - self.d) / n
# 迭代计算
for _ in range(self.max_iterations):
new_r = [one_minus_d] * n
for i in range(n):
for j in range(n):
new_r[i] += self.d * M[i][j] * r[j]
# 检查收敛
max_change = max(abs(new_r[i] - r[i]) for i in range(n))
r = new_r
if max_change < self.min_delta:
break
# 返回节点-排名映射
return {node: r[i] for node, i in node_index.items()}
# 测试
if __name__ == "__main__":
graph = {
'A': ['B', 'C'], # A链接到B和C
'B': ['A', 'C'], # B链接到A和C
'C': ['A', 'B', 'D'], # C链接到A、B、D
'D': ['C'] # D链接到C
}
pagerank = PageRank(0.85, 100, 0.0001)
ranks = pagerank.calculate(graph)
print('PageRank计算结果：')
for node, rank in sorted(ranks.items(), key=lambda x: x[1], reverse=True):
print(f'{node}: {rank:.4f}')
package main
import (
"fmt"
"math"
)
type PageRank struct {
d float64
maxIterations int
minDelta float64
}
func NewPageRank(dampingFactor float64, maxIterations int, minDelta float64) *PageRank {
return &PageRank{
d: dampingFactor,
maxIterations: maxIterations,
minDelta: minDelta,
}
}
func (pr *PageRank) Calculate(graph map[string][]string) map[string]float64 {
nodes := make([]string, 0, len(graph))
for node := range graph {
nodes = append(nodes, node)
}
n := float64(len(nodes))
// 初始化PageRank为1/N
ranks := make(map[string]float64)
for _, node := range nodes {
ranks[node] = 1.0 / n
}
// 迭代计算
for _ := range pr.maxIterations {
newRanks := make(map[string]float64)
maxChange := 0.0
for _, node := range nodes {
var rankSum float64
// 收集所有指向当前节点的网页的贡献
for _, source := range nodes {
links := graph[source]
for _, link := range links {
if link == node && len(links) > 0 {
rankSum += ranks[source] / float64(len(links))
break
}
}
}
// PageRank公式
newRanks[node] = (1-pr.d)/n + pr.d*rankSum
change := math.Abs(newRanks[node] - ranks[node])
if change > maxChange {
maxChange = change
}
}
// 更新排名
for node := range ranks {
ranks[node] = newRanks[node]
}
// 检查收敛
if maxChange < pr.minDelta {
break
}
}
return ranks
}
// 使用矩阵幂迭代法（更高效）
func (pr *PageRank) CalculateWithMatrix(graph map[string][]string) map[string]float64 {
nodes := make([]string, 0, len(graph))
nodeIndex := make(map[string]int)
for i, node := range graph {
nodes = append(nodes, node)
nodeIndex[node] = i
}
n := len(nodes)
// 构建转移矩阵
M := make([][]float64, n)
for i := range M {
M[i] = make([]float64, n)
}
for source, links := range graph {
i := nodeIndex[source]
if len(links) > 0 {
for _, target := range links {
j := nodeIndex[target]
M[j][i] = 1.0 / float64(len(links))
}
} else {
// 悬空节点：均匀分布到所有节点
for j := 0; j < n; j++ {
M[j][i] = 1.0 / float64(n)
}
}
}
// 初始化向量
r := make([]float64, n)
for i := range r {
r[i] = 1.0 / float64(n)
}
oneMinusD := (1 - pr.d) / float64(n)
// 迭代计算
for range pr.maxIterations {
newR := make([]float64, n)
for i := range newR {
newR[i] = oneMinusD
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
newR[i] += pr.d * M[i][j] * r[j]
}
}
// 检查收敛
maxChange := 0.0
for i := 0; i < n; i++ {
change := math.Abs(newR[i] - r[i])
if change > maxChange {
maxChange = change
}
}
r = newR
if maxChange < pr.minDelta {
break
}
}
// 返回节点-排名映射
result := make(map[string]float64)
for node, i := range nodeIndex {
result[node] = r[i]
}
return result
}
func main() {
graph := map[string][]string{
"A": {"B", "C"}, // A链接到B和C
"B": {"A", "C"}, // B链接到A和C
"C": {"A", "B", "D"}, // C链接到A、B、D
"D": {"C"}, // D链接到C
}
pagerank := NewPageRank(0.85, 100, 0.0001)
ranks := pagerank.Calculate(graph)
fmt.Println("PageRank计算结果：")
// 排序并打印
type nodeRank struct {
node string
rank float64
}
var results []nodeRank
for node, rank := range ranks {
results = append(results, nodeRank{node, rank})
}
// 简单排序
for i := 0; i < len(results)-1; i++ {
for j := i + 1; j < len(results); j++ {
if results[j].rank > results[i].rank {
results[i], results[j] = results[j], results[i]
}
}
}
for _, nr := range results {
fmt.Printf("%s: %.4f\n", nr.node, nr.rank)
}
}
当一个网页只有出链没有入链时，它的PageRank会逐渐流向这些页面， 导致其他页面的排名下降。
引入随机跳转机制 (1-d)/N，确保排名不会完全泄漏。 即使所有出链都指向悬挂节点，用户也可能随机跳转到其他页面。
一组网页只有相互之间的链接，形成一个"陷阱"， 使得外部链接无法传入，内部排名不断累积。
阻尼因子允许用户"跳出"陷阱。 对于悬挂节点（无出链），将其权重均匀分布到所有节点。
大规模图中，需要很多次迭代才能收敛。
使用稀疏矩阵存储、利用幂迭代法的性质、 或采用MapReduce等分布式框架并行计算。
| 特性 | PageRank | HITS | SALSA |
|---|---|---|---|
| 提出者 | Page & Brin | Kleinberg | Lempel & Moran |
| 迭代方式 | 全局迭代 | Authority/Hub交替 | 双向随机游走 |
| 时间复杂度 | O(m × k) | O(m × k) | O(m × k) |
| 主题敏感 | 否 | 是 | 部分 |
| 应用场景 | 网页排名 | 权威页面挖掘 | 社区发现 |
Google早期使用PageRank作为核心排序因素，结合内容相关性计算最终排名。
在Twitter、微博等平台识别重要用户/账号，基于粉丝的"质量"评估影响力。
评估学术论文的重要性，考虑引用该论文的其他论文的影响力。
基于"用户-物品"二部图，利用PageRank思想发现相似用户或推荐物品。
检测网络中的重要节点（如关键服务器、恶意网站）。
预先定义16个主题类别，针对每个主题计算PageRank， 查询时根据用户兴趣选择对应主题的排名。
在阻尼因子中引入个性化偏好，更注重用户关注的网页。
考虑链接的重要性差异，不仅按数量均分，而是根据上下文加权。
反 spam 算法，通过可信种子页面评估其他页面的可信度。
结合PageRank和社区结构，用于大规模网络分析。