图算法

这是一页“图算法专题导航”。目标不是把文章堆在一起，而是给你一条从基础遍历到分布式图计算的可执行学习路径。 目录现状（已完成专题化） 图算法系列已迁移到： 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 目标： ...

副标题 / 摘要 子图匹配是图查询里的硬骨头：理论上 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)（通常较小） 节点/边约束（标签、方向、属性谓词） 目标： ...

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