Listing All Maximal Cliques in Large Sparse Real-World Graphs

By David Eppstein, Darren Strash. JEAL, 2011

356 citations recorded by the source corpus.

We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, Loffler, and Strash (ISAAC 2010) and analyze its performance on a large corpus of real-world graphs. Our analysis shows that this algorithm is the first to offer a practical solution to listing all maximal cliques in large sparse graphs. All other theoretically-fast algorithms for sparse graphs have been shown to be significantly slower than the algorithm of Tomita et al. (Theoretical Computer Science, 2006) in practice. However, the algorithm of Tomita et al. uses an adjacency matrix, which requires too much space for large sparse graphs. Our new algorithm opens the door for fast analysis of large sparse graphs whose adjacency matrix will not fit into working memory.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/ff8c2bfe566808be9029c719c7b4cd37d6249d39

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Autonomously constructing hierarchical task networks for planning and human-robot collaboration (2016, methodology): “This step can be accomplished in time O(d|V |3) using the Bron-Kerbosch algorithm [29], where d is the degeneracy of the graph and |V | is the number of graph vertices,”
The Anatomy of the Facebook Social Graph (2011, background): “In contrast, Eppstein and Strash recently examined the degeneracy of several graphs, both social and non-social, and found that across the entire graphs (not examining only neighborhoods), the degeneracies were much more modest [29].”