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