Fast Maximum Clique Algorithms for Large Graphs
Ryan A. Rossi

David F. Gleich

Purdue UniversityPurdue University

Assefaw H. Gebremedhin
Purdue University

rrossi@purdue.edu

dgleich@purdue.edu
Md. Mostofa Ali Patwary

agebreme@purdue.edu

Northwestern University

mpatwary@eecs.northwestern.edu
ABSTRACT

11. bio

Categories and Subject Descriptors
G.2.2 [Graph theory]: Graph algorithms; H.2.8 [DatabaseApplications]: Data Mining

1.

ALGORITHMS AND APPLICATIONS

We propose a fast, parallel maximum clique finder wellsuited for applications involving large sparse graphs. Ouralgorithm is a branch and bound method with novel andaggressive pruning strategies. Branch and bound type algorithms for maximum clique explore all maximal cliquesthat cannot be pruned via search tree optimizations [3, 7,5, 8]. They differ chiefly in the way the pruning is done.
Our algorithm is distinguished by several features. First,
it begins by finding a large clique using a near linear-timeheuristic; the obtained solution is checked for optimality before the algorithm proceeds any further, and the algorithm isterminated if the solution is found to be optimal. Second, weuse this heuristic clique, in combination with (tight) upperbounds on the largest clique, to aggressively prune. Theupper bounds are computed at the level of the input graphor individual neighborhoods. Third, we use implicit graphedits and periodic full graph updates in order to keep ourCopyright is held by the author/owner(s).
WWW’14 Companion, April 7–11, 2014, Seoul, Korea.
ACM 978-1-4503-2745-9/14/04.
http://dx.doi.org/10.1145/2567948.2577283.

2. collab

0.8

3. interω̃/ ωWe propose a fast, parallel maximum clique algorithm forlarge sparse graphs that is designed to exploit characteristics
of social and information networks. Despite clique’s status
as an NP-hard problem with poor approximation guarantees,
our method exhibits nearly linear runtime scaling over realworld networks ranging from 1000 to 100 million nodes. In atest on a social network with 1.8 billion edges, the algorithm
finds the largest clique in about 20 minutes. Key to theefficiency of our algorithm are an initial heuristic procedurethat finds a large clique quickly and a parallelized branch
and bound strategy with aggressive pruning and ordering
techniques. We use the algorithm to compute the largest
temporal strong components of temporal contact networks.

0.6

4. retweet

0.4

5. tech
6. web

0.2

7. facebook
8. social

01 2

3 4 567

8Figure 1: Results of our heuristic on over 74 networks
originating from 8 types of data. We find that our heuristic (ω̃) finds the largest clique (ω) in biological, collaboration, and web networks in all but one case.

implementation efficient. Additional features the algorithm
incorporates are discussed in the full version of this paper [6].
Heuristic step. Our heuristic, outlined in Algorithm 1,builds a clique by searching around each vertex in the graphand greedily adding vertices from the neighborhood as longas they form a clique. The order of vertices is the degeneracy
order. This heuristic step finds the largest clique in the graphin over half of the social networks we consider (see Figure 1).
It can therefore be used as a stand-alone procedure.
Bounds. Our branch and bound procedure, Algorithm 2,
heavily uses several bounds to prune the search space. Let
the core-number of vertex v be denoted by K(v). If K(G) is
the largest core number of any vertex in G, then K(G) + 1 isan upper bound on the clique size. Well-known relationships
between core numbers, degeneracy order, and coloring allow
us to further tighten this bound. Let L(G) be the numberof colors used by a greedy coloring algorithm in degeneracy
order. Then L(G) ≤ K(G) + 1 and we get a potentiallytighter bound on the size of the largest clique:
Fact 1.1. ω(G) ≤ L(G) ≤ K(G) + 1
We can further improve the bounds in Fact 1.1 by exploiting
the fact that the largest clique must also be in a vertexneighborhood. Let NR (v), the reduced neighborhood graphof v, be the vertex-induced subgraph of G corresponding tov and all neighbors of v that have not been pruned from thegraph yet. All the bounds in Fact 1.1 apply to finding thelargest clique in each of these neighborhood subgraphs:
Fact 1.2. ω(G) ≤ maxv L(NR (v)) ≤ maxv K(NR (v)) + 1
Our algorithm uses the bounds in Fact 1.2 in its search
procedure.

Algorithm 1 Our greedy heuristic to find a large clique.
The input array K holds core numbers of vertices.

log Runtime

2

1 procedure HeuristicClique(G = (V, E) , K)2
Set H = {}, Set max = 03for each v ∈ V in decreasing core number order do
4
if v’s core number is ≥ max then5
Let S be the neighs. of v with core numbers ≥ max
6
Set C = {}7
for each vertex u ∈ S by decreasing core num. do
8
if C ∪ {u} is a clique then Add u to C

10−1−2910−3345678if |C| > max then Set H = C, Set max = |H|
return H, a large clique in G

9log |V| + |E|
Algorithm 2 Our exact maximum clique algorithm.
Figure 2:

The empirical runtime of our exact cliquefinder in social and information networks scales almost
linearly with the network dimension.

Runtime. We plot the runtime of the algorithm pictoriallyin Figure 2 for a representative subset of 32 of the 74 networks.
The figure demonstrates linear scaling between 1000 vertices
and 100M vertices. The runtime for the friendster graph with
1.8 billion edges (from the SNAP collection) is 20 minutes.
The algorithm is parallelized in a shared memory setting
using a worker task-queue and a global broadcast [6]. Our
source code and additional data on an extensive collectionsof networks is available in an online appendix.1
Application. As a demonstrative application, we use ourmaximum clique finder to identify temporal strong components (tSCC), a recently introduced notion [1, 2]. A temporal
network is defined by a set of vertices V and a temporal setof edges ET ⊆ V × V × R+ between the vertices. Specifically,each edge (u, v, t) in a temporal network has a unique timet ∈ R+ . In such a network, a path represents a sequenceof edges that must be traversed in increasing order of edge
times. If each edge represents a contact between two entities,for example, then a path is a feasible route for information.
Two vertices (u, w) are strongly connected if there exists
a temporal path P from u to w and from w to u. And atSCC is a maximal set of vertices C ⊆ V such that any pairof vertices in C are strongly connected [1, 2]. Checking ifa graph has a k-node tSCC is NP-complete. Nonetheless,
we can compute the largest tSCC by finding a maximum
clique in a derived graph called a strong-reachability graph[2]. A strong-reachability graph is obtained by inserting anedge between every pair of vertices in the temporal graphwhenever there is a temporal path between them [4]. A maximum clique in the reachability graph, after non-reciprocatededges have been removed, is then the largest temporal strong
component [2]. When we apply our maximum clique finder tocompute tSCC in reachability graphs with millions of edges,
it takes less than a second.
Acknowledgements. This work is supported in part by
NSF grants CCF-1149756 and CCF-1218916.

2.

REFERENCES[1] S. Bhadra and A. Ferreira. Complexity of connected components
in evolving graphs and the computation of multicast trees indynamic networks. ADHOC-NOW, pages 259–270, 2003.
[2] V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, andV. Latora. Components in time-varying graphs. Chaos,22(2):023101, 2012.
1

The appendix is at https://www.cs.purdue.edu/homes/dgleich/codes/maxcliques/ and the code is at http://ryanrossi.com/pmc.

1 procedure MaxClique(G = (V, E))
2
Set K = CoreNumbers(G) . K is a vertex-indexed array
3
Set H = HeuristicClique(G, K)
4
Remove (explicitly) vertices with K(v) < |H|5
while |G| > 0 do
6
Let u be the vertex with smallest reduced degree
7
InitialBranch(u). the routine grows H
8Remove u from G
9Periodically, explicitly remove vertices from G
10Return H, the largest clique in G

11 procedure InitialBranch(u)12Set P = NR (u)13
if |P | ≤ |H| then return
1415
16
1718
1920

Set KN = CoreNumbers(P)Set K(P ) = maxv∈P KN (v)if K(P ) + 1 < |H| then return
Remove any vertex with KN (v) < |H| from P
Set L = Color(P , KN ) in degen. order . L is nr of colors
if L ≤ |H| then returnBranch({}, P )21 procedure Branch(C, P )22while |P | > 0 and |P | + |C| > |H| do
23
Select a vertex u from P and remove u from P
24
Set C 0 = C ∪ {u}25
Set P 0 = P ∩ {NR (u)}26
if |P 0 | > 0 then27
Set L = Color(P 0 ) in natural (any) order28
if |C 0 | + L > |H| then Branch(C 0 , P 0 )
29
30
31

else if |C 0 | > |H| then
. C 0 is maximal
Set H = C 0. new max clique
Remove any v with K(v) < |H| from G . implicitly[3] P. R. J. Östergård. A fast algorithm for the maximum cliqueproblem. Disc. Appl. Math., 120:197–207, 2002.
[4] R. K. Pan and J. Saramäki. Path lengths, correlations, andcentrality in temporal networks. arXiv, page 1101.5913v2, 2011.
[5] B. Pattabiraman, M. M. A. Patwary, A. H. Gebremedhin,W. Liao, and A. Choudhary. Fast algorithms for the maximumclique problem on massive sparse graphs. In WAW, 2013.
[6] R. Rossi, D. Gleich, A. Gebremedhin, M. Patwary, and M. Ali.
Parallel maximum clique algorithms with applications tonetwork analysis and storage. arXiv preprint arXiv:1302.6256,
pages 1–10, 2013.
[7] E. Tomita and T. Kameda. An efficient branch-and-boundalgorithm for finding a maximum clique with computationalexperiments. J. of Global Optimization, 37(1):95–111, 2007.
[8] J. Xiang, C. Guo, and A. Aboulnaga. Scalable maximum cliquecomputation using mapreduce. In Conference on DataEngineering (ICDE), pages 74–85. IEEE, 2013.