Listing all maximal cliques in large sparse real-world graphs
From MaRDI portal
Publication:5266538
DOI10.1145/2543629zbMATH Open1365.05276arXiv1103.0318OpenAlexW1485742133WikidataQ56210402 ScholiaQ56210402MaRDI QIDQ5266538FDOQ5266538
Maarten Löffler, Darren Strash, David Eppstein
Publication date: 16 June 2017
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Abstract: We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, L"offler, 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.
Full work available at URL: https://arxiv.org/abs/1103.0318
Recommendations
- Listing all maximal cliques in sparse graphs in near-optimal time
- Enumerating maximal cliques in large sparse graphs
- Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
- A new decomposition technique for maximal clique enumeration for sparse graphs
- On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)
Cited In (47)
- Maximal strongly connected cliques in directed graphs: algorithms and bounds
- Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
- Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- SIAS-miner: mining subjectively interesting attributed subgraphs
- Finding Cliques in Social Networks: A New Distribution-Free Model
- Title not available (Why is that?)
- An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
- Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
- Title not available (Why is that?)
- On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs
- Compact structure for sparse undirected graphs based on a clique graph partition
- Essentially tight kernels for (weakly) closed graphs
- On Approximating the Number of $k$-Cliques in Sublinear Time
- Fast circular arc segmentation based on approximate circularity and cuboid graph
- Improved Space Efficient Algorithms for BFS, DFS and Applications
- Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
- Computing dense and sparse subgraphs of weakly closed graphs
- Why Is Maximum Clique Often Easy in Practice?
- Local community detection based on small cliques
- Declawing a graph: polyhedra and branch-and-cut algorithms
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- A Constructive Arboricity Approximation Scheme
- Title not available (Why is that?)
- Computing maximal cliques in link streams
- Constraint and Satisfiability Reasoning for Graph Coloring
- Parallel Maximum Clique Algorithms with Applications to Network Analysis
- Title not available (Why is that?)
- Listing Maximal Independent Sets with Minimal Space and Bounded Delay
- Computing and Combinatorics
- Algorithm Theory - SWAT 2004
- Space efficient linear time algorithms for BFS, DFS and applications
- Efficient enumeration of dominating sets for sparse graphs
- A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation
- On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Proximity Search for Maximal Subgraph Enumeration
- Faster algorithms for counting subgraphs in sparse graphs
- Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- A new decomposition technique for maximal clique enumeration for sparse graphs
- Title not available (Why is that?)
- Efficiently enumerating all maximal cliques with bit-parallelism
- Enumerating maximal cliques in link streams with durations
- 1-planarity testing and embedding: an experimental study
- Worst-case analysis of clique MIPs
- Multivariate algorithmics for finding cohesive subnetworks
This page was built for publication: Listing all maximal cliques in large sparse real-world graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5266538)
