关于子图枚举的相关问题，我已经搜索过了。但是，他们不符合我的要求(*)。 (如果我误解了什么，请告诉我。)
是否有一种有效的算法或工具来枚举无向父图的所有“连接且未标记”的子图。
在我的例子中，父图是一个 Internet 拓扑，因此节点数量可能很大。我想枚举父图的所有连接的未标记模式(即子图)。
(*) 我搜索了Efficiently find all connected subgraphs和 Subgraph enumeration但它们都分别针对顶点标记的诱导子图和完整子图。但我想要的只是连接的未标记子图。
最佳答案
一个可能有帮助的主题名称是“频繁子图挖掘”，这似乎是它的一个名称。当然，该领域有各种工具和算法，尽管它们可能无法完全满足您的要求。
正如您链接中两个问题的答案中的其他人指出的那样，大图的子图数量可能非常大。假设您真的想列出它们，而不只是计算它们，那么这可能需要很长时间。
编辑:OP 指出这里的输入是一个大图，而不是一组较小的图，这不适用于标准图挖掘
我仍然认为通用方法在这里可以奏效。用于挖掘的输入图集是数据图子图的某个子集。但是那个子图集是你首先想要的!
所以假设您选择了您想要的子图大小(假设有 6 个顶点)，然后您随机选择父级(互联网拓扑)中的起始顶点并“生长”这些种子，在每个生长步骤中剔除那些不匹配。然后对不同大小的子图重复。
当然，这是一个概率算法，但它可以给你一些想法。
关于algorithm - 子图枚举的高效算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29969341/