Listing all maximal cliques in large sparse real-world graphs
From MaRDI portal
Publication:5266538
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.
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
Cited in
(55)- Faster maximal clique enumeration in large real-world link streams
- Computing dense and sparse subgraphs of weakly closed graphs
- A constructive arboricity approximation scheme
- Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- On maximal cliques with connectivity constraints in directed graphs
- On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
- Why is maximum clique often easy in practice?
- A linear time algorithm for maximal clique enumeration in large sparse graphs
- Local community detection based on small cliques
- A note on the problem of reporting maximal cliques
- Declawing a graph: polyhedra and branch-and-cut algorithms
- A new decomposition technique for maximal clique enumeration for sparse graphs
- Proximity Search for Maximal Subgraph Enumeration
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- Compact structure for sparse undirected graphs based on a clique graph partition
- Algorithm Theory - SWAT 2004
- Essentially tight kernels for (weakly) closed graphs
- Finding cliques in social networks: a new distribution-free model
- Enumerating maximal cliques in link streams with durations
- 1-planarity testing and embedding: an experimental study
- Worst-case analysis of clique MIPs
- An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
- Listing Maximal Independent Sets with Minimal Space and Bounded Delay
- On approximating the number of \(k\)-cliques in sublinear time
- Improved space efficient algorithms for BFS, DFS and applications
- External-memory network analysis algorithms for naturally sparse graphs
- Space efficient linear time algorithms for BFS, DFS and applications
- Maximal strongly connected cliques in directed graphs: algorithms and bounds
- Listing all maximal cliques in sparse graphs in near-optimal time
- Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
- Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
- Parallel maximum clique algorithms with applications to network analysis
- Fast circular arc segmentation based on approximate circularity and cuboid graph
- Computing and Combinatorics
- Faster algorithms for counting subgraphs in sparse graphs
- scientific article; zbMATH DE number 1500539 (Why is no real title available?)
- Efficient enumeration of dominating sets for sparse graphs
- scientific article; zbMATH DE number 7765378 (Why is no real title available?)
- Computing maximal cliques in link streams
- Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
- Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
- An output sensitive algorithm for maximal clique enumeration in sparse graphs
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Efficient enumeration of dominating sets for sparse graphs
- On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs
- Fast maximal cliques enumeration in sparse graphs
- Multivariate algorithmics for finding cohesive subnetworks
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation
- Efficiently enumerating all maximal cliques with bit-parallelism
- Constraint and satisfiability reasoning for graph coloring
- Computing the degeneracy of large graphs
- SIAS-miner: mining subjectively interesting attributed subgraphs
- Enumerating maximal cliques in large sparse graphs
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)
