Paper Info
Title
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.
Year
DOI
Venue
2011
10.1145/2543629
ACM Journal of Experimental Algorithmics
Keywords
DocType
Volume
large sparse real-world graph,sparse graphs,theoretical computer science,maximal clique listing,d-degenerate graphs.,adjacency matrix,large sparse graph,sparse graph,fast analysis,practical solution,maximal clique,large corpus,new algorithm,bron-kerbosch algorithm,theoretically-fast algorithm,working memory
Journal
18,
Citations 
PageRank 
References 
77
2.07
51
Authors
3
Name
Order
Citations
PageRank
David Eppstein14897533.94
Maarten Löffler255162.87
Darren Strash323817.72