子图同构与 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 邻居下的组合爆炸。
一手资料
- A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets
- NetworkX 同构算法
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。