Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection

Abstract

The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, information retrieval and many other areas related to the World Wide Web. There exist several algorithms for the problem with acceptable runtimes for certain classes of graphs, but many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques and is able to find maximum cliques in very large, sparse graphs quickly. Extensive experiments on different kinds of synthetic and real-world graphs show that our new algorithm can be orders of magnitude faster than existing algorithms. We also present a heuristic that runs orders of magnitude faster than the exact algorithm while providing optimal or near-optimal solutions. We illustrate a simple application of the algorithms in developing methods for detection of overlapping communities in networks.

28 pages, 7 figures, 10 tables, 2 algorithms. arXiv admin note: substantial text overlap with arXiv:1209.5818

References in corpus (10)

• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Benchmark graphs for testing community detection algorithms
• The Dynamics of Viral Marketing
• Detecting the overlapping and hierarchical community structure of complex networks
• Graph Evolution: Densification and Shrinking Diameters
• Predicting Positive and Negative Links in Online Social Networks
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• On the Normalization and Visualization of Author Co-Citation Data Salton's Cosine versus the Jaccard Index

Cited by in corpus (7)

• Omni-swarm: A Decentralized Omnidirectional Visual-Inertial-UWB State Estimation System for Aerial Swarms
• Solving large Maximum Clique problems on a quantum annealer
• TEASER: Fast and Certifiable Point Cloud Registration
• Efficient Maximum $k$-Defective Clique Computation with Improved Time Complexity
• A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates
• Kimera-Multi: a System for Distributed Multi-Robot Metric-Semantic Simultaneous Localization and Mapping
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods