Project Team Members:
Northwestern University
Fast Max-Clique Finder
Description:
The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, informatics, and many other areas. Although there exist several algorithms with acceptable runtimes for certain classes of graphs, none of them are feasible for massive graphs. We have devised a new exact algorithm which employs novel pruning techniques to very quickly solve for the maximum clique on large sparse graphs. Extensive experiments on several types of synthetic and real-world graphs show that our new algorithm is up to several orders of magnitude faster than existing algorithms for most instances. We also present a heuristic variant that runs orders of magnitude faster than the exact algorithm, while providing optimal or near-optimal solutions. Our algorithms are also well suited for parallelization, and have potential applications in various domains including social networks, which are discussed in our papers (below).
Fast Max-Cliquer is a publicly available code that implements our new and fast hierarchical-pruning based algorithms.
Publications:
- Bharath Pattabiraman, Mostofa Patwary, Assefaw Gebremedhin, Wei-keng Liao, and Alok Choudhary. Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection, Internet Mathematics, 2014. (pdf).
- Bharath Pattabiraman, Mostofa Patwary, Assefaw Gebremedhin, Wei-keng Liao, and Alok Choudhary. Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs, In Proceedings of the 10th Workshop on Algorithms and Models for the Web Graph, Cambridge, MA, Lecture Notes in Computer Science, Springer, vol. 8305, pp. 156-169, 2013. (presentation, pdf).
