在中等大小的圖中枚舉集

Question

我有一箇中等大小的圖（570個節點，6912​​7邊，密度：0.42，格式爲gexf），我想列舉所有大小大於N（比如5）的派系。什麼是最有效的方法？我正在尋找任何流行語言或軟件包中的圖書館。

Answer 1

您可以使用SNAP network analysis library，它實現了Tomita et al。 2006算法。所有其他理論上快速的算法都顯示出比Tomita等人慢得多的速度。在實踐中，至少對於稀疏圖（Eppstein et al。2010）。

如果該算法需要大量圖形的內存太多，您可以嘗試Eppstein等人的線性空間算法。 2010/2011。

• Tomita，E.; Tanaka，A。& Takahashi，H.用於產生所有最大派系和計算實驗的最壞情況時間複雜度。理論計算機科學，2006,363,28-42。DOI:10.1016/j.tcs.2006.06.015

• Eppstein，D. Löffler，M。& Strash，D.Cong，O.在近似最優時間內列出稀疏圖中的所有最大派系。 ISAAC '10：Proc。第21屆算法與計算國際研討會，Springer Berlin/Heidelberg，2010,6506,403-414。 DOI:10.1007/978-3-642-17517-6_36

• Eppstein，D. & Strash，D.列出大型稀疏真實世界圖中的所有最大派系。 SEA '11：Proc。第10屆國際實驗算法研討會，Springer Berlin/Heidelberg，2011,6630，364-375。 DOI:10.1007/978-3-642-20662-7_31