2

我有一个中等大小的图（570 个节点，6912​​7 条边，密度：gexf 格式的 0.42），我想枚举所有大小大于 N 的集团（比如 5）。最有效的方法是什么？我正在寻找任何流行语言或软件包的库。

4

1 回答 1

1

您可以使用实现 Tomita 等人的SNAP 网络分析库。2006 算法。所有其他理论上快速的算法已被证明比 Tomita 等人慢得多。在实践中，至少对于稀疏图（Eppstein et al. 2010）。

如果该算法对大图需要太多内存，您可以尝试 Eppstein 等人的线性空间算法。2010/2011 年。

  • 富田，E。Tanaka, A. & Takahashi, H. 生成所有最大团和计算实验的最坏情况时间复杂度。理论计算机科学, 2006, 363, 28 - 42. DOI:10.1016/j.tcs.2006.06.015

  • 爱普斯坦，D。Löffler, M. & Strash, D. Cheong, O. 在接近最佳时间的稀疏图中列出所有最大团。ISAAC '10：过程。第 21 届算法与计算国际研讨会，Springer Berlin / Heidelberg，2010, 6506, 403-414。DOI:10.1007/978-3-642-17517-6_36

  • Eppstein, D. & Strash, D. 列出大型稀疏现实世界图中的所有最大派系。海'11：过程。第 10 届实验算法国际研讨会，Springer Berlin / Heidelberg，2011, 6630, 364-375。DOI:10.1007/978-3-642-20662-7_31

于 2012-10-03T01:24:01.277 回答