Graph Algorithms

这是一页“图算法专题导航”。目标不是把文章堆在一起，而是给你一条从基础遍历到分布式图计算的可执行学习路径。 目录现状（已完成专题化） 图算法系列已迁移到： content/zh/dev/algorithm/graph/ 并采用两位数字前缀（00/10/20...）做阅读顺序标识，方便： 文件系统内按顺序浏览 后续增量插入新文章（可保留编号间隔） 批量维护时快速定位阶段 推荐阅读顺序（按能力建设） 第 0 阶段：遍历基本功（先打地基） BFS / DFS 工程入门：k-hop 查询、子图抽取与路径可达性 最短路径实战：BFS、Dijkstra、A* 的工程化选型 目标： 能稳定写出迭代版图遍历； 能解释什么时候用 BFS、什么时候用 Dijkstra/A*； 习惯加 early stop、visited、预算限制。 第 1 阶段：可达性与连通结构（图查询核心） k-hop 与可达性查询：BFS 限制、Reachability 索引与 2-hop Labeling Connected Components 与 SCC：Tarjan / Kosaraju 目标： 把“能不能到达”从一次搜索升级成系统能力； 理解无向连通与有向强连通是两类不同问题； 建立“在线 BFS + 离线索引”的组合思维。 第 2 阶段：图分析指标（从可达走向洞察） 图中心性：Degree / Betweenness / Closeness PageRank / Personalized PageRank：节点重要性与增量更新 目标： 能解释“重要性”的不同定义与适用边界； 能把中心性与 PageRank 用在推荐/风控/影响力分析； 理解“指标正确”和“平台能跑”是两回事。 第 3 阶段：结构挖掘与匹配（应用层能力） 子图匹配：VF2、Ullmann 与剪枝 社区发现：Louvain 与 Label Propagation 目标： ...

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

从 Edge-cut/Vertex-cut 目标函数出发，系统讲解 METIS 多层分区思想与工程落地，重点解释分区如何影响查询延迟和跨机通信量。

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

副标题 / 摘要 社区发现不是“把图分几堆”这么简单，而是要在准确性、可解释性、速度和可维护性之间做平衡。本文按 ACERS 结构拆解两种工程最常见算法：Louvain（模块度优化） 与 Label Propagation（标签传播）。 预计阅读时长：12~16 分钟 标签：社区发现、Louvain、Label Propagation、图分区 SEO 关键词：community detection, Louvain, Label Propagation, modularity, graph partition 元描述：社区发现工程入门：Louvain 与 LPA 的原理、复杂度、选型与落地模板，覆盖群体识别、图分区、冷启动分析。 目标读者 做社交图、风控图、推荐系统图分析的工程师 想把“社区发现”从论文概念落到生产实践的开发者 需要在“图分区/冷启动”场景做群体结构建模的人 背景 / 动机 社区发现在工程里很常见： 群体识别：识别强关联账号簇、异常团伙、兴趣圈层 图分区：把高连通子图放在同一分片，减少跨分片通信 冷启动分析：新用户/新实体通过邻域社区快速归类 痛点在于： 全局最优通常不可得（NP-hard 相关目标） 数据规模大、更新快，离线算法难以频繁重跑 不同业务对“稳定性/速度/解释性”优先级不同 所以工程上最常见的两类方法是： Louvain：追求较高质量社区（模块度） Label Propagation (LPA)：追求速度与简单实现 核心概念 概念 含义 工程影响 Community 内部边密、外部边疏的节点集合 影响分区与推荐质量 Modularity(Q) 度量社区划分质量的指标 Louvain 优化目标 Label Propagation 节点迭代采用邻居主流标签 速度快、结果有随机性 Graph Partition 按社区切分存储/计算 降低跨机通信成本 Cold Start 用邻域结构给新节点快速归群 提升启动期召回 A — Algorithm（题目与算法） 题目还原（工程抽象版） 给定无向图 G=(V,E)，输出每个节点所属社区 ID，并支持以下用途： ...

副标题 / 摘要 子图匹配是图查询里的硬骨头：理论上 NP-hard，但工程里并不是“只能慢”。本文按 ACERS 模板讲清 VF2 / Ullmann 的核心思路，并把重点放在真正决定性能的地方：候选生成与剪枝策略。 预计阅读时长：15~20 分钟 标签：子图匹配、VF2、Ullmann、图数据库 SEO 关键词：Subgraph Isomorphism, VF2, Ullmann, candidate pruning, 图模式匹配 元描述：从 NP-hard 的子图同构问题出发，解释 VF2/Ullmann 机制与工程剪枝实践，覆盖图数据库常见受限模式查询。 目标读者 需要在图数据库做模式查询、规则检测、风险关系识别的工程师 已掌握 BFS/DFS/连通分量，希望进阶图匹配能力的开发者 需要在“可解释规则匹配”与“性能约束”之间做权衡的算法同学 背景 / 动机 你在图数据库里会经常遇到这种需求： 找出“一个人-两家公司-同一设备”的可疑结构 找出“作者-论文-机构”的特定模式 找出“交易链中的环形洗钱模板” 这类查询本质是 Subgraph Isomorphism（子图同构）： 给模式图 Q，在数据图 G 中找结构与约束都满足的嵌入映射。 理论上它是 NP-hard，意味着最坏情况很难避免指数爆炸。 但工程上大多数查询是受限模式（有标签、有方向、有属性、有小模式规模），因此性能核心变成： 先把候选压到很小，再做匹配搜索。 核心概念 Subgraph Isomorphism：模式图节点到数据图节点的单射映射，保边关系成立 受限模式（constrained pattern）：标签、方向、度数、属性谓词限制 候选集（candidate set）：每个模式节点可能映射到的数据节点集合 剪枝（pruning）：在搜索树早期排除不可能映射，减少回溯分支 VF2：基于状态扩展与可行性检查的深度优先匹配框架 Ullmann：基于候选矩阵与邻域一致性迭代收缩的经典方法 A — Algorithm（题目与算法） 题目还原（工程化） 给定： 数据图 G=(V_G,E_G)（通常很大） 模式图 Q=(V_Q,E_Q)（通常较小） 节点/边约束（标签、方向、属性谓词） 目标： ...

副标题 / 摘要 中心性不是论文概念，而是图系统里的“节点重要性排序器”。本文按 ACERS 结构讲透 Degree / Betweenness / Closeness，并给出一条务实结论：线上大多数系统只稳定支持 Degree + 近似 Betweenness。 预计阅读时长：12~16 分钟 标签：图论、中心性、Degree、Betweenness、Closeness SEO 关键词：图中心性, Degree Centrality, Betweenness, Closeness, 近似 Betweenness 元描述：图中心性工程指南：三大指标定义、复杂度、近似算法与落地策略，附可运行代码。 目标读者 做关系图分析、知识图谱、图数据库查询优化的工程师 需要把“节点重要性”从概念变成上线指标的开发者 想知道为何 Betweenness 工程上昂贵、如何做近似替代的同学 背景 / 动机 你在图系统里迟早会遇到这类问题： 哪些节点是“社交大 V”或“交易枢纽”？ 哪些节点是关键桥梁，断开就会让图显著分裂？ 哪些节点整体上离其他节点更近，适合作为入口/缓存热点？ 对应到中心性指标： Degree Centrality：连接数多不多（本地重要性） Betweenness Centrality：是否位于大量最短路径中（桥梁重要性） Closeness Centrality：到全图平均距离是否更短（全局接近性） 现实里最大的坑不是“不会定义”，而是“算不动”： Degree 非常便宜，几乎所有系统都能实时支持 Betweenness 精确计算很贵，通常只能离线或近似 Closeness 需要大量最短路，图一大就难在线 核心概念 1) Degree Centrality 无向图中节点 v 的度中心性常写为： C_D(v) = deg(v) / (n - 1) 含义：节点局部连接活跃度。 ...

副标题 / 摘要 连通性告诉你“图怎么分块”，而 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：按入度排序 问题： ...

围绕 k-hop 与可达性查询，讲清 BFS+hop 限制、传递闭包取舍、以及位图索引/2-hop labeling 的工程落地路径。

副标题 / 摘要 连通分量是图算法的基础地基：无向图关注“是否连在一起”，有向图关注“是否互相可达”。本文按 ACERS 模板，从朴素做法推导到 Tarjan / Kosaraju，并给出图数据库落地场景与多语言可运行实现。 预计阅读时长：14~18 分钟 标签：图论、连通分量、SCC、Tarjan SEO 关键词：Connected Components, SCC, Tarjan, Kosaraju, 图数据库 元描述：从无向连通分量到有向强连通分量，讲清 Tarjan/Kosaraju 的核心机制、复杂度和工程落地。 目标读者 需要把 BFS/DFS 用到“滚瓜烂熟”的算法学习者 在图数据库场景做子图分析、分片规划的工程师 想建立“无向 CC + 有向 SCC”统一认知框架的中级开发者 背景 / 动机 工程里你会很快遇到这三类问题： 这批节点是否天然分成多个互不相连的群？（无向图连通分量） 哪些节点形成“互相可达”的强闭环？（有向图 SCC） 如何把大图切成更可并行、更易缓存、更易分片的子图？ 如果只会 BFS/DFS 但不会“分量视角”，你会反复做可达性查询，成本高且难维护。 连通分量算法的价值是：一次全图扫描，把局部查询变成 O(1) 的分量 ID 比较。 核心概念 Connected Components（CC）：无向图中，任意两点都可达的最大节点集合 Strongly Connected Components（SCC）：有向图中，任意两点互相可达的最大节点集合 Condensation DAG（缩点图）：把每个 SCC 缩成一个点后得到的有向无环图 Tarjan 核心状态：dfn[u]（时间戳），low[u]（可回溯到的最小时间戳），栈与 in_stack Kosaraju 核心流程：原图按完成时序排序 + 反图二次 DFS A — Algorithm（题目与算法） 题目还原（工程化表述） 给定一个图 G=(V,E)： ...