Robert R. McCormick School of Engineering and Applied Science Electrical Engineering and Computer Science Department Center for Ultra-scale Computing and Information Security at Northwestern University

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:

Software Download:

CONTACT:

Most files in the suite are self explanatory and include comments. In case you have unresolvable issues or if you would like to give suggestions or contribute software, please email us.

Northwestern University EECS Home | McCormick Home | Northwestern Home | Calendar: Plan-It Purple
© 2011 Robert R. McCormick School of Engineering and Applied Science, Northwestern University
"Tech": 2145 Sheridan Rd, Tech L359, Evanston IL 60208-3118  |  Phone: (847) 491-5410  |  Fax: (847) 491-4455
"Ford": 2133 Sheridan Rd, Ford Building, Rm 3-320, Evanston, IL 60208  |  Fax: (847) 491-5258
Email Director

Last Updated: $LastChangedDate: 2015-03-06 21:41:36 -0600 (Fri, 06 Mar 2015) $