Listing All Maximal Cliques in Large Sparse Real-World Graphs

Abstract

We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, Löffler, 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.

12 pages, 4 figures. To appear at the 10th International Symposium on Experimental Algorithms (SEA 2011)

References in corpus (4)

• Community structure in social and biological networks
• Finding community structure in networks using the eigenvectors of matrices
• The Dynamics of Viral Marketing
• An O(m) Algorithm for Cores Decomposition of Networks

Cited by in corpus (5)

• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Mining Novel Multivariate Relationships in Time Series Data Using Correlation Networks
• Estimating Subgraph Frequencies with or without Attributes from Egocentrically Sampled Data
• Arabesque: A System for Distributed Graph Mining - Extended version
• An Efficient System for Subgraph Discovery