给定两个图（A 和 B），我试图根据边权重的差异确定是否存在与给定某个阈值的 A 匹配的 B 的子图。也就是说，如果我取每对关联边之间的差值之和，它将低于指定的阈值。A 和 B 之间的顶点标签不一致，所以我只依赖边缘权重。
A 会有点小（例如最大 10），而 B 会更大（例如最大 200）。
问问题
573 次
1 回答
0
我相信这两个软件包之一可能会有所帮助：
MATLAB 中的图形匹配工具箱“使用仿射约束 (SMAC) 实现谱图匹配，可选择使用克罗内克双随机标准化”。它在网页上声明它“处理不同大小的图（子图匹配）” http://www.timotheecour.com/software/graph_matching/graph_matching.html
MATLAB 中的图匹配工具箱中使用的算法基于 Timothee Cour、Praveen Srinivasan 和 Jianbo Shi 题为“平衡图匹配”的论文中描述的算法。该论文发表在 NIPS 2006 上。
此外，还有一个名为 Graph Matching Toolkit (GMT) 的工具包，它似乎支持容错子图匹配，因为它确实支持容错图匹配。它不是使用谱法，而是有多种计算编辑距离的方法，然后我的印象是它通过给出最小编辑距离的argmax来找到最佳匹配。如果它不明确支持子图匹配并且您不关心效率，则可以只搜索 B 的所有子图并使用 GMT 尝试在 A 中查找这些子图的匹配项。或者您可以只搜索B. http://www.fhnw.ch/wirtschaft/iwi/gmt的子图
不幸的是，这些似乎都不在 Python 中，而且它们似乎也不支持 networkx 的图形格式。但我相信您可能能够找到一个转换器，它将 networkx 图的表示更改为这些工具包可用的东西。然后你可以运行工具包并输出你想要的子图匹配。
于 2017-02-13T22:37:10.917 回答