副标题 / 摘要
连通性告诉你“图怎么分块”，而 PageRank 告诉你“块里谁更重要”。这正是图数据库区别于关系数据库的关键能力之一：不仅能做连接，还能做结构化重要性传播。本文按 ACERS 结构讲清 PageRank / PPR 的算法原理与工程落地。

  • 预计阅读时长：15~20 分钟
  • 标签：PageRank、PPR、图数据库、稀疏矩阵
  • SEO 关键词：PageRank, Personalized PageRank, 稀疏矩阵, 增量更新, 图数据库
  • 元描述：从经典 PageRank 到 Personalized PageRank，覆盖迭代计算、稀疏矩阵优化与增量更新策略，并给出多语言可运行实现。

目标读者

  • 需要在图数据库做排序、推荐、影响力分析的工程师
  • 已掌握 BFS/DFS/连通分量，想进阶“图上评分”方法的开发者
  • 关注大图线上迭代性能与更新延迟的算法工程师

背景 / 动机

你前面已经把图分成了连通分量和 SCC，但工程里还有一个更难的问题：

  • 同一个分量里，谁更关键？
  • 给定一个用户或种子节点，谁与它“结构上更相关”？

这就是 PageRank / Personalized PageRank（PPR） 的职责。

这也是图数据库和关系数据库的关键差异之一：

  • 关系数据库强在 Join 与过滤（行/列视角）
  • 图数据库强在拓扑传播（边结构视角）

PageRank 本质是“在图上做概率质量传播”，它把局部连边和全局结构合成一个可排序分值。

核心概念

  • PageRank：全局重要性分数，和入链质量相关，不仅是入度多少
  • Personalized PageRank（PPR）：在随机游走中偏向某个种子集合，得到“个性化重要性”
  • 阻尼系数 d/alpha：控制继续沿边游走还是回到随机跳转/种子分布
  • 稀疏矩阵：大图邻接矩阵极稀疏，必须用 CSR/CSC 或邻接表实现乘法
  • 增量更新：图边/节点变化后，尽量局部修正而非全量重算

A — Algorithm（题目与算法）

题目还原（工程化）

给定有向图 G=(V,E)，计算每个节点的重要性分数：

  1. PageRank：输出全图统一重要性
  2. PPR：给定种子分布 s，输出相对该种子的个性化重要性

输入输出

名称类型描述
nint节点数量
edgesList[(u,v)]有向边 u -> v
d / alphafloat阻尼系数，通常 0.85 左右
svectorPPR 的种子分布（和为 1）
返回vector每个节点的 rank 分数

示例 1（PageRank）

n = 4
edges = [(0,1),(1,2),(2,0),(2,3)]

输出: rank[0..3]
特点: 0/1/2 构成循环，3 只入不出，分数受结构影响而非简单入度

示例 2（PPR）

同上图，种子节点设为 2（s[2]=1）

输出: ppr[0..3]
特点: 与节点 2 路径近、可达性强的节点得分更高

思路推导（从朴素到可用）

朴素想法 1：按入度排序

问题：

  • 只看“有多少人指向你”，不看“谁指向你”
  • 来自低质量节点的大量入边会误导结果

朴素想法 2：固定深度随机游走采样

问题：

  • 采样方差大，稳定性差
  • 很难给线上服务做可控误差承诺

关键观察

  1. 重要性应来自“高质量节点的投票”
  2. 投票是可迭代传播过程，可写成线性迭代
  3. 图很稀疏，核心成本在稀疏乘法和收敛轮数

方法选择

  • PageRank：全局基线评分
  • PPR：按用户/查询种子做个性化评分
  • 工程重点：迭代式计算 + 稀疏存储 + 增量更新

C — Concepts（核心思想）

PageRank 公式

设 PR_t(u) 是第 t 轮节点 u 的分数，Out(v) 是 v 的出度：

[ PR_{t+1}(u)=\frac{1-d}{N}+d\sum_{v\to u}\frac{PR_t(v)}{Out(v)} ]

含义：

  • 以 1-d 概率随机跳转（防止陷入闭环）
  • 以 d 概率沿边传播重要性

PPR 公式

给定种子分布 s（例如某用户历史点击节点的归一化分布）：

[ \pi_{t+1}=(1-\alpha)s+\alpha P^T\pi_t ]

含义：

  • 每轮都“回到种子”，所以结果带个性化偏置
  • 当 s 是均匀分布时，PPR 退化到接近普通 PageRank

收敛判据

常用 L1 差值：

[ |r_{t+1}-r_t|_1<\varepsilon ]

工程上 eps 常用 1e-6 ~ 1e-8，并设置 max_iter 防止极端图上长尾迭代。

实践指南 / 步骤

  1. 用邻接表或 CSR 构图，避免稠密矩阵
  2. 处理 dangling 节点（出度为 0）
  3. 迭代更新 rank 向量
  4. 每轮计算误差并判断收敛
  5. 线上大图优先 warm start（以上一版 rank 为初值）
  6. 图局部变更时做增量更新而非全量重算

可运行示例（Python）

from typing import List, Tuple


def pagerank(n: int, edges: List[Tuple[int, int]], d: float = 0.85, eps: float = 1e-8, max_iter: int = 100):
    out = [[] for _ in range(n)]
    for u, v in edges:
        out[u].append(v)

    rank = [1.0 / n] * n

    for _ in range(max_iter):
        new_rank = [(1.0 - d) / n for _ in range(n)]

        dangling_mass = 0.0
        for u in range(n):
            if len(out[u]) == 0:
                dangling_mass += rank[u]
            else:
                share = rank[u] / len(out[u])
                for v in out[u]:
                    new_rank[v] += d * share

        # 将 dangling 质量均匀回流
        add_back = d * dangling_mass / n
        for i in range(n):
            new_rank[i] += add_back

        diff = sum(abs(new_rank[i] - rank[i]) for i in range(n))
        rank = new_rank
        if diff < eps:
            break

    return rank


def personalized_pagerank(
    n: int,
    edges: List[Tuple[int, int]],
    seed: List[float],
    alpha: float = 0.85,
    eps: float = 1e-8,
    max_iter: int = 100,
):
    out = [[] for _ in range(n)]
    for u, v in edges:
        out[u].append(v)

    pi = seed[:]  # warm start with seed

    for _ in range(max_iter):
        new_pi = [(1.0 - alpha) * seed[i] for i in range(n)]

        dangling_mass = 0.0
        for u in range(n):
            if len(out[u]) == 0:
                dangling_mass += pi[u]
            else:
                share = pi[u] / len(out[u])
                for v in out[u]:
                    new_pi[v] += alpha * share

        # dangling 质量回注入种子分布（更符合 PPR 语义）
        for i in range(n):
            new_pi[i] += alpha * dangling_mass * seed[i]

        diff = sum(abs(new_pi[i] - pi[i]) for i in range(n))
        pi = new_pi
        if diff < eps:
            break

    return pi


if __name__ == "__main__":
    n = 5
    edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)]

    pr = pagerank(n, edges)
    print("PR:", [round(x, 6) for x in pr])

    seed = [0.0] * n
    seed[2] = 1.0
    ppr = personalized_pagerank(n, edges, seed)
    print("PPR(seed=2):", [round(x, 6) for x in ppr])

运行：

python3 pagerank_demo.py

E — Engineering（工程应用）

场景 1：推荐系统候选重排（Python）

背景：召回得到 1k 候选，需按图结构重要性重排。
为什么适用：PPR 能把“对当前用户更相关”的图邻域放大。

def rerank_by_score(candidates, score):
    return sorted(candidates, key=lambda x: score.get(x, 0.0), reverse=True)

print(rerank_by_score([3, 1, 2], {1: 0.12, 2: 0.35, 3: 0.2}))

场景 2：影响力分析（Go）

背景：社交/知识传播图中估计节点影响力。
为什么适用：PageRank 反映“被重要节点引用”的级联价值。

package main

import "fmt"

func topK(nodes []int, score map[int]float64, k int) []int {
	for i := 0; i < len(nodes); i++ {
		for j := i + 1; j < len(nodes); j++ {
			if score[nodes[j]] > score[nodes[i]] {
				nodes[i], nodes[j] = nodes[j], nodes[i]
			}
		}
	}
	if k > len(nodes) {
		k = len(nodes)
	}
	return nodes[:k]
}

func main() {
	nodes := []int{1, 2, 3, 4}
	score := map[int]float64{1: 0.08, 2: 0.31, 3: 0.12, 4: 0.22}
	fmt.Println(topK(nodes, score, 2))
}

场景 3：增量更新管道（JavaScript）

背景：边每天都在增删，无法每次全量重算。
为什么适用：以旧 rank 为 warm start，局部更新可显著降低时延。

function warmStartUpdate(prevRank, deltaEdgesCount) {
  const factor = Math.max(0.9, 1 - deltaEdgesCount * 0.001);
  return prevRank.map((x) => x * factor);
}

console.log(warmStartUpdate([0.2, 0.3, 0.5], 12));

R — Reflection（反思与深入）

复杂度分析

  • 单次迭代复杂度：O(E)
  • 总复杂度：O(T * E)（T 为迭代轮数）
  • 空间复杂度：O(V + E)（邻接表 + rank 向量）

替代方案与取舍

方法优点局限
入度排序计算快忽略来源质量，噪声大
PageRank全局稳定，解释性强不带个性化偏好
PPR个性化效果好每个种子都算一遍成本高
采样随机游走可并行、近似灵活方差与稳定性控制更复杂

为什么当前方案最工程可行

  • 迭代式模型简单，易做批处理与监控
  • 稀疏矩阵/邻接表天然适配大图
  • 支持 warm start 与增量更新，能满足线上延迟

解释与原理（为什么这么做）

PageRank 把“图结构”变成“概率流守恒”问题：

  • 每个节点把当前分数按出边分发
  • 目标节点接收来自上游节点的质量
  • 阻尼项保证系统可遍历、可收敛

PPR 在这个框架上加入“回到种子分布”的偏置，让排序结果和用户/查询上下文绑定。

常见问题与注意事项

  1. 为什么会收敛很慢？
    可能是 alpha 过高、图直径大或 dangling 节点多；可调低 alpha、加预处理和 warm start。

  2. dangling 节点怎么处理？
    常见做法是将其质量均匀分发，或在 PPR 中按种子分布回注入。

  3. PPR 线上是否太贵？
    需要配合缓存、批量种子、近似索引或离线预计算。

  4. 增量更新什么时候失效？
    当图结构大幅重排（大规模边重写）时，局部修正误差会积累，需要周期性全量重算兜底。

最佳实践与建议

  • 用稀疏存储（CSR/CSC 或邻接表）作为默认实现
  • 迭代监控必须同时看：残差、最大轮数命中率、top-k 稳定度
  • 线上优先 warm start，再加“变更规模阈值”决定增量或全量
  • 把 PageRank 作为粗排特征，PPR 作为个性化加权特征组合

S — Summary（总结）

核心收获

  • 连通分量回答“怎么分块”，PageRank/PPR 回答“块里谁更重要”。
  • PageRank 是全局结构评分，PPR 是面向种子的个性化评分。
  • 工程落地三件事必须同时做：迭代式计算、稀疏矩阵实现、增量更新机制。
  • 图数据库在这类拓扑传播任务上天然优于纯关系模型的 Join 视角。
  • 想要线上可用，必须把“收敛误差 + 计算成本 + 更新频率”一起纳入治理。

推荐延伸阅读

  • Brin, Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine
  • Andersen et al. Local graph partitioning using PageRank vectors
  • Neo4j GDS 文档：PageRank / Personalized PageRank

小结 / 结论

PageRank/PPR 不是“老算法”，而是图计算系统里的基础能力层。
当你把它和连通分量、SCC、分片策略结合后，才真正形成图数据库的工程闭环。

元信息

  • 阅读时长：15~20 分钟
  • 标签：PageRank、PPR、图数据库、推荐系统、增量更新
  • SEO 关键词：PageRank, Personalized PageRank, 稀疏矩阵, 增量更新
  • 元描述：从 PR 到 PPR，系统讲解图上重要性传播与工程优化（迭代、稀疏、增量）。

行动号召（CTA）

建议你下一步直接做两件事：

  1. 在你的业务图上跑一次全量 PageRank，记录 top-k 稳定性。
  2. 做一次“日更边集”的增量更新实验，比较全量与增量的误差和时延。

如果你愿意，我可以继续写“6️⃣ HITS / SALSA 与 PageRank 的工程对比”。

多语言参考实现（Python / C / C++ / Go / Rust / JS）

def pagerank(n, edges, d=0.85, iters=50):
    out = [[] for _ in range(n)]
    for u, v in edges:
        out[u].append(v)
    r = [1.0 / n] * n
    for _ in range(iters):
        nr = [(1 - d) / n] * n
        dangling = 0.0
        for u in range(n):
            if not out[u]:
                dangling += r[u]
                continue
            share = r[u] / len(out[u])
            for v in out[u]:
                nr[v] += d * share
        add = d * dangling / n
        for i in range(n):
            nr[i] += add
        r = nr
    return r

#include <stdio.h>

void pagerank_demo() {
    // 最小示意：真实工程应使用 CSR/CSC 存储
    double rank[3] = {1.0/3, 1.0/3, 1.0/3};
    for (int t = 0; t < 5; ++t) {
        // 省略细节，演示迭代框架
        printf("iter %d: %.6f %.6f %.6f\n", t, rank[0], rank[1], rank[2]);
    }
}

int main() {
    pagerank_demo();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

vector<double> pagerank(int n, const vector<pair<int,int>>& edges, double d=0.85, int iters=50) {
    vector<vector<int>> out(n);
    for (auto [u,v] : edges) out[u].push_back(v);
    vector<double> r(n, 1.0 / n);

    for (int t = 0; t < iters; ++t) {
        vector<double> nr(n, (1 - d) / n);
        double dangling = 0.0;
        for (int u = 0; u < n; ++u) {
            if (out[u].empty()) {
                dangling += r[u];
            } else {
                double share = r[u] / out[u].size();
                for (int v : out[u]) nr[v] += d * share;
            }
        }
        double add = d * dangling / n;
        for (int i = 0; i < n; ++i) nr[i] += add;
        r.swap(nr);
    }
    return r;
}

int main() {
    vector<pair<int,int>> edges{{0,1},{1,2},{2,0},{2,3}};
    auto r = pagerank(4, edges);
    for (double x : r) cout << fixed << setprecision(6) << x << " ";
    cout << "\n";
}

package main

import "fmt"

func pagerank(n int, edges [][2]int, d float64, iters int) []float64 {
	out := make([][]int, n)
	for _, e := range edges {
		u, v := e[0], e[1]
		out[u] = append(out[u], v)
	}
	r := make([]float64, n)
	for i := range r {
		r[i] = 1.0 / float64(n)
	}
	for t := 0; t < iters; t++ {
		nr := make([]float64, n)
		for i := range nr {
			nr[i] = (1.0 - d) / float64(n)
		}
		dangling := 0.0
		for u := 0; u < n; u++ {
			if len(out[u]) == 0 {
				dangling += r[u]
				continue
			}
			share := r[u] / float64(len(out[u]))
			for _, v := range out[u] {
				nr[v] += d * share
			}
		}
		add := d * dangling / float64(n)
		for i := range nr {
			nr[i] += add
		}
		r = nr
	}
	return r
}

func main() {
	edges := [][2]int{{0, 1}, {1, 2}, {2, 0}, {2, 3}}
	fmt.Println(pagerank(4, edges, 0.85, 50))
}

fn pagerank(n: usize, edges: &[(usize, usize)], d: f64, iters: usize) -> Vec<f64> {
    let mut out = vec![Vec::<usize>::new(); n];
    for &(u, v) in edges {
        out[u].push(v);
    }

    let mut r = vec![1.0 / n as f64; n];
    for _ in 0..iters {
        let mut nr = vec![(1.0 - d) / n as f64; n];
        let mut dangling = 0.0;

        for u in 0..n {
            if out[u].is_empty() {
                dangling += r[u];
            } else {
                let share = r[u] / out[u].len() as f64;
                for &v in &out[u] {
                    nr[v] += d * share;
                }
            }
        }

        let add = d * dangling / n as f64;
        for x in &mut nr {
            *x += add;
        }
        r = nr;
    }
    r
}

fn main() {
    let edges = vec![(0, 1), (1, 2), (2, 0), (2, 3)];
    let r = pagerank(4, &edges, 0.85, 50);
    println!("{:?}", r);
}

function pagerank(n, edges, d = 0.85, iters = 50) {
  const out = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) out[u].push(v);

  let rank = Array(n).fill(1 / n);

  for (let t = 0; t < iters; t += 1) {
    const next = Array(n).fill((1 - d) / n);
    let dangling = 0;

    for (let u = 0; u < n; u += 1) {
      if (out[u].length === 0) {
        dangling += rank[u];
      } else {
        const share = rank[u] / out[u].length;
        for (const v of out[u]) next[v] += d * share;
      }
    }

    const add = (d * dangling) / n;
    for (let i = 0; i < n; i += 1) next[i] += add;
    rank = next;
  }

  return rank;
}

console.log(pagerank(4, [[0, 1], [1, 2], [2, 0], [2, 3]]));