NetworkX边诱导子图同构如何忽略大图额外边完成匹配

解决方案 #

你遇到的匹配失败问题是因为GraphMatcher.subgraph_isomorphisms_iter()默认采用诱导子图同构规则：要求大图中匹配节点导出的子图，和子图结构完全一致，多余的边会直接导致匹配失败。
你需要的非诱导子图匹配规则（仅要求子图中定义的所有边在大图映射节点中都存在，忽略大图匹配节点间的额外边），可以直接使用NetworkX内置的subgraph_monomorphisms_iter()方法实现，该方法的匹配规则完全符合你的需求。

修改后完整代码 #

import networkx as nx
from networkx.algorithms import isomorphism
import matplotlib.pyplot as plt

subg = nx.Graph()
subg.add_nodes_from([0]+[i+1 for i in range(6)])
subg.add_edges_from([(0, i) for i in range(1,7)])

bigg = nx.Graph()
bigg.add_nodes_from([0]+[i+1 for i in range(6)])
bigg.add_edges_from([(0, i) for i in range(1,7)]+[(i,i+1) for i in range(1,6)]+[(1,6)])

nx.draw(subg, with_labels=True)
plt.show()
nx.draw(bigg, with_labels=True)
plt.show()

matcher = isomorphism.GraphMatcher(bigg, subg)
# 替换为子图单态射匹配，符合非诱导子图的匹配规则
print([x for x in matcher.subgraph_monomorphisms_iter()])

结果说明 #

你给出的示例中，子图是7节点星型结构，唯一的6度中心节点只能映射到大图中同样是6度的节点0，子图的其余6个节点可以任意排列映射到大图的1-6节点，最终会输出720种（6的阶乘）合法映射结果。
如果匹配需要同时校验节点属性或边属性，可以在初始化GraphMatcher时传入node_match、edge_match参数自定义匹配逻辑。

内容的提问来源于stack exchange，提问作者Ken Goss