PageRank

系统讲解 Pregel（BSP）与 GAS（Gather-Apply-Scatter）两大图计算模型，重点落到 PageRank、Connected Components 和并行 BFS 的执行路径、收敛策略与工程取舍。

副标题 / 摘要 动态图场景里，真正的痛点不是“会不会算法”，而是“更新来了能不能顶住”。本文按 ACERS 模板讲透三件工程必修：增量最短路径、增量 PageRank、连通性维护，以及三条现实策略：局部重算、延迟更新、近似结果。 预计阅读时长：14~18 分钟 标签：动态图、增量计算、最短路径、PageRank、连通性维护 SEO 关键词：动态图, 增量最短路径, 增量 PageRank, 连通性维护, 局部重算, 延迟更新, 近似结果 元描述：动态图工程指南：在高频更新场景下如何用增量算法与工程策略控制时延和成本。 目标读者 做图数据库、关系图、推荐图在线服务的工程师 从离线图计算转向实时增量计算的开发者 想把“全量重算”改造成“可上线更新流水线”的技术负责人 背景 / 动机 静态图算法在论文里很优雅，但真实系统里图是不断变化的： 用户关系新增/删除 交易边持续流入 内容图和知识图谱持续更新 工程上 80% 的痛点就在这里： 全量重算太慢，赶不上更新速率 在线强一致代价太高，P99 失控 业务只要“可用近似”，却在做“昂贵精确” 所以核心问题变成： 不是怎么把答案算出来，而是怎么在更新流下持续算得动。 核心概念 概念 含义 工程关注点 增量最短路径 边/点更新后只修复受影响区域 影响域检测、局部重算 增量 PageRank 图更新后迭代残差局部传播 残差阈值、批量窗口 连通性维护 动态维护是否连通/分量变化 插入快、删除难 局部重算 只对受影响子图重新计算 降低 CPU/内存 延迟更新 把更新合并成批次统一处理 吞吐优先、可控延迟 近似结果 用误差边界换计算成本 SLA 与精度平衡 A — Algorithm（题目与算法） 题目还原（工程化） 给定一个持续更新的图 G_t=(V_t,E_t) 和操作流： ...

副标题 / 摘要 连通性告诉你“图怎么分块”，而 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)，计算每个节点的重要性分数： PageRank：输出全图统一重要性 PPR：给定种子分布 s，输出相对该种子的个性化重要性 输入输出 名称 类型 描述 n int 节点数量 edges List[(u,v)] 有向边 u -> v d / alpha float 阻尼系数，通常 0.85 左右 s vector PPR 的种子分布（和为 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：按入度排序 问题： ...