《大规模分布式计算深入解析》13.2 子图同构与 motif:模式计数的代价

判定路径 0-1-2 存在与否、计数三角形 motif 1 与星形 C(3,2)=3;同构判定组合爆炸,motif 计数按中心顶点枚举。

子图同构与 motif:模式计数的代价

子图同构判定一个模式(路径、三角形、星形)是否出现在大图中:lab 里路径 0-1-2 存在(用例 119),路径 0-3-1 不存在(用例 120)。

motif 是出现次数显著达标的子图模式,计数是它的代价中心——naive 做法枚举顶点组合,复杂度随模式大小指数上升。

motif 计数:按中心枚举

三角形 motif:图含 0-1-2 一个三角形,计数=1(用例 121)。星形按中心顶点计数:k=3 星形中心 0 连 1/2/3,计数 1(用例 122);k=2 星形从 3 个邻居里选 2 个,计数 C(3,2)=3(用例 123)。

下图就是这张测试图:中心 0 连 1/2/3,1-2 再构成三角形。

flowchart TD
    S0["0"] --- S1["1"]
    S0 --- S2["2"]
    S0 --- S3["3"]
    S1 --- S2

判定与计数的界限

存在性判定只要一个映射,计数要枚举全部映射。放大到 50 邻居,星形 k=2 是 C(50,2)=1225(用例 127),k=3 是 C(50,3)=19600(用例 129)——组合账本决定 motif 只能在很小模式上跑。

子图同构是 NP 完全,工程上用候选过滤与剪枝;索引能帮锚点定位(第 13.1 章),模式内部的映射枚举仍是本体的代价。

验证

从卷十一实验包 解包,用 index 用例 119-123 验证子图同构存在/不存在判定、三角形 motif 计数 1、星形 k=3 计数 1、k=2 计数 C(3,2)=3;用例 127/129 验证 50 邻居下的组合爆炸。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图