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