高效子图枚举算法

Question

我已经搜索了与子图枚举相关的问题，但它们没有满足我的需求。如果我有误解，请告诉我。

是否有一种高效的算法或工具，用于枚举无向父图的所有“连接的、未标记的”子图。

在我的情况下，父图是互联网拓扑结构，因此节点数量可能很大。我想枚举父图中所有连接的未标记模式（即子图）。

我已经搜索了Efficiently find all connected subgraphs和Subgraph enumeration，但它们都针对顶点标记诱导和完全子图。但我只想要连接的未标记子图。

- taylrj

---

如果父图是顶点标记的（我所知道的所有计算机表示都是隐式顶点标记的），并且您想要仅生成不同的未标记子图，则需要多次解决NP完全的子图同构问题。（如果您从包含某些图的两个副本的父图开始，很容易看出这一点：对于第一个副本的任何子图，在考虑第二个副本的子图时，如何避免生成该子图第二次？） - j_random_hacker

@j_random_hacker - 在这个问题中，“未标记的子图”要求是由于我的目标图形是Internet拓扑结构的子网（即网络的图形）。与其他针对化学结构的问题相比[注]，我的问题可能是一个“未标记”的子图枚举问题，因为Internet上的任何节点都被认为是相同的，我只对它们的模式感兴趣。[注] 子图枚举 链接 - taylrj

@j_random_hacker - 正如你所提到的，我知道可能不存在一个高效的算法，因为无法避免重复的子图同构测试。然而，我仍然想知道是否有任何想法可以解决这个问题。非常感谢任何评论。 - taylrj

Answer 1

一个可能有帮助的主题名称是“频繁子图挖掘”，这似乎是此项工作的一种名称。该领域中有各种工具和算法，尽管它们可能不完全符合您的要求。

正如其他人在您链接的两个问题的答案中指出的那样，大型图的子图数量可能非常多。假设您实际上想要列出它们，而不仅仅是计数，那么可能需要很长时间。 编辑：OP指出，此处的输入是一个大型图形，而不是一组较小的图形集，这将无法使用标准图形挖掘

我仍然认为一般方法在这里可以起作用。挖掘的图形输入集是数据图形的某些子图的子集。但是，这个子图集就是您首先想要的！

因此，假设您选择了一个所需的子图大小（假设为6个顶点），然后在父级（互联网拓扑）中随机选择起始顶点并“增长”这些种子，在每个增长步骤中淘汰不匹配的种子。然后为不同大小的子图重复此过程。

当然，这是一种概率算法，但它可以给您一些想法。

- gilleain

---

我之前也搜索过这个主题。在我看来，这个问题涉及到一个包含许多图的图集。并且频繁子图挖掘算法可以列出出现频率最高的图形，并具有整个图形数据集的最小支持度。如果我专门为此问题使用“频繁子图挖掘”工具[注]（该数据集只有一个父图，最小支持度=1），我只能得到异常结束的程序（我认为这可能是由于内存溢出引起的）。[注] gSpan 链接 - taylrj

@TaylorFang 嗯，我明白你的观点。但是如果没有将图挖掘应用于网络拓扑或单个大型图输入，这对我来说仍然很惊讶。例如，在化学反应网络（如代谢网络）中，模式发现方面正在进行积极的研究。 - gilleain

非常感谢您的帮助。让我用自己的话来实现您的想法。在每次迭代中，随机选择种子并通过添加共享相同端点（即种子）的边来生长，并同时通过同构测试修剪不匹配的边。当种子的大小达到首次选择的大小时，它将被放入子图集中。通过增加首次选择的大小，大多数子图将作为结果被发现。 - taylrj

@TaylorFang 是的，听起来没错。这种“增长”方法相当普遍，并且应该在其他地方有很好的描述 - 当然除了多输入图的情况。可能存在访问所有子图（特定大小）仅一次的问题，以及如果两个子图开始重叠该怎么办的问题（尽管这对您可能不是问题）。 - gilleain