CODEWITHSUNDEEP
graph-theory
derfred
derfred

Reputation: 19841

Clique enumeration in medium sized graph

I have a medium sized graph (570 nodes, 69127 edges, density: 0.42 in gexf format) and I want to enumerate all cliques with a size larger than N (say 5). What is the most efficient method available? I am looking for a library in any popular language or software package.

Upvotes: 2

Views: 231

Answers (1)

edallme
edallme

Reputation: 934

You can use the SNAP network analysis library, which implements the Tomita et al. 2006 algorithm. All other theoretically-fast algorithms have been shown to be significantly slower than Tomita et al. in practice, for sparse graphs at least (Eppstein et al. 2010).

If that algorithm requires too much memory for a large graph, you can try the linear-space algorithm of Eppstein et al. 2010/2011.

  • Tomita, E.; Tanaka, A. & Takahashi, H. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 2006, 363, 28 - 42. DOI:10.1016/j.tcs.2006.06.015

  • Eppstein, D.; Löffler, M. & Strash, D. Cheong, O. Listing all maximal cliques in sparse graphs in near-optimal time. ISAAC '10: Proc. 21st International Symposium on Algorithms and Computation, Springer Berlin / Heidelberg, 2010, 6506, 403-414. DOI:10.1007/978-3-642-17517-6_36

  • Eppstein, D. & Strash, D. Listing all maximal cliques in large sparse real-world graphs. SEA '11: Proc. 10th International Symposium on Experimental Algorithms, Springer Berlin / Heidelberg, 2011, 6630, 364-375. DOI:10.1007/978-3-642-20662-7_31

Upvotes: 1

Related Questions