Source-linked AI summary
Listing All Maximal Cliques in Large Sparse Real-World Graphs
David Eppstein, Darren Strash
TL;DR
Maximal-clique listing is difficult because outputs can be exponential, while Tomita et al.’s fast method requires an adjacency matrix that may not fit for large sparse graphs. The paper implements and evaluates the Eppstein–Löffler–Strash algorithm, finding it competitive with Tomita et al. while using linear space. This makes it a practical choice for listing maximal cliques in large sparse graphs.
Problem
Fast maximal-clique listing is needed for sparse graphs, but Tomita et al.’s adjacency-matrix representation limits applicability when large graphs do not fit into working memory.
Method
The paper implements the Eppstein–Löffler–Strash algorithm and compares it with Tomita et al. and adjacency-list variants on real-world and synthetic graphs.
Results
The algorithm is highly competitive with Tomita et al. on sparse graphs, stays within a small constant factor on other graphs, and requires linear space.
Takeaways & Limitations
The algorithm is a fast and reliable choice for listing maximal cliques, especially when the input graph is large and sparse.
Takeaways & Limitations
The study could not compare its results with Cliquer because that program’s newly implemented maximal-clique listing functionality returned incorrect results.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets maximal-clique listing in sparse graphs, where worst-case output can be exponential but real-world inputs are often sparse. It evaluates an Eppstein–Löffler–Strash algorithm designed to retain Tomita-level speed while using linear storage.
- 1 Introduction: Maximal-clique listing can require exponential time, but practical feasibility depends on handling sparse input graphs effectively.Graphs with exponentially many cliques are possible, although such worst-case graphs are not typically encountered in practice.
- 1 Introduction: Tomita et al.’s algorithm is often orders of magnitude faster in practice, but its adjacency matrix can exceed the memory available for large sparse graphs.The paper seeks comparable speed with linear storage cost.
- 1 Introduction: The new algorithm combines Tomita-style pivoting with Bron–Kerbosch recursion and dynamically represents relevant adjacencies during recursive calls.Its analysis uses graph degeneracy as a parameter.
- 1.1 Our Results: The evaluation compares the new implementation with Tomita et al., an adjacency-list variant, and a simplified list-based version across real-world and synthetic graphs.The corpus includes large sparse graphs and graphs that are not as sparse.
- 1.1 Our Results: On large sparse graphs, the new algorithm is as fast or faster than Tomita et al.; on less sparse graphs, it remains within a small constant factor.The new method can also be faster by very large factors on some sparse instances.
2 Preliminaries
The preliminaries define degeneracy and explain Bron–Kerbosch maximal-clique listing with Tomita pivoting. They also describe adjacency-list adaptations and the Eppstein–Löffler–Strash refinement for sparse graphs.
- 2.1 Degeneracy: A graph’s degeneracy is the smallest d such that every subgraph contains a vertex of degree at most d.Both degeneracy and a corresponding ordering can be computed in linear time.
- 2.1 Degeneracy: A degeneracy ordering places each vertex so that it has at most d neighbors later in the ordering.This ordering bounds the candidate-set size in recursive calls.
- 2.2 The Algorithm of Tomita et al.: Bron–Kerbosch maintains a partial clique R, expansion candidates P, and forbidden vertices X, reporting R when both P and X are empty.If P is empty while X is nonempty, the algorithm backtracks without reporting a clique.
- 2.2 The Algorithm of Tomita et al.: Pivoting restricts recursion to non-neighbors of a selected pivot because every maximal clique must contain one of those vertices.Tomita et al. choose a pivot maximizing neighbors in P, minimizing the recursive branches.
- 2.3 Sparse-Graph Implementations: The adjacency-list variant computes pivots by scanning vertices and testing neighbor membership, yielding an O(∆(n −∆)3∆/3) time bound.Its bound depends on maximum degree ∆, which may be substantially larger than degeneracy.
3 Implementation and experiments
The implementation compares adjacency-matrix and adjacency-list variants of Tomita et al. with three Eppstein–Löffler–Strash variants across synthetic and real-world networks. Experiments show the new algorithm is consistently effective on large sparse graphs, while performance varies with graph density and competing implementation.
- Implementation: The study implements three Eppstein–Löffler–Strash variants alongside adjacency-matrix and adjacency-list versions of Tomita et al.The variants include implementations without data structuring, with a linear-space dynamic graph structure, and a simplified representation of subproblems.
- Experimental setup: The implementation runs on a 32-bit Ubuntu 10.10 workstation with 2.6GB of memory, using C compiled with gcc -O2.The processor was a 2.53 GHz Intel Core i5 M460.
- Experimental datasets: The experiments use four public real-world network collections, including social, bibliographic, biological, road, email, citation, co-purchasing, and Web graphs.Synthetic Moon–Moser, DIMACS, and random graphs provide additional reference comparisons.
- Results: Approximately 130× faster performance than Tomita et al. was observed on one of Mark Newman’s four largest graphs.The new algorithm was faster than Tomita et al. on all four largest Newman graphs.
- Results: The new algorithm was significantly faster on the worm and fruitfly BioGRID networks and matched or nearly matched Tomita et al. on the remaining networks, including yeast.The yeast network was relatively dense, so the comparison also tests performance beyond the sparsest cases.
- Results: The algorithm was consistently faster on the tested Pajek networks, and Tomita et al. could not run on two because of their large size.Despite this, the new algorithm found all cliques quickly in those two networks.
- Results: Nearly all Stanford graphs were too large for Tomita et al. to fit into memory, while the new algorithm remained consistently fast across the data sets.The maxdegree implementation was faster on extremely sparse graphs but orders of magnitude slower on the large soc-wiki-Talk network.
- Results: On reference graphs, Eppstein–Löffler–Strash was 2 to 3 times slower than Tomita et al. on many graphs but up to 30 times faster on the sparsest graphs.The maxdegree algorithm was faster in the sparsest cases but significantly slower on other data.
4 Conclusion
The Eppstein–Löffler–Strash algorithm is practical for large sparse graphs and competitive with Tomita et al., while using linear space. Comparisons with Cliquer remain incomplete because its maximal-clique listing functionality returned incorrect results.
- The Eppstein–Löffler–Strash algorithm is practical for listing maximal cliques in large sparse graphs.
- It is highly competitive with Tomita et al. on sparse graphs and remains within a small constant factor on other graphs.
- Linear space for the graph and data structures avoids the adjacency-matrix memory requirement that can exclude large sparse graphs.
- Cliquer could not be included because its newly implemented maximal-clique listing functionality returned incorrect results.