SIAM J. SCI. COMPUT.
Vol. 37, No. 5, pp. C589–C616

c 2015 Society for Industrial and Applied Mathematics


PARALLEL MAXIMUM CLIQUE ALGORITHMS WITH
APPLICATIONS TO NETWORK ANALYSIS∗RYAN A. ROSSI† , DAVID F. GLEICH† , AND ASSEFAW H. GEBREMEDHIN‡
Abstract. We present a fast, parallel maximum clique algorithm for large sparse graphs that isdesigned to exploit characteristics of social and information networks. The method exhibits a roughly
linear runtime scaling over real-world networks ranging from a thousand to a hundred million nodes.
In a test on a social network with 1.8 billion edges, the algorithm ﬁnds the largest clique in about 20
minutes. At its heart the algorithm employs a branch-and-bound strategy with novel and aggressive
pruning techniques. The pruning techniques include the combined use of core numbers of vertices
along with a good initial heuristic solution to remove the vast majority of the search space. In
addition, the exploration of the search tree is parallelized. During the search, processes immediately
communicate changes to upper and lower bounds on the size of the maximum clique. This exchange
of information occasionally results in a superlinear speedup because tasks with large search spaces
can be pruned by other processes. We demonstrate the impact of the algorithm on applications using
two diﬀerent network analysis problems: computation of temporal strong components in dynamic
networks and determination of compression-friendly ordering of nodes of massive networks.
Key words. parallel maximum clique algorithms, branch-and-bound, network analysis, temporal strong components, graph compression
AMS subject classifications. 05C69, 05C82, 05C85, 05C90, 90C27
DOI. 10.1137/14100018X

1. Introduction. The maximum clique problem seeks to ﬁnd a clique (complete
subgraph) of the largest possible size in a given graph. The problem is, in general, NPhard to solve, even in an approximate sense [34]. As a result, one is inclined to believethat exact algorithms for ﬁnding maximum cliques will be too slow to be practical forlarge network analysis applications. In fact, because of this inclination, in a numberof network analysis problems where maximum cliques are the natural and accurate
models, practitioners frequently settle for loose, approximate models representing“dense-enough” subgraphs that can be detected quickly or heuristic clique methods
that generally perform well enough in practice. Yet, many real-world problems havefeatures that do not elicit worst-case behaviors from well-designed algorithms.
In this paper, we present a demonstrably fast, parallel, exact algorithm for the
maximum clique problem. The presentation includes the design, implementation,
analysis, and performance evaluation of the algorithm. Further, enabled by its eﬃciency, we use the clique ﬁnder to achieve three goals: (i) study maximum cliquesin large-scale social and information networks, (ii) ﬁnd the largest temporal strong
components in time-varying networks, and (iii) obtain compression-friendly orderingsof vertices in graphs.
The algorithm. In its basic form, our algorithm is a branch-and-bound method∗ Submitted to the journal’s Software and High Performance Computing section December 15,
2014; accepted for publication (in revised form) July 21, 2015; published electronically October 22,
2015. A two-page preliminary version of this work appeared in the proceedings of WWW 2014 [51].
http://www.siam.org/journals/sisc/37-5/100018.html† Department of Computer Science, Purdue University, West Lafayette, IN 47906 (rrossi@purdue.
edu, dgleich@purdue.edu). The second author’s research was supported by NSF CAREER award
CCF-1149756.
‡ School of Electrical Engineering and Computer Science, Washington State University, Pullman,
WA 99163 (assefaw@eecs.wsu.edu). This author’s research was supported by NSF award CCF1218916 and by Department of Energy award DE-SC0010205.

C589

C590

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

log Runtime

2
1
0
−1
−2
−3
3

4

5

6

7

8

9

log |V| + |E|
Fig. 1. A log-log plot of the runtime of our clique ﬁnder on 32 social and information networks
drawn from a variety of domains. The plot shows that the runtime scales almost linearly with
network dimension.

with novel pruning strategies. Several key components stand out as features contributing to its eﬃciency and distinguishing it from existing algorithms.
First, the algorithm begins by ﬁnding a large clique using a near-linear-time heuristic; the obtained solution is checked for optimality (using the bounds described in section 3) before the algorithm proceeds any further, and the algorithm is terminated if
the solution is found to be optimal. Second, we use the heuristic solution, in combination with (tight) upper bounds on the largest clique, to aggressively prune the graph.
The upper bounds are computed at the level of the input graph or local neighborhoods.
Third, we use implicit graph edits and periodic full graph updates in order to keep our
implementation eﬃcient. Fourth, we parallelize the search procedure. The parallel
search is designed such that processes (workers) immediately communicate changes
to upper and lower bounds on the size of maximum clique. As a result, vertices withespecially large search spaces can be pruned by other processes, which occasionallyresults in a superlinear speedup. Finally, rather than a ﬁxed algorithm, our method isa framework that can be specialized into diﬀerent variants. The framework is tunable
in the sense that the graph representation, data structures, and the implementationsof the algorithm can be adapted based on the properties of the input graph and thetarget system. The framework is discussed in detail in section 4, the bounds it uses
in its pruning strategies are reviewed in section 3, and the framework’s overall performance is evaluated and compared against existing methods in section 5. We havemade our implementation publicly available at https://github.com/ryanrossi/pmc.
Cliques in large social and information networks. Our investigation on large-scalesocial and information networks (section 2) reveals that ﬁnding the largest clique insuch networks can in practice be done fast (see Table 1). By way of example, using
the maximum clique algorithm proposed here, we can ﬁnd the maximum clique insocial networks with nearly two billion edges in about 20 minutes on a 16-core sharedmemory system. More generally, our method is observed to have a roughly linear
runtime (Figure 1) for these networks. As a point of comparison, our new solver signiﬁcantly outperforms a recent fast maximum clique ﬁnder that we developed [48, 49]
as well as an oﬀ-the-shelf clique enumerator (section 5). Consequently, we expect the
new algorithm to be useful for various tasks in which maximum cliques are needed suchas analyzing large networks, evaluation of graph generators, community identiﬁcation,
and anomaly detection.
Applications. One motivation for this work came from a connection between the

PARALLEL MAXIMUM CLIQUE ALGORITHMS

C591

largest temporal strong component of a dynamic network and maximum cliques in an
associated graph. In a network where each edge represents a contact—a phone call,an email, or physical proximity—between two entities at a speciﬁc point in time, onegets an evolving network structure [26] where a temporal path represents a sequenceof contacts that obeys time. A temporal strong component is a set of vertices where
all pairwise temporal paths exist, just like a strong component is a set of vertices
where all pairwise paths exist.
Surprisingly, checking whether an evolving network has a temporal strong component of size k is NP-complete [42, 3]. For some intuition, consider the following “wrong”
reduction from the perspective of establishing NP-hardness. A temporal strong component of size k corresponds to a clique of size k in a temporal reachability graphwhere each edge represents a temporal path between vertices. Finding the maximum
clique, then, reveals the largest temporal strong component. This connection may
initially appear not helpful in practice, since computing, or even approximating, thelargest clique in a graph is NP-hard. If a fast algorithm (for real-world instances) is inplace, however, the connection can be exploited. We apply our maximum clique ﬁnder
for this analysis and discuss properties of temporal components we ﬁnd in Twitterand phone call networks in section 6.1.
Previous studies have found bipartite cliques useful for compressing networks [10].
Here we tackle an easier problem and use cliques to compute a compression-friendly
ordering that makes many edges in the graph local. We ﬁnd (section 6.2) that thisordering generates results that are nearly as good as existing heuristics tailor-designed
for that problem.
Related work. Pardalos and Xue [47] provide a good review of exact algorithms
for maximum clique that existed prior to 1994. Notable methods proposed sincethen include, among others, the works of Bomze et al. [8], Östergård [44], Tomita andKameda [58], and San Segundo, Rodrı́guez-Losada, and Jiménez [52]. In a recent work,
Prosser [50] provides a computational study comparing various exact algorithms for
maximum clique. The vast majority of existing work focuses on sequential maximum
clique ﬁnders, but there is growing work on parallel algorithms as well. Recent work on
parallel algorithms includes the multithreaded algorithm of McCreesh and Prosser [41]and the MapReduce-based method due to Xiang, Guo, and Aboulnaga [64].
A problem related to maximum clique ﬁnding is maximal clique enumeration:
identifying all the maximal cliques in G. There is a considerable body of recent workon this problem. Tomita, Tanaka, and Takahashi [59] look at the worst-case timecomplexity of generating all maximal cliques and conduct computational experiments.
Eppstein and coworkers [24, 23] show how eﬃcient data structures can be used todesign algorithms for clique enumerations in near optimal time. Schmidt et al. [54]develop parallel algorithms for maximal clique enumeration, and Cheng and coworkers [13, 14] consider clique enumeration on massive graphs. Xie and Yu [65] show
the connection of the clique enumeration problem to frequent pattern mining. Du
and coworkers [20, 21] ﬁnd that maximal cliques in social networks are distributed
according to a power-law; in particular [21] takes advantage of the properties of social
and information networks in order to enumerate all maximal cliques faster. In comparison, we show here how we can develop fast algorithms for solving the maximum
clique problem for these networks and temporal strong components by appropriately
applying pruning steps and bounds.
2. Cliques in social and information networks. Before presenting the details of our new algorithm, we begin by demonstrating how fast it ﬁnds maximum

C592

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

Table 1
Properties of and results on 32 of the social and information networks studied here. The numberof vertices |V | and edges |E| are followed by K for thousands, M for millions, and B for billions. The
column K + 1 corresponds to a core number-based upper bound on maximum clique size, ω̃ denotes
the size of the clique obtained by the initial heuristic step, and ω denotes the actual maximum cliquesize. The last column shows the runtime of the exact algorithm. It can be seen that our algorithm
took less than 21 minutes to solve the “largest” problem in the collection.
Graph

|V |

|E|

K+1

ω̃

ω

Time (s)1.

celegans
dmela

453
7.4K

2.0K
26K

11
12

9
7

9
7

<.01
0.06

2.

mathsciet
dblp
hollywood

333K
317K
1.1M

821K
1.0M
56M

25
114
2209

25
114
2209

25
114
2209

0.08
0.05
1.69

3.

wiki-talk

92K

361K

59

14

15

0.09

4.

retweet

1.1M

2.3M

19

13

13

0.58

5.

whois
rl-caida
as-skitter

7.5K
191K
1.7M

57K
608K
11M

89
33
112

55
17
66

58
17
67

0.09
0.13
1.2

6.

arabic-2005
wikipedia2
it-2004
uk-2005

164K
1.9M
509K
130K

1.7M
4.5M
7.2M
12M

102
67
432
500

102
31
432
500

102
31
432
500

0.03
1.16
0.12
0.06

7.

cmu
mit
stanfordberkeleyuillinois
penn
texas
fb-a
fb-b
uci-uni

6.6K
6.4K
12K
23K
31K
42K
36K
3.1M
2.9M
59M

250K
251K
568K
852K
1.3M
1.4M
1.6M
24M
21M
92M

70
73
92
65
86
63
82
75
64
17

45
32
51
42
56
43
49
23
23
6

45
33
51
42
57
44
51
25
24
6

0.09
0.1
0.09
0.16
0.18
0.24
0.33
6.3
5.52
33.86

8.

slashdot
gowallayoutubeflickrlivejournal
orkut
twitterfriendster

70K
197K
1.1M
514K
4.0M
3.0M
21M
66M

359K
950K
3.0M
3.2M
28M
106M
265M
1.8B

54
52
52
310
214
231
1696
304

25
29
16
45
214
44
174
129

26
29
17
58
214
47
323
129

0.06
0.2
0.84
5.2
2.98
48.49
598
1205

cliques in various social and information networks and highlighting observations wemake regarding the cliques obtained.
We experiment in this section with 32 networks categorized into eight broadclasses. (In the appendix we report results on a more extensive collection of networks
comprising 76 social and information networks and 63 dense graphs from the 1996
DIMACS Clique Challenge [61].) Table 1 lists the names and sizes of the 32 networks
considered here. (Detailed data on the properties of these networks is provided inTables 4–6 in the appendix). Table 1 also lists the size of the largest clique in each
network and the time it took the algorithm to ﬁnd each clique. We plot the runtime
pictorially in Figure 1, which shows a linear scaling between a thousand and a hundred
million vertices.
Below we brieﬂy describe the networks and what cliques within them signify.
For all of the networks, we discard edge weights and self-loops when they exist. In
addition, if the graph is directed, we remove nonreciprocated edges. This strategy
will identify fully directed cliques. Further, for networks with multiple components,
we consider only the largest connected component (when undirected) and the largest

PARALLEL MAXIMUM CLIQUE ALGORITHMS

C593

strongly connected component (when directed).
1. Biological networks. We study a network where the nodes are proteins and theedges represent protein-protein interactions (dmela [56]), and another where nodes
are substrates and edges are metabolic reactions (celegans [31]). Cliques in these
networks signify biologically relevant modules.
2. Collaboration networks. These are networks in which nodes represent individuals and edges represent scientiﬁc collaborations or movie production collaborations(mathscinet [45]; dblp, hollywood [5]). Large cliques in these networks are expected because they are formed when collaborations involve many participants.
3. Interaction networks. Here, nodes represent individuals, and edges representinteraction in the form of message posts (wiki-talk [38]). Cliques in such networks
represent mutually interacting groups of individuals.
4. Retweet networks. Here, nodes are Twitter users, and two users are connectedby an edge if they have retweeted each other (retweet). We collected the network
retweet ourselves. A clique here is a group of users that have all mutually retweeted
each other; it may represent an interest cartel or an anomaly.
5. Technological networks. The nodes in these networks are routers, and edges areobserved communications between the entities (as-skitter, rl-caida [11]; whois [62]).
A clique represents all-to-all communication among entities.
6. Web link networks. Here, nodes are Web pages, and edges are hyperlinks
between pages (wikipedia [17]; arabic-2005, it-2004, uk-2005 [4]). Large cliques
represent large sets of pages where full pairwise navigation is possible.
7. Facebook networks. Nodes represent people, and edges are “Facebook friendships” (cmu, mit, stanford, berkeley, uillinois, penn, texas [60]; fb-a, fbb [63]; uci-uni [28]). Cliques here are groups of people with mutual friendships.
8. Social networks. Nodes are again people, and edges are social relationships in
the form of friendship or follower (orkut, livejournal, youtube [66]; slashdot[39]; gowalla [15]; flickr [29]; twitter [37]; friendster [66]).
We summarize below our ﬁndings about cliques in these networks and the performance of our algorithm as follows:• We observe that the initial heuristic step of the algorithm ﬁnds the largest cliquein most cases: 17 of the 32 instances considered here, and 54 of the 76 networks
considered in Tables 4–6 in the appendix; see the left plot in Figure 2 for a summary.
This property helps our exact maximum clique algorithm terminate quickly.
• We studied the relationship between the largest k-core (a notion to be discussed in
section 3) and the largest clique. The right part of Figure 2 shows a summary of
the results we obtained on all 76 networks. In the collaboration and most Web-link
networks, we ﬁnd that the largest k-core coincides with a maximum clique in thegraph. The social networks, in comparison, have a much larger diﬀerence between
the two, which suggests a fundamental diﬀerence in the types of networks formed
via collaboration relationships versus social relationships.
• We observe that technological networks have surprisingly large cliques. Given thata clique represents an overly redundant set of edges, this would suggest that thesemaximum cliques represent over-built technology, or critical groups of nodes.
• We observe that for the twitter network, the nodes in the largest clique are neither of the two obvious suspects, that is, (i) just spam accounts nor (ii) legitimate
accounts with massive numbers of followers and following similar large numbers.
Rather, the largest clique consists of some combination of nodes from the two
sets. We believe that most members of this clique likely reciprocate all follower

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

1

1

0.8

0.8
ω/ ( K + 1)

ω̃/ ω

C594

0.6
0.4
0.2
0

1. bio2. collab
3. inter

0.6

4. retweet

0.4

5. tech
6. web

0.2
1 2

3 4 5

6

7

8

0

7. faceboo
8. social
1 2

3 45

6

7

8

Fig. 2. These two plots summarize the results on all the 76 social and information networks
listed in Tables 4–6 in the appendix. The left panel plots the ratio of the clique size obtained byour heuristic (ω̃) to the largest clique size obtained by the entire algorithm (ω). It shows that theheuristic gives the exact solution in the biological, collaboration, and web networks in all but one
case. The right panel plots of the ratio of the maximum clique size (ω) to the largest core number
plus one (K +1). The ﬁgures identiﬁes the networks where the core number tightly bounds the largest
clique.

relationships.
3. Bounds on maximum clique size. As a prelude to our maximum cliquealgorithm, we review a few easy-to-derive upper bounds on the size of the largest
clique ω(G) in a graph G. These bounds will allow us to terminate our algorithm
once we have found something that hits the upper bound or stop a local search earlybecause no larger clique exists.
A simple upper bound on the size of the largest clique is the maximum degree
Δ(G) in the graph. Usually this is too simple to be useful. A stronger bound can beobtained using k-cores. A k-core in a graph G is a vertex induced subgraph where
all vertices have degree at least k [55]. The core number of a vertex v is the largest
k such that v is in a k-core. We denote it by K(v), and we denote by K(G) the
largest core number in the entire graph G. Suppose that G contains a clique of sizeq. Then each vertex in the clique has degree q − 1, and the entire graph must havea (q − 1)-core. Thus K(G) + 1 is an upper bound on the largest clique size ω(G).
Note that, in contrast to cliques, the core numbers of all vertices in a graph can becomputed with a linear-time algorithm [2].
The value K(G) is also known as the degeneracy of the graph. The quantity
K(G) + 1 is an upper bound on the number of colors used by a greedy coloringalgorithm that processes vertices in order of decreasing core numbers—also known asdegeneracy order [25]. The number of colors used by any greedy coloring of G is also
an upper bound on the size of the largest clique because a clique of size k requires kcolors. Let L(G) be the number of colors used by a greedy coloring algorithm thatuses the degeneracy order. Then L(G) ≤ K(G) + 1, and we get a potentially tighter
bound on the size of the largest clique. The bound L(G) can be computed in linear
time with some care about the implementation of the greedy coloring scheme [27, 40].
We summarize the bounds we have at this point as follows.
Fact 3.1. ω(G) ≤ L(G) ≤ K(G) + 1 ≤ Δ(G) + 1.
We can further improve the bounds in Fact 3.1 by using one additional fact abouta maximum clique in a graph. Deﬁne the neighborhood graph of a vertex v to be
the graph induced by v and its neighbors. Then any neighborhood graph of a vertex

PARALLEL MAXIMUM CLIQUE ALGORITHMS

C595

within the largest clique has a clique of the same size within the neighborhood graphas well. The way our algorithm proceeds is by iteratively removing vertices from thegraph that cannot be in the largest clique. Let NR (v), the reduced neighborhood
graph of v, be the vertex-induced subgraph of G corresponding to v and all neighborsof v that have not been removed from the graph yet. All the bounds in Fact 3.1
apply to ﬁnding the largest clique in each of these neighborhood subgraphs. We cantherefore state the following.
Fact 3.2.
(3.1)

ω(G) ≤ max L(NR (v))
v

(3.2)

≤ max K(NR (v)) + 1(3.3)≤ max Δ(NR (v)) + 1.

vv

Computing the tighter bounds in Fact 3.2 requires slightly more than linear work.
For each vertex, we need to form the neighborhood graph. If we look at the union of
all of these neighborhood graphs, there is a vertex in some neighborhood graph foreach edge in G. Thus there are a total of O(|E|) vertices in all neighborhoods. By
the same argument, there are O(|E| + |T |) edges, where |T | is the total number oftriangles in the graph. Consequently, we can make the following statement.
Fact 3.3. The total work involved in computing the bounds in Fact 3.2 is boundedby O(|E| + |T |).
4. A maximum clique algorithms framework. Given an undirected graph
G = (V, E), let Cv denote a clique of the largest size containing the vertex v. A
maximum clique in G can be found by computing Cv for every vertex v in V andthen picking the largest among these. This clearly is wasteful. Most branch-andbound–type algorithms for maximum clique speed up the process by keeping aroundthe size of the largest clique computed at any point in the course of the algorithm(maxSoFar) and avoiding computation of every Cu , u ∈ V , that would eventually besmaller than maxSoFar, a process generically referred to as pruning [47, 44, 58, 48, 64].
The algorithms diﬀer chieﬂy in the way the pruning is done. The algorithm wedeveloped in recent work [48] uses a hierarchical pruning strategy that relies primarilyon comparisons of degrees of vertices in the original input graph with maxSoFar,
eﬀectively using the weakest bound in Fact 3.1. In comparison, the new method
presented here uses the tightest bound in Fact 3.2. Furthermore, the method contains
a variety of new algorithmic and performance optimization ingredients that result insigniﬁcantly superior performance (see section 5.5).
For reference throughout the discussion in this section, we outline our algorithm
in the pseudocodes in Algorithms 1 and 2.
4.1. The fast heuristic clique finder. Our exact maximum clique algorithm
begins by calling a fast heuristic clique ﬁnder that makes use of core numbers ofvertices, which in turn is computed in a prior auxiliary step (see Lines 2 and 3 in theprocedure MaxClique in Algorithm 2). The goal of the initial heuristic step is to ﬁnda large clique in the graph quickly. The heuristic is similar to the maximum-degree–
based heuristic described in [48, 49], which, in exploring for a maximum clique in whicha vertex v participates, simply picks a vertex of the highest degree in the neighborhoodof v. The heuristic search described here diﬀers, as we use core numbers of vertices toguide the search instead. The inspiration for this change is the relationship between

C596

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

core numbers, the degeneracy order, and a simple 2-approximation algorithm for thedensest subgraph problem [36, 12].
Algorithm 1. Our greedy heuristic to ﬁnd a large clique. This is used as the ﬁrst
step in the exact algorithm, outlined in Algorithm 2. The input array K holds corenumbers of vertices. The output of the algorithm is a large clique H.
1 procedure HeuristicClique(G = (V, E) , K)
2
3
4
5
6
7
8
9
10
11
12

Set H = {}, Set max = 0
for each v ∈ V in decreasing core number order do
if v’s core number is ≥ max then
Let S be the neighbors of v with core numbers ≥ max
Set C = {}for each vertex u ∈ S by decreasing core number do
if C ∪ {u} is a clique thenAdd u to C
if |C| > max thenSet H = C, Set max = |H|
return H, a large clique in G

The heuristic, outlined in Algorithm 1, builds a clique by searching around eachvertex in the graph and greedily adding vertices from the neighborhood as long as they
form a clique. The order of vertices is the degeneracy order (the input parameter K
contains the needed core numbers of the vertices; we write it in boldface to indicatethat it is a vector (an array)). Because the core numbers are also a lower bound on thesize of the largest clique a vertex participates in, we can eﬃciently prune the greedy
exploration.
As mentioned in section 2, this heuristic step in itself ﬁnds the largest clique inthe graph in over half of the social networks we consider. It can therefore be used
as a stand-alone procedure. All steps in Algorithm 1, except for the statements inlines 7–9, can be performed using work proportional to the degree of a vertex. Thosestatements in turn require work proportional to the size of the subgraph induced by
the neighborhood of a vertex. The overall runtime can therefore be (loosely) upperbounded by O(|E| · Δ(G)).
4.2. Initial pruning. After our exact algorithm ﬁnds a heuristic clique H in
the input graph G using the core numbers of the vertices, it puts those numbers toanother strategic use. Suppose we ﬁnd a clique in G of size ω̃ = |H|. Then we caneliminate all vertices with core numbers strictly less than ω̃ from our search (Line
4 in MaxClique). This pruning operation works because a clique of size ω̃ + 1 orlarger must have vertices with core numbers at least ω̃. In a few cases, we observedthat this step suﬃces to certify that H is the maximum clique as we remove all of
the graph. This happens, for instance, with the LiveJournal network. Moreover, thispruning procedure reduces memory requirements signiﬁcantly for most networks.
In our implementation, for this initial pruning, vertices are explicitly removed
from the graph. This step often removes a substantial fraction of the total vertices
and reduces the total memory required to store the graph.
4.3. Searching. After we reduce the size of the graph via the initial pruning, wethen run a search strategy over all the remaining vertex neighborhoods in the graph(the while-loop in MaxClique). The algorithm we run is similar to a standard (Bron–
Kerbosch) branch-and-bound scheme for maximal clique enumeration [9]. However,C597

PARALLEL MAXIMUM CLIQUE ALGORITHMS

Algorithm 2. Our exact maximum clique algorithm. See section 4.5 fordetails about how to parallelize it.
1 procedure MaxClique(G = (V, E))
2
Set K = CoreNumbers(G) K is a vertex-indexed array
3
Set H = HeuristicClique(G, K)
 H is global (is updated in Branch)
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 return14
Set KN = CoreNumbers(P)15
Set K(P ) = maxv∈P KN (v)16
if K(P ) + 1 < |H| then return
17
Remove any vertex with KN (v) < |H| from P
18
Set L = Color(P , KN ) in degeneracy order19
if L ≤ |H| then return20
Branch(P , {})21 procedure Branch(P, C)
22
while |P | > 0 and |P | + |C| > |H| do
23
Select a vertex w from P and remove w from P
24
Set C  = C ∪ {w}25
Set P  = P ∩ {NR (w)}26
if |P  | > 0 then27
Set L = Color(P  ) in natural (any) order28
if |C  | + L > |H| then29
Branch(P  , C  )30else if |C  | > |H| then31
Set H = C 
32Remove any v with K(v) < |H| from G

 L is number of colors C  is maximal
 new max clique implicitly

we unroll the ﬁrst two levels of branching and apply our clique bounds in order toﬁnd only the largest clique.
At this point, we wish to introduce a bit of terminology. Recall (from section 3)
that NR (v) is the reduced neighborhood graph of v. Let dR (v) denote the reduced degree of v. The reduced neighborhood graphs exclude vertices that have been removed
from the graph due to changes in the lower bound on the clique size caused by k-coresand vertices whose local searches have terminated. At the risk of being overly formal,let ω̃ be the current best lower bound on the clique size, and let X be a set of vertices
removed via searching. ThenNR (v) = G({v} ∪ {u : (u, v) ∈ E, K(u) ≥ ω̃, u ∈ X}).
We explore the remaining vertices in order of the smallest to largest reduced de-C598

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

gree. For each vertex, we explore its neighborhood using the function InitialBranch.
When InitialBranch returns, we have found the largest clique involving that vertex,
and so we can remove it from the graph. This is done by marking it as removed in anarray and then checking that array before using information about the vertex in the
future. This implementation provides constant time deletion operations, albeit withan additional check on use. To eliminate these checks, we ﬁnd it advantageous to periodically recreate the graph data structure in light of all the deletions and recomputek-cores. This reduces the cost of the intersection operations. In addition, we believethat this step aggregates memory access to a more compact region thereby improving
caching on the processor. We do this every four seconds of wall clock time. The four
second interval worked well in our experiments, but the choice is rather arbitrary, andwe did not investigate other choices of intervals in any detail. Here, incorporating thestreaming algorithm proposed in [53] may help make the recomputation of k-cores
more eﬃcient.
The ﬁrst step of InitialBranch is a set of tests to check whether any of thebounds from Fact 3.2 rule out ﬁnding a bigger clique in the neighborhood of the vertex
u being explored. The ﬁrst test (line 13) essentially corresponds to the weakest bound,(3.3), in Fact 3.2. To check against the bound given by (3.2), we compute the corenumbers for each vertex in the neighborhood subgraph. If the largest core numberin the neighborhood subgraph is less than the current lower bound, we immediately
return and add the vertex to the list of searched vertices (line 16). If it isn’t, thenwe compute a greedy coloring of the subgraph using the degeneracy order in orderto obtain the coloring bound from Fact 3.2 (speciﬁcally (3.1)). We check against
this bound, and we immediately return if the comparison suggests no larger clique ispresent (line 19). If none of these checks pass, then we enter into a recursive procedurethat examines all subsets of the neighborhood in a search for cliques (Branch).
The procedure Branch maintains a reduced neighborhood subgraph P and aclique C. The invariant shared by these sets is that we can add a vertex from P to C
and get a clique one vertex larger. We pick a vertex and do this. To be precise, wepick the vertex with the most recently introduced color (in our implementation, thisis the largest color, where colors are positive integer numbers), as this is a weak cliqueindicator. We then check whether the clique C  is maximal by testing whether there
exists any set P  that satisﬁes the invariant. If not, then we test whether it is possiblethat C  and P  have a large clique. The largest clique possible is |C  | + ω(P  ) ≤|C  | + L(P  ), and so, using the function Color, we compute a new greedy coloring
to get the upper bound L(P  ). Unlike the greedy coloring in InitialBranch, here
we do not use the degeneracy ordering, as it was not worth the extra work in ourinvestigations. If C  and P  pass these tests, we recurse on C  and P  . If C  is
maximal, then we compare it against the current best clique H, and update H if C 
is larger.
Illustration (Figure 3). We use the example in Figure 3 to illustrate several of
the points we have been discussing thus far. The core number K(G) of this graph is 4,
which yields the upper bound of 5 on the maximum clique size. The clique detectedby our heuristic is {1, 8, 23}; the graph has two maximum cliques: {19, 20, 21, 22}
and {23, 24, 25, 26}. Our algorithm removes vertices 10, 11, 12, 13 and 16, 17, 18 in theinitial pruning. Subsequently, our method will explore vertex 9 and remove it basedon the maximum neighborhood core of 3. It explores vertex 15 next and removes it
due to the neighborhood core bound. It then removes vertex 14 due to an insuﬃcientdegree. Subsequently, it ﬁnds the clique around vertex 19, then prunes all vertices

PARALLEL MAXIMUM CLIQUE ALGORITHMS
11

10

C599

12

16
1

5

2

6

9

13

15
14

17
19

3

7

21

18
22

4

8

23

20

24
25

26

Fig. 3. An example used to illustrate the workings of Algorithm 2. See discussion at the endof section 4.3.

except 1 through 8 due to core number bounds. Finally, it eliminates vertex 1 dueto the neighborhood core bound; all other vertices are then iteratively removed via
degree bounds.
4.4. Performance optimization. To keep the presentation simple, we have left
out several details on performance enhancement that we have in our implementation.
(The code is available online for interested readers.) To give an example, we use an
adjacency matrix structure for small graphs in order to facilitate constant-time edge
queries, and we use a fast procedure for neighborhood set intersection that runs intime proportional to the size of the output set.
In the overall algorithm, we identify the following elements as the most important
for attaining high performance:– ﬁnding a good initial solution via the fast heuristic clique ﬁnder,– using the smallest-to-largest ordering in the main loop; this helps ensure that neighborhoods of high degree vertices are as small as possible,– using eﬃcient data structures for all the operations and graph updates, and– aggressively using k-core bounds and coloring bounds to remove vertices early.
4.5. Parallelization. We have parallelized the search procedure in the algorithm. Our own implementation uses shared memory, but we describe the parallelization at a high level such that it could be used with a distributed memory architecture
as well. The focus of our discussion is on the general scheme and not on the particulardetails.
The parallel constructs we use are a worker task-queue and a global broadcast
channel. In fact, the basic algorithm remains the same. We compute the majority ofthe preprocessing work serially on a single processor with the exception of a parallel
search for the clique in the initial heuristic step. Here, we assume that each worker hasa copy of the graph, and we distribute vertices to workers to ﬁnd the largest heuristic
clique in the neighborhood. In serial, we reduce the graph in light of the bounds andthen redistribute a copy of the graph to all workers. At this point, we view the main

C600

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

while-loop as a task generator and farm the current vertex out to a worker to ﬁnd thelargest clique in that neighborhood. Workers cooperate by communicating improved
bounds between each other whenever they ﬁnd a clique and whenever they remove a
vertex from the graph using the shared broadcast channel. When a worker receives an
updated bound, we have found that it is often possible for that worker to terminate its
own search at once. Unlike most previous algorithms, the speedup from our parallel
maximum clique algorithms can be superlinear since we are less dependent on the
precise order of vertices explored. In our own shared memory implementation, we
avoid some of the communications by using global arrays and locked updates.
5. Performance evaluation. As demonstrated in Table 1 and Figure 1, ourclique ﬁnder runs fast on social and information networks, and it exhibits roughly
linear runtime scaling as the problem size is increased. We used a two-processor Intel
E5-2670 system with 16 cores and 256 GB of memory for those tests and the additional
tests presented in this section. None of the experiments came close to using all thememory. In this section we look at four additional questions regarding performance:(a) How does the runtime of our algorithm break down into time spent in theinitial heuristic and time used by the rest of the algorithm?
(b) How scalable is our parallel algorithm?
(c) How does our method compare to other clique ﬁnders on social and information networks?
(d) Is the tighter upper bound that results from using neighborhood cores (asopposed to cores in the original graph) worth the additional eﬀort?
In what follows, we will refer to the new algorithm that we propose here (outlinedin Algorithms 1 and 2) as “pmc” (short for parallel maximum clique). For detailed
performance analysis purposes we will consider several variants of pmc.
5.1. Dataset. For the results reported in this section, we additionally use problems from the DIMACS Clique Challenge [61]. We do so in order to evaluate theperformance of our clique ﬁnder on an established benchmark of diﬃcult problems.
These problems represent particularly hard instances; some of them remain unsolvable in reasonable time by the best, tailor-designed, state-of-the-art maximum cliquealgorithms. Detailed data on the properties of these graphs is given in Tables 7 and 8
in the appendix. We restate here a few of the more general features. These graphs are
all small, ranging between 45 to 1500 vertices. They contain, however, an enormous
number of edges and triangles in comparison with the social and information networks.
The number of triangles ranges between 34 thousand and 520 million. We divide the63 graphs in the collection that our method was able to solve into an “easy” set of 27graphs (where our algorithm ﬁnds a solution in less than a second) and a “hard ” setof 31 graphs (where the solution time could vary from a second to an hour). Tables 7
and 8 are grouped according to these two categories.
5.2. Runtime breakdown (question (a)). As mentioned earlier, our maximum clique algorithm (Algorithm 2) begins by computing core numbers of vertices
and subsequently invoking a fast heuristic clique ﬁnding step (Algorithm 1). With
the help of the core numbers, the solution obtained by the heuristic step (clique H) isused to prune out portions of the input graph that cannot result in a larger clique (line
4 of Algorithm 2). If the remaining graph is empty, it means the heuristic solution is
optimal and the algorithm would terminate immediately, returning H as the solution.
In that case, the runtime of the overall algorithm would simply be the runtime of theheuristic. In the other direction, the heuristic solution may still be optimal while the

C601

PARALLEL MAXIMUM CLIQUE ALGORITHMS

10 0

1. bio2. collab

heuristic time
total time

3. inter

10 -2

4. retweet
5. tech
6. web10-4

7. facebook
8. social
9. dm-easy

10 -6

10. dm-hard

1 2 34 5 6

7

8

9

10

Fig. 4. The ratio of time taken by the heuristic step to the total time for all graphs whereclique-ﬁnding took more than 0.01 seconds; note that dm-easy and dm-hard are the DIMACS “easy”
and “hard” sets listed in Tables 7 and 8 in the appendix.

20
8

15

6

SpeedupSpeedup7

soc−orkut (290)soc−flickr (22)socfb−Texas (2.3)

5
4
3

10

brock400−4 (331)san200−0−9−2 (1)san400−0−7−1 (0.2)
brock800−4 (3604)
brock400−3 (619)p−hat1500−1 (4)san1000 (1)

5

2
1
0
0 1

4

8

Processors

12

16

0
0 1

4

8

12

16

Processors

Fig. 5. Speedup of our parallel maximum clique algorithm on social and information networks(left) and DIMACS graphs (right). Single processor runtimes in seconds are shown in parentheses.

remaining graph is nonempty, in which case the algorithm would continue to run only
to report that same solution eventually. Tables 4 through 7 in the appendix list theruntimes of just the heuristic (tω̃ ) and of the overall algorithm (tω ) for all of the graphs
in the testbed. It can be seen that, for a vast majority of the social and information
networks, the runtimes tω and tω̃ are within an order of magnitude, while for someof the DIMACS graphs the ratio tω̃ /tω can be many orders of magnitude. Figure 4
provides a pictorial summary: it shows a plot of the ratio just mentioned for the test
graphs in the diﬀerent categories with nontrivial runtimes of over 0.01 seconds.
5.3. Parallel speedup (question (b)). On the left in Figure 5 we show the
speedup obtained, as more processors are employed, by our pmc method for threesocial networks. On the right in the same ﬁgure we show speedup results of pmc
for seven of the DIMACS graphs. The runtime for both includes all the serialized
preprocessing work, such as computing the core numbers initially. The ﬁgures show
two diﬀerent behaviors. For social networks, we only get mild speedups on 16-cores,
the best result being for the largest problem soc-orkut. For the DIMACS graphs, on
the other hand, we observe roughly linear and, sometimes, superlinear speedup as weC602

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

1

P(r ≤ τ)

0.8

0.6

0.4
pmc
pmc (no neigh cores)
pmc (native ordering)
FMC
MaxCliqueDyn
BK

0.2

0
0

5

τ

10

15

Fig. 6. Performance proﬁle plots comparing a serial version of pmc and its variants against
three existing maximum clique algorithms on 30 social and information networks.

increase the number of processes. The superlinear speedup is due to fast returns from
unfruitful branches as a result of the parallel exploration of the search space. These
results indicate that our parallelization strategy is promising and helps reduce theruntime for diﬃcult problems. In future work, we plan to investigate the performanceof the same strategy on implementations for distributed-memory and other emerging
architectures.
5.4. Performance profile plots. To help address the two remaining questions,(c) and (d), we use performance proﬁle plots to compare algorithms [19]. Performance
proﬁle plots compare the performance of multiple algorithms on a set of problems (testset). The essential underlying idea is the use of a cumulative distribution function fora performance metric (in our case runtime), instead of, for example, taking averages
or sum-totals over all the test cases. Performance proﬁle plots are similar to ROC
curves in that the best results are curves that lie towards the upper left. For a quick
intuition, suppose we have N problems (test cases) in total and that an algorithm
solves M of them within 4 times the speed of the best solver for each problem. Thenwe would have a point (τ, r) = (log2 4, M/N ) in the plot. Note that the horizontal axes
reﬂects a speed diﬀerence factor of 2τ . The fraction of problems that an algorithm
solves successfully is given by the left-most highest point on the curve. In Figure 6,
for instance, the method labeled BK solves only around 80% of the problems in thetest set, and it does so at a factor of 210 times the runtime of the fastest algorithm inthe set (pmc).
5.5. Comparison with other methods on social networks (question (c)).
The test we conduct here begins with a “self-comparison.” In particular, we consider
several variants of pmc in order to assess the eﬀects of the various components on
the method’s performance. We then compare these variants against a set of existing
methods. The variants of pmc that we consider are a serial version with neighborhoodcores exploited (pmc), the same version but without exploiting neighborhood cores(pmc no neigh cores), and a version that uses only the k-core pruning steps andsearches vertices in their native order, the order in which they were read from disk,

PARALLEL MAXIMUM CLIQUE ALGORITHMS(a) DIMACS-hard (serial).

C603(b) DIMACS-hard (16 threads).

Fig. 7. Performance proﬁle plots comparing two versions of pmc (with and without neighborhood cores) on DIMACS-hard graphs. Left: Comparison of serial versions of the two variants.
Right: A similar comparison of the parallel versions.

rather than degeneracy order (pmc native ordering).
We compare these three variants of pmc against each other and against threestate-of-the-art maximum clique ﬁnders: the recent method FMC (for fast maximum
clique) from [48]; the method MaxCliqueDyn [35], which dynamically adapts a greedy
color sort; and a recent implementation of the Bron–Kerbosch (BK) algorithm in
the igraph package [18]. Our algorithm pmc diﬀers from FMC in several importantways. Among others, the initial pruning (via the initial heuristic step) and the latercore-based pruning strategies are new, and the implementation is completely diﬀerent.
Figure 6 shows the results of the comparisons on a set of 30 social and information
networks.
From the performance proﬁle plots in Figure 6 for these types of networks, we ﬁndlittle diﬀerence between using and not using the neighborhood cores within our own
framework, and a somewhat more pronounced diﬀerence between using degeneracy
ordering versus native ordering. Relative to the alternative algorithms in the comparison, we see that the most optimized version of the method proposed here (pmc) oﬀers
a dramatic performance improvement. Compared to the BK algorithm, pmc is over1000 times faster for some problems and solves all of the instances. Compared to the
FMC algorithm, pmc is about 50 times faster. This illustrates that our algorithm uses
properties of the social and information networks to quickly hone in on the largest
clique.
5.6. Assessment of using neighborhood cores (question (d)). We alreadysaw from the tests discussed in the previous subsections that using neighborhood coresin our maximum clique algorithm makes little diﬀerence for social and information
networks. How about for the DIMACS (and similarly-structured) graphs? The plots
in Figures 7(a) and 7(b) show results on the 30 hard instances of the DIMACS problems for a test assessing the impact of using or not using neighborhood cores. The
plots show results for two cases: pmc run in serial (a) and pmc run in parallel on 16
threads (b). It can be seen that, in the serial case, the neighborhood cores greatly
help reduce the work in the majority of cases. In a few cases, not using them entailsa large increase in work (the point furthest to the right in the serial ﬁgure). All of
the work involved in computing these cores is parallelized, and we observe that, inparallel, using them is never any worse than about 20.5 ≈ 144% the speed of theC604

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

A

0,1,3
0,1
1,2,3
0,1,2,3

0,2,3 1

D

0

C
2,3 3

0,1,2 0,1,3

B

0,1,2 1,2,3 0,1,2,3
0,3

F

0
0,1,2,3

E

Fig. 8. An example, adopted from [3], illustrating a temporal network. The reader can verify
that there exist temporal paths from node A to all other nodes, from B to all other nodes, from C to
all other nodes, from D to all nodes but F, from E to all nodes but F, and from F to all other nodes.

fastest method.
5.7. Summary of performance results. In summary, we observe that (i) the
overall runtime of our algorithm is of the same order of magnitude as the time spentin the initial heuristic for social and information networks and easy DIMACS graphs,
whereas the variation is more signiﬁcance for the denser DIMACS graphs; (ii) our parallelization strategy is eﬀective; (iii) our algorithm outperforms existing algorithms
dramatically; and (iv) neighborhood core bounds are of great help for solving challenging problems. We recommend using neighborhood cores, as they help the algorithm
terminate faster with challenging problems and almost never take more than twice
the time for easy ones.
6. Applications. Although the maximum clique problem is generally NP-hard,
as we saw in previous sections, our procedure runs in nearly linear time on many realworld networks. This makes it plausible for the procedure to be used as a part in a fast
method for another, encompassing real-world problem, opening up an opportunity forpotentially great impact. In this section, we illustrate this potential by using our
method as a subroutine in algorithms for two applied problems: ﬁnding the largest
temporal strong component in a dynamic network and ﬁnding a compression-friendly
order of the nodes of a network.
6.1. Temporal strong components. Temporal strong components were recently proposed by Bhadra and Ferreira [3] and Nicosia et al. [42] to extend the ideaof a strong component in a (static) network to a temporal (dynamic) network. Let
V be a set of vertices, and ET ⊆ V × V × R+ be the set of temporal edges between
vertices in V . Each edge (u, v, t) has a unique time t ∈ R+ . For such a temporal
network, a path represents a sequence of edges that must be traversed in increasingorder of edge times. That is, if each edge represents a contact between two entities,
then a path is a feasible route for information. See Figure 8 for an illustration.
Temporal paths are inherently asymmetric because of the directionality of time.
Two vertices (u, w) are strongly connected if there exists a temporal path P from u
to w and from w to u. A temporal strongly connected component (temporal SCC)
is deﬁned as a maximal set of vertices C ⊆ V such that any pair of vertices inPARALLEL MAXIMUM CLIQUE ALGORITHMS

C605

C is strongly connected. Note that this is exactly the same deﬁnition as a strong
component in a graph where we replaced the notion of a path with a temporal path.
In the example in Figure 8, the set {A, B, C, D, E} forms a temporal SCC.
As previously mentioned, checking whether a graph has a k-node temporal SCC is
NP-complete [3, 42]. Nonetheless, we can compute the largest such strong component
using a maximum clique algorithm. Let us brieﬂy explain how (see Algorithm 3 foran outline). The ﬁrst step is to transform the temporal graph into what is calleda strong-reachability graph. For each pair of vertices in V , we place an edge in thestrong-reachability graph if there is a temporal path between them. This is easy to do
by using a method developed by [46]. With this reachability graph, the second stepof the computation is to remove any nonreciprocated edges and then ﬁnd a maximum
clique. That maximum clique is the largest set of nodes where all pairwise temporalpaths exist and ,hence, is the largest temporal strong component [42]. Note that theremoval of nonreciprocated edges can result in some vertices being singletons, which
are in turn removed prior to the computation of the temporal SCC. Thus the vertex
set VR in the reachability graph could be a strict subset of the vertex set V in thetemporal graph.
Algorithm 3. Largest temporal strong component.
Input: Temporal graph G = (V, ET )1 procedure max-tscc(G = (V, ET ))2
ER = reach(G).
3Remove nonreciprocal edges from ER .
4
Obtain VR by discarding singleton vertices from V.
5Compute the max-clique C in the reachability graph (VR , ER ).
procedure reach(G = (V, ET ))Sort edges to be in reverse time order.
8
Set ER to be the set of all self-loops.
9
for (i, j, t) ∈ ET do
10
Add (i, k) to ER for all k, where (j, k) ∈ ER .
11
Return ER
6
7

Dataset.
We study three types of temporal networks. In each, the nodes
represent people.
1. Contact networks: The edges here represent face-to-face contacts in a social
experiment designed to simulate epidemic spreading of a contagious agent (infectdublin, infect-hyper [30]). See [57] for more details about these data.
2. Interaction networks: The edges represent private Facebook messages (fbmessages [43]) or cellular telephone calls in data gathered at the Reality Mining
project at MIT (reality [22]).
3. Retweet networks: The edges here are retweets. We analyzed a network ofpolitical retweets centered around the November, 2010 election in the US (retweetelect [16]), and a similar network of retweets about a UN conference held in Copenhagen (retweet-copen [1]). The latter data was collected over a two-week period.
Results and analysis. Figure 9 shows the reachability and largest temporalstrong component for the retweet-elect and reality networks. It took the maximum clique ﬁnder less than a second to identify these components. We summarize
the remaining experiments on the temporal strong components in Table 2. For all ofthese networks, we were able to identify the largest temporal strong component in less

C606

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN(a) Reachability (retweet-elect).

(c) Reachability (reality).

(b) Temporal SCC (retweet-elect).

(d) Temporal SCC (reality).

Fig. 9. Results on computation of temporal SCCs in the retweet-elect and reality networks.
In order to compute the largest temporal SCC, we ﬁrst compute the strong reachability network (a),(c). These networks are rather dense and often reveal clear community structure. In the retweetelect network, we see clear communities for the political left and right. We ﬁnd that the largest
temporal SCC in retweet-elect (b) consists of 166 Twitter users classiﬁed as politically “right”
according to the original data with only a single exception. In the largest temporal SCC in thereality network (d), we see a small group of core users maintaining connectivity among various
groups.

than a second after we computed the reachability network. There are two reasons forthis performance. First, in all of the networks except for the interaction networks, thelargest clique is the set of vertices with highest core numbers. Second, our heuristic
computes the largest clique in all of these networks, and we are able to quickly reduce
the remaining search space when it isn’t the largest k-core as well.
Observations. We observe several interesting properties in these temporal strong
components. In the two contact networks (infect-hyper and infect-dublin), bothof the largest strong components had about 100 vertices, despite the drastically different sizes of the initial datasets. We suspect that this is a consequence of the data

C607

PARALLEL MAXIMUM CLIQUE ALGORITHMS

Table 2For each temporal network, we list the number of temporal edges, the number of vertices andedges in the reachability graph, the size ω of the temporal strong component, and the runtime of our
maximum clique algorithm.
Graph

|ET |

|VR |

|ER |

ω

Time (s)infect-dublin
infect-hyper

415K
20K

11K
113

176K
6.2K

84
106

<.01
<.01

fb-messages
reality

61K
52K

1.9K
6.8K

532K
4.7M

707
1236

0.05
0.19

retweet-electretweet-copen

61K
45K

18K
8.6K

66K
474K

166
581

0.02
0.22

collection methodology since the infect-dublin data were collected over months
whereas the infect-hyper data were collected over days. In the interaction networks,
the components contain a signiﬁcant fraction of the total vertices, roughly 20–30%.
In the retweet networks, the components are a much smaller fraction of the vertices.
Given the strong communication pattern between the groups, the components aregood candidates for centers of communities in the networks.
Together these results show that temporal strong components are a strict requirement on a group of nodes in a network. For instance, there is a considerable diﬀerencein the size of temporal strong components between networks with asymmetry in therelations (retweet-elect) compared with networks with symmetric relationships(fb-messages and reality). This ﬁnding may be important for those interested indesigning seeded viral campaigns on these networks.
6.2. Ordering for network compression. In this application, we consider
using the maximum cliques of a network to produce an ordering of the vertices thatshould be useful for compression, reducing the space needed to store the network
structure. Compression has two important beneﬁts. First, it reduces the amount of
IO traﬃc involved in using the graph. Second, good compression schemes may reduce
the amount of work involved in running an algorithm on the graph [33, 32]. Stateof-the-art network compression techniques heavily exploit locality of links within theadjacency list representation of a graph to reduce the number of bits required tostore each edge [6, 7, 5]. Cliques are the densest local feature of a graph, and in thisapplication, we order the vertices of a network such that every vertex is in a large
clique. This ensures that there are many local edges within the graph. We thenevaluate how well the bvgraph [6, 7] compression method reduces the graph size using
this ordering.
The speciﬁc ordering we use is the result of the following process. Given a graphG, we ﬁnd a maximum clique C in G, remove C from G, and repeat the process untilall vertices are removed. To improve the runtime, we run our heuristic method to
ﬁnd large cliques. We then order the vertices according to the cliques, C1 , C2 , . . . , CI ,where I denotes the number of iterations needed. Internally within each Ci we orderthe vertices by their degrees. We then permute the graph to use this ordering, and use
the bvgraph compression scheme with all default settings to compress the networks.
Table 3 shows the results that we get on two Facebook networks (and Figure 10 illustrates the application of the clique-based reordering of the columns of the adjacency
matrix of a portion of the fb-Penn network). We compare the compression obtainedby reporting the size of each graph in bytes after compressing. We evaluate threeC608

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

Table 3Size in bytes required to store two Facebook graphs using the bvgraph compression scheme inthree diﬀerent orders.

Vertices

Edges

NativeLLP

PMC

fb-Pennfb-Texas

42K
36K

1.4M
1.6M

423750746054272740801
3232909

3104286
3508224

0

0

100

100

200

200

vertices

vertices

Graph

300

400

500
0

300

400

100

200
300
vertices(a) Before.

400

500

500
0

100

200
300
vertices

400500(b) After.

Fig. 10. Plots of the nonzero entries of the adjacency matrix of a graph before and after theclique-based ordering of the columns is applied.

orderings of the vertices: the native order, the layered label propagation (LLP) order proposed to help improve compression with the bvgraph algorithm [5], and our
clique-based order computed using pmc. We ﬁnd that our ordering results in better compression than using the native ordering of the data, and it is comparable to
the LLP order although slightly worse. Previous research found that identifying andcompressing large bicliques with a linear number of edges helped to improve upon
methods that use the adjacency list [10]. Given the success of this simple ordering,
we plan to evaluate these more involved schemes in future work.
7. Conclusions. We presented a new fast algorithm that ﬁnds the maximum
clique on billion-edge social networks in minutes. The algorithm exhibits linear runtime scaling over graphs from a thousand vertices to a hundred million vertices andhas good parallelization potential. We applied the algorithm to compute the largest
temporal strong components of a dynamic network, which involves ﬁnding the largest
clique in a static reachability graph, and to obtain an ordering friendly for graph compression. Our hope is that maximum clique will become a standard network analysis
measure. Towards that end, we make our software package and related information
available online for others to use: the original codes used to generate the results for thispaper can be found at http://www.cs.purdue.edu/∼dgleich/codes/maxcliques, and an
updated repository is available at https://github.com/ryanrossi/pmc.
Appendix. Dataset properties. The tables in this section summarize thenumerical properties of the datasets used in the analysis in this paper. Those headers
not previously deﬁned include the mean clustering coeﬃcient κ and the maximum
number of triangles incident on a vertex Tmax (and the average Tavg ).

|E|1087562
195702796
761
1112702

roadNetPA
roadNetCA

retweettwittercopen
retweetcrawl

117
1029
227885215415142760388

623
2196
2765
5451
6451
7680
54397
180811360767

143
113
410
1133
1266
6809
32430
33696
92117

enrononly
infecthyper
infectdublin
emailuniv
fbmessages
realityemailEU
enronlarge
wikiTalk

1188
1948
2025
25569
914
13422
91286
117619196972716460814134820644
1049866
56306653

diseasomeyeastcelegans
dmela

netscience
379
GrQc
4158
CondMat
21363
HepPh
11204
AstroPh17903
dblp2010
226413
citeseer
227320
MathSciNet
332689dblp2012
317080hollywood2009 1069126

|V |

516
1458
453
7393

Graph

36
447
525939201336361476

2667
50601
21342
16029
7473
1200
1469762175933
2509401

2763
14333751315310073670
405004247939378139894
1730334
667315514748661845

4080
618
9852
8697

|T |
4
2
8
6

davg

17
37
5070

9
12

42
98
50
71
112
261
623
1383
1220

2
2
4

2
2

8
38
13
9
10
2
3
10
7

34
4
81
6
279
8
491
20
504
22
238
6
1372 7496
4343
611467 105

50
56
237
190

Δ

0.07
0.06
0

0.06
0.06

0.36
0.5
0.44
0.17
0.04
0
0.03
0.09
0.05

0.43
0.63
0.26
0.66
0.32
0.38
0.46
0.14
0.31
0.31

0.43
0.05
0.12
0.01

κ

6
27
1555

8
7

125
1731
280
261
242
52
1615
17744
17699

75
1179
1615
39633
11269
5947
5398
1564
8345
3977656

152
18
870
225

Tmax

0.4
0.6
0.5

0.2
0.2

18.7
447.8
52.1
14.1
5.9
0.2
4.5
64.6
27.2

7.3
34.5
24
899.1
226.2
21.2
35.8
5.2
21
13795.1

7.9
0.4
21.7
1.2

Tavg

4
5
19

4
4

10
29
18
12
12
6
23
44
59

9
44
26
239
57
75
87
25
114
2209

11
6
11
12

K
0.01
0.01
0.01
0.06

4
4
13

3
4

8
15
16
12
5
5
12
20
15

0.01
0.01
0.58

0.5
0.25

0.01
0.01
0.01
0.01
0.01
0.05
0.02
0.03
0.09

0.01
0.01
0.01
0.01

tω̃ (sec)

4
4
13

3
4

8
15
16
12
5
5
12
20
14

0.01
0.01
0.23

0.21
0.25

0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.02

9
0.01
44
0.01
26
0.01
239 0.01
57
0.01
75
0.05
87
0.06
25
0.08
114 0.05
2209 1.69

11
6
9
7

tω (sec) ω̃

9
0.01
44
0.01
26
0.01
239 0.01
57
0.01
75
0.05
87
0.06
25
0.08
114 0.05
2209 1.69

11
6
9
7

ω

Table 4
Biological, collaboration, interaction, road, and retweet networks. Here and in all subsequent tables, |V | is the number of vertices, |E| the number of edges,|T | the number of triangles, Δ the maximum degree, davg the average degree, κ the mean clustering coeﬃcient, Tmax the maximum number of triangles incident
on a vertex, Tavg the average number of triangles incident on a vertex, K the core number of the graph, ω the size of maximum clique, tω the runtime of ourexact maximum clique algorithm, ω̃ the size of the approximate maximum clique computed by our heuristic, and tω̃ the runtime of our heuristic maximum cliquealgorithm.

PARALLEL MAXIMUM CLIQUE ALGORITHMS

C609

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

C610

|V |
6632
56943
85123
14787860761011094209|E|
31212
2347482
1898406072
136441286309526

|T |

102
6
443
7
1134 72507 10626
314730 925409 728754 54369 122651 1327466 705214 55109
61079 153370 495
41071 635455 13

Δ

0.13
0.09
0.11
0.03
0
0.02
0.01
0.01
0.15
0.14
0.04
0.02

0.23
0.31
0.01
0
0.06
0.01

κ

251
5151
11517
13382
1687
93817
151081
18082052452579740
1313133
158150

588
22271
8513
17
6044
564609

Tmax

7.2
18
26.1
17.2
0.2
34.7
14.8
8.1
343
62.1
525.1
190.8

14.8
314
4.7
0.1
7.1
50.9

Tavg

10
33
53
54
29
52
50
52
310
214
231
304

16
89
24
7
33
112

K

7
0.01
16 0.02
37 0.05
26 0.06
60.23
29 0.2
16 0.55
17 0.84
58 5.2214 2.98
47 48.49
129 1205.47

16
58
16
4
17
67

ω

0.01
0.09
0.05
0.05
0.13
1.2

7
0.01
16 0.01
37 0.01
25 0.02
6
0.05
29 0.05
14 0.18
16 0.2745 0.22214 2.98
44 14.39
129 548.04

16
55
16
4
17
66

tω (sec) ω̃Table 5
Technological and social networks.
Graph
2113
7476
40164
62561
19091416946166357
4791001483224120564388617
681941473316589169158
176313864
250658109
1573931856
12521172426

0.01
0.01
0.01
0.01
0.05
0.67

tω̃ (sec)routersrf
WHOIS
internetas
p2pgnutella
RLcaidaasskitter
2914
100120212945358647713319950327
19367482987624319045227933062
106349209
1806067135

davg

wikiVote889
epinions
26588
brightkite
56739
slashdot
70068
twitterfollow 404719
gowalla196591
youtube495957
youtubesnap 1134890
ﬂickr
513969
livejournal4033137
orkut
2997166
friendster
65608366

6621
6402
14917
9885
11586
17206
20453
63392
23831
22900
30795
29732
41536
35111
36364
2937612309716558790782

CMU
MIT
UCSB37Duke14
Stanford3
UConn
UCLA
OR
Wisconsin87
Berkeley13
UIllinois
IndianaPenn94
UF
Texas84
Banon
Aanon
uciunipolblogs
643
google
1299
edu
3031
BerkStan
12305
webbase2001 16062
spam
4767
indochina2004 11358
sk2005121422arabic2005
163598
wikipedia2009 1864433
it2004509338uk2005129632

|V |

Graph

2280
2773
6474
19500
25593
37375
47606
33441917472694507315717841311744049

24995925123048221550643756830960486774760481688683594685241912644211305757
13622201465654
1590651
20959854
23667394
92208195

|E|

9012
15204
30174
30915
63345
3870516302342980263
65011059
6653808
1016652636
2513657160

6930159
7111758
922997115427674
17507610
10252326
15339651
10504602
14586621
16108779
28052775
28173249
21623388
36440373
33535656
155972349
166819284
19126557

|T |
davg

165 7
59
4
104 4
59
3
1679 3477 15199 8590 51102 212624 4469 28850 181840 75708 78810 641887 102
1172 981709 70
1180 73
1098 253484 703434 744632 821358 874410 658246 83
6312 874356 144915 154960 3

Δ

0.16
0.53
0.27
0.28
0.02
0.15
0.57
0.47
0.95
0.05
0.95
1

0.19
0.18
0.16
0.17
0.16
0.13
0.14
0.15
0.12
0.11
0.14
0.14
0.1
0.12
0.1
0.05
0.05
0

κ

392
189
523
384
1362
6273
1475
3481
5884
12404
93368
124251

24065
27788
16140
41982
33177
21515
17534
19467
46791
69511
66178
37292
68097
159087141050
36861
50241
7781

Tmax

Table 6
Facebook and Web networks.

14
11.7
10
2.5
3.9
81.2
55.5
24.5
397.4
3.6
1996
19390.7

1046.71110.9618.8
1560.71511.1
595.9
750
165.7
612.1
703.4
911
947.6
520.6
1037.9
922.2
53.1
53.9
0.3

Tavg

13
18
30
29
33
36
50
82
102
67
432
500

70
73
66
86
92
66
66
53
61
65
86
77
63
84
82
64
75
17

K
0.09
0.1
0.03
0.19
0.09
0.07
0.1
0.09
0.17
0.16
0.18
0.21
0.24
0.28
0.33
5.52
6.3
33.86

0.01
0.01
0.01
0.02
0.02
0.02
0.03
0.03
0.04
0.04
0.05
0.06
0.06
0.07
0.08
2.1
2.56
18.49

tω̃ (sec)

90.01
18 0.01
30 0.01
29 0.01
33 0.01
20 0.01
50 0.01
82 0.02102 0.03
31 0.69
432 0.12500 0.06

45
32
52
32
51
49
49
29
36
42
56
46
43
51
49
23
23
6

tω (sec) ω̃

90.01
18 0.01
30 0.01
29 0.01
33 0.01
20 0.04
50 0.01
82 0.02102 0.03
31 1.16432 0.12500 0.06

45
33
53
34
51
50
51
30
37
42
57
48
44
55
51
24
25
6

ω

PARALLEL MAXIMUM CLIQUE ALGORITHMS

C611

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

C612

DSJC500-5

Graph

45

500

|V |

1534
3235
4459
8473
9139
23191
46627

9876
12048
13089

918

62624

|E|

2874231

16230
76758
55704
546252247008163996266967444796888733871120308

33732

7856550

|T |

22
22
57
57
163 163247 247
1013 1013

190

17
34
20
86
38
95
188

114
134
147

41

286

Δ

179

15
32
17
84
36
92
186

98
120
130

40

250

davg

0.19
0.9
0.6
0.97
0.99

0.9

0.73
0.76
0.74
0.77
0.76
0.77
0.77

0.49
0.61
0.66

0.92

0.5

κ

45
1440
7875
29421
507558

16144

100
429
141
2814
534
3441
13609

3163
5404
7031

757

20527

Tmax

45
1440
7875
29421
50755814371.2

81.2
383.8
111.4
2731.3494
3279.913393.5

2398.44366.95601.5

749.6

15713.1

Tavg

103

16
54
92

23
58
164
248
1014

167

15
33
18
84
36
93
186

85
106
118

41

226

K

11

4
14
8

4
0.01
32 0.01
16 0.02
128 0.01
512 0.36

55

12 0.01
24 0.01
14 0.01
58 0.01
26 0.03
64 0.02
126 0.05

12
15
17

16

13

ω

0.01

0.01
0.01
0.04

0.01

0.3

11

4
14
8

12 0.01
24 0.01
14 0.01
58 0.01
26 0.01
64 0.01
126 0.03

9
12
14

16

12

tω (sec) ω̃

0.01

0.01
0.01
0.01

0.01

0.01

Table 7
DIMACS “easy” graphs.

MANN-a9
200
200
200

17910

2880
92160
2016000
7531776
519739392

3799.9

45
1026
3003

0.03

15
17
13
46
8

0.01
0.01
0.02
0.01
0.01

4
0.01
32 0.01
16 0.01
128 0.01
512 0.19

0.01

0.01
0.01
0.01

tω̃ (sec)

brock200-2
brock200-3
brock200-4
200
200
500
200
500
500
500

704
1824
20864
31616
518656

4770

45
1026
3003

0.01
0.01
0.02

gen200-p0-9-55 200

c-fat200-1
c-fat200-2
c-fat500-1
c-fat200-5
c-fat500-2
c-fat500-5
c-fat500-10

64
64
256
256
1024

0.63

0.43
0.74
0.73

0.06
0.01
0.02
0.01
0.01

36

hamming6-4
hamming6-2
hamming8-4
hamming8-2
hamming10-2

110

15
53
91

18
30
18
70
13

124

125
126
123
163
184

15
53
91

6663.57003.77272.1
14403.613063.7

649791

8899
8577
9785
16354
15898

1260
71820
360360

0.7
0.73
0.74
0.9
0.66

9435

138
139
139
179
199

210
1855
5460

161
155
164
191
225

171

1332702
14007361454424
28807235225496

28
70
120

13868
13930
13930
17910
39900

johnson8-2-4
johnson8-4-4
johnson16-2-4

200
200
200
200
400

keller4
sanr200-0-7
san200-0-7-1
san200-0-7-2
san200-0-9-1
san400-0-5-1

225990

300
500
500
700
1000
1000
1500

200
200
200
400
400
400
400
400
400
1000

p-hat300-3
p-hat500-2
p-hat500-3
p-hat700-2
p-hat1000-1
p-hat1000-2
p-hat1500-1

sanr200-0-9
san200-0-9-2
san200-0-9-3
sanr400-0-5
san400-0-7-1
san400-0-7-2
san400-0-7-3
sanr400-0-7
san400-0-9-1
san1000

17863
17910
17910
39984
55860
55860
55860
55869
71820
250500

33390
62946
93800
121728122253244799284923

17910

14834
59681
59723
59765
59786
207333207505207643208166776

brock200-1
brock400-3
brock400-1
brock400-4
brock400-2
brock800-3
brock800-1
brock800-4
brock800-2

70551
533115249826keller5

200
400
400
400
400
800
800
800
800

MANN-a27
MANN-a45|E|

gen200-p0-9-44 200

1000

378
1035

DSJC1000-5

|V |

Graph

285028828737122871009399634211388942
11280099
11171766
10901049
23169036
86356584

56646219957924
27160053
26656629
921641773970454
34315488

98043630

2874090

1631100
13281468
13311033
13337715
13350273
69627666
69786183
69940425
70468920

26008398
546656220

62378964

|T |
499

davg

189
188
187
233
301
304
307
310
374
550

267
389
452
539
408
766
614

638

190

165
322
320
326
328
558
560
565
566

178
179
179
199
279
279
279
279
359
501

222
251
375
347
244
489
379

582

179

148
298
298
298
298
518
518
519
520

374 3731031 1030

551

Δ

0.9
0.9
0.9
0.5
0.73
0.73
0.72
0.7
0.9
0.69

0.76
0.58
0.77
0.58
0.28
0.57
0.29

0.75

0.9

0.75
0.75
0.75
0.75
0.75
0.65
0.65
0.65
0.65

0.99
1

0.5

κ

15942
15819
15645
13587
32312
32886
33668
33547
62776
100736

26733
40865
77235
79243
22689
15760453239

151289

16160

10123
38587
38113
39654
40148
10080310148510327710401669067
529012

75982

Tmax

Table 8
DIMACS “hard” graphs.

14251.4
14368.6
14355
9990.928472.428200.2
27929.427252.6
57922.686356.6

18882.1
19915.854320.138080.99216.473970.5
22877

12634514370.58155.533203.7
33277.633344.3
33375.787034.6
87232.7
87425.5
88086.168805.3
528170

62379

Tavg

167
170
170
178
262
260
254
259
345
465

181
171
304
236
164
328
253

561

168

135
279
278
278
279
484
488
486
487

365
1013

460

K
22.4

35

16
20
19
20
21
17
17
17
17

0.68
0.12
41.07
0.77
0.06
40.65
0.33

36
40
33
11
31
17
16
18
58
9

27
25
38
36
9
35
10

3362.05 23

0.71

0.14
78.18
105.82
11.91
35.2
517.39785.4
251.93583.4242 16.08
60 0.01
44 1.29
13 0.07
40 0.02
30 0.04
22 0.58
21 22.9
100 0.31
15 0.07

36
36
50
44
10
46
12

27

44

21
31
27
33
29
25
23
26
24

0.01

tω̃ (sec)

0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01

0.01
0.01
0.01
0.01
0.01
0.01
0.01

0.01

0.01

0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01

125 0.01
340 0.1313tω (sec) ω̃

126 0.44
345 189.49

15

ω

PARALLEL MAXIMUM CLIQUE ALGORITHMS

C613

C614

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN

Acknowledgments. We are grateful to the anonymous referees and the associate editor for a number of suggestions that improved this paper.
REFERENCES[1] N. K. Ahmed, F. Berchmans, J. Neville, and R. Kompella, Time-based sampling of social
network activity graphs, in Proceedings of the Eighth Workshop on Mining and Learningwith Graphs (MLG’10), ACM, Washington, DC, 2010, pp. 1–9.
[2] V. Batagelj and M. Zaversnik, An o(m) algorithm for core decomposition of networks,
arXiv:0310049, 2003.
[3] S. Bhadra and A. Ferreira, Complexity of connected components in evolving graphs andthe computation of multicast trees in dynamic networks, in Proceedings of ADHOC-NOW
2003, Lecture Notes in Comput. Sci. 2865, Springer, New York, 2003, pp. 259–270.
[4] P. Boldi, B. Codenotti, M. Santini, and S. Vigna, UbiCrawler: A scalable fully distributed
web crawler, Softw. Pract. Exper., 34 (2004), pp. 711–726.
[5] P. Boldi, M. Rosa, M. Santini, and S. Vigna, Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks, in Proceedings of the 20th
International Conference on the World Wide Web, ACM, New York, 2011, pp. 587–596.
[6] P. Boldi and S. Vigna, The webgraph framework I: Compression techniques, in Proceedingsof the 13th International Conference on the World Wide Web, ACM, New York, 2004,
pp. 595–602.
[7] P. Boldi and S. Vigna, Codes for the world wide web, Internet Math., 2 (2005), pp. 407–429.
[8] I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo, The maximum clique problem,in Handbook of Combinatorial Optimization 4, D.-Z. Du and P. Pardalos, eds., Springer,
New York, 1999, pp. 1–74.
[9] C. Bron and J. Kerbosch, Algorithm 457: Finding all cliques of an undirected graph, Comm.
ACM, 16 (1973), pp. 575–577.
[10] G. Buehrer and K. Chellapilla, A scalable pattern mining approach to web graph compression with communities, in Proceedings of the International Conference on Web Search and
Web Data Mining (WSDM2008), ACM, New York, 2008, pp. 95–106.
[11] CAIDA, Skitter, software available from http://caida.org/tools/measurement/skitter/.
[12] M. Charikar, Greedy approximation algorithms for ﬁnding dense components in a graph, inProceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX ’00), Springer-Verlag, New York, Berlin, 2000, pp. 84–95.
[13] J. Cheng, Y. Ke, A. W-C. Fu, J. X. Yu, and L. Zhu, Finding maximal cliques in massive
networks, ACM Trans. Database Syst., 36 (2011), 21.
[14] J. Cheng, L. Zhu, Y. Ke, and S. Chu, Fast algorithms for maximal clique enumeration withlimited memory, in Proceedings of the ACM SIGKDD, 2012, pp. 1240–1248.
[15] E. Cho, S. A. Myers, and J. Leskovec, Friendship and mobility: User movement in locationbased social networks, in Proceedings of the 17th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining (KDD ’11), ACM, New York, 2011, pp. 1082–
1090.
[16] M. D. Conover, J. Ratkiewicz, M. Francisco, B. Gonçalves, A. Flammini, and
F. Menczer, Political polarization on Twitter, in Proceedings of the Fifth International
AAAI Conference on Weblogs and Social Media (ICWSM), 2011, pp. 89–96.
[17] P. G. Constantine and D. F. Gleich, Using polynomial chaos to compute the inﬂuence ofmultiple random surfers in the PageRank model, in Proceedings of the 5th Workshop on
Algorithms and Models for the Web Graph (WAW2007), A. Bonato and F. C. Graham,eds., Lecture Notes in Comput. Sci. 4863, Springer, New York, 2007, pp. 82–95.
[18] G. Csardi and T. Nepusz, The igraph software package for complex network research, InterJournal, Complex Systems, (2006), 1695; online at http://necsi.org/events/iccs6/papers/c1602a3c126ba822d0bc4293371c.pdf.
[19] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance proﬁles,Math.l Program., 91 (2002), pp. 201–213.
[20] N. Du, C. Faloutsos, B. Wang, and L. Akoglu, Large human communication networks: Patterns and a utility-driven generator, in Proceedings of the ACM SIGKDD, 2009, pp. 269–
278.
[21] N. Du, B. Wu, L. Xu, B. Wang, and P. Xin, Parallel algorithm for enumerating maximal
cliques in complex network, in Mining Complex Data, Vol. 165, Springer, New York, 2009,
pp. 207–221.
[22] N. Eagle and A. Pentland, Reality mining: Sensing complex social systems, Personal andUbiquitous Computing, 10 (2006), pp. 255–268.

PARALLEL MAXIMUM CLIQUE ALGORITHMS

C615[23] D. Eppstein, M. Löffler, and D. Strash, Listing all maximal cliques in sparse graphs innear-optimal time, Algorithms Comput., (2010), pp. 403–414.
[24] D. Eppstein and D. Strash, Listing all maximal cliques in large sparse real-world graphs,
Experiment. Alg., (2011), pp. 364–375.
[25] P. Erdös and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad.
Sci. Hungarica, 17 (1966), pp. 61–99.
[26] A. Ferreira, On models and algorithms for dynamic communication networks: The case for
evolving graphs, in Proceedings of ALGOTEL, 2002, pp. 155–161.
[27] H. J. Finck and H. Sachs, Über eine von H.S. Wilf angegebene Schranke für die chromatische
Zahl endlicher Graphen, Math. Nachr., 39 (1969), pp. 373–386.
[28] M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, Walking in Facebook: A casestudy of unbiased sampling of OSNs, in Proceedings of INFOCOM, 2010, pp. 1–9.
[29] D. F. Gleich, Graph of Flickr photo-sharing social network, in DOI: 10.4231/D39P2W550,
2012.
[30] L. Isella, J. Stehlé, A. Barrat, C. Cattuto, J. F. Pinton, and W. Van den Broeck,
What’s in a crowd? Analysis of face-to-face behavioral networks, J. Theoret. Biol., 271(2011), pp. 166–180.
[31] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A. L. Barabasi, The large-scaleorganization of metabolic networks, Nature, 407 (2000), pp. 651–654.
[32] U. Kang and C. Faloutsos, Beyond “caveman communities”: Hubs and spokes for graphcompression and mining, in Proceedings of ICDM 2011, IEEE Press, Piscataway, NJ, 2011,
pp. 300–309.
[33] C. Karande, K. Chellapilla, and R. Andersen, Speeding up algorithms on compressed web
graphs, in Proceedings of the Second ACM International Conference on Web Search andData Mining (WSDM ’09), ACM, New York, 2009, pp. 272–281.
[34] S. Khot, Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring, in Proceedings of the 42nd IEEE Symposium on Foundations ofComputer Science, 2001, pp. 600–609.
[35] J. Konc and D. Janezic, An improved branch and bound algorithm for the maximum clique
problem, Proteins, 4 (2007), p. 5.
[36] G. Kortsarz and D. Peleg, Generating sparse 2-spanners, J. Alg., 17 (1994), pp. 222–236.
[37] H. Kwak, C. Lee, H. Park, and S. Moon, What is Twitter, a social network or a news media?,in Proceedings of the 19th International Conference on the World Wide Web, ACM, New
York, 2010, pp. 591–600.
[38] J. Leskovec, D. Huttenlocher, and J. Kleinberg, Predicting positive and negative links inonline social networks, in Proceedings of the 19th International Conference on the World
Wide Web, ACM, New York, 2010, pp. 641–650.
[39] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, Community structure in large
networks: Natural cluster sizes and the absence of large well-deﬁned clusters, Internet.
Math., 6 (2009), pp. 29–123.
[40] D. W. Matula, A max-min theorem for graphs with application to graph coloring, SIAM Rev.,
10 (1968), pp. 481–482.
[41] C. McCreesh and P. Prosser, Multi-threading a state-of-the-art maximum clique algorithm,
Algorithms, 6 (2013), pp. 618–635.
[42] V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, and V. Latora, Components
in time-varying graphs, Chaos, 22 (2012), 023101.
[43] T. Opsahl and P. Panzarasa, Clustering in weighted networks, Social Networks, 31 (2009),
pp. 155–163.
¨[44] P. R. J. Ostergård, A fast algorithm for the maximum clique problem, Disc. Appl. Math.,
120 (2002), pp. 197–207.
[45] G. Palla, I. J. Farkas, P. Pollner, I. Derényi, and T. Vicsek, Fundamental statisticalfeatures and self-similar properties of tagged networks, New J. Phys., 10 (2008), 123026.
[46] R. K. Pan and J. Saramäki, Path lengths, correlations, and centrality in temporal networks,
Phys. Rev. E, 84 (2011), 016105.
[47] P. M. Pardalos and J. Xue, The maximum clique problem, J. Global Opt., 4 (1994), pp. 301–
328.
[48] B. Pattabiraman, Md. Mostofa Ali Patwary, A. H. Gebremedhin, W.-K. Liao, and
A. Choudhary, Fast algorithms for the maximum clique problem on massive sparse graphs,
in Proceedings of WAW 2013, Algorithms and Models for the Web Graph, Lecture Notes
in Comput. Sci. 8305, Springer, New York, 2013, pp. 156–169.
[49] B. Pattabiraman, Md. Mostofa Ali Patwary, A. H. Gebremedhin, W.-K. Liao, and
A. Choudhary, Fast algorithms for the maximum clique problem on massive sparse graphswith applications to overlapping community detection, Internet. Math., 11 (2015), pp. 421–
448.

C616

RYAN A. ROSSI, DAVID F. GLEICH, AND ASSEFAW H. GEBREMEDHIN[50] P. Prosser, Exact algorithms for maximum clique: A computational study, arXiv:1207.4616v1,
2012.
[51] R. A. Rossi, D. F. Gleich, A. H. Gebremedhin, and Md. Mostofa Ali Patwary, Fast
maximum clique algorithms for large graphs, in the Companion Publication of the 23rd
International Conference on the World Wide Web (WWW Companion ’14), International
World Wide Web Conferences Steering Committee, Geneva, Switzerland, 2014, pp. 365–366.
[52] P. San Segundo, D. Rodrı́guez-Losada, and A. Jiménez, An exact bit-parallel algorithm
for the maximum clique problem, Comput. Oper. Res., 38 (2011), pp. 571–581.
¨ V. Çatalyürek, Streaming[53] A. E. Sarı́yüce, B. Gedik, G. Jacques-Silva, K.-L. Wu, and U.
algorithms for k-core decomposition, in Proceedings of the Very Large Databases Endowment meeting, 6 (2013), pp. 433–444.
[54] M. C. Schmidt, N. F. Samatova, K. Thomas, and B. H. Park, A scalable, parallel algorithm
for maximal clique enumeration, J. Parallel Distributed Comput., 69 (2009), pp. 417–428.
[55] S. B. Seidman, Network structure and minimum degree, Social Networks, 5 (1983), pp. 269–
287.
[56] R. Singh, J. Xu, and B. Berger, Global alignment of multiple protein interaction networks
with application to functional orthology detection, Proc. Natl. Acad. Sci. USA, 105 (2008),
pp. 12763–12768.
[57] SocioPatterns, Infectious SocioPatterns Dynamic Contact Networks, dataset available fromhttp://www.sociopatterns.org/datasets/ (accessed 09/12/12).
[58] E. Tomita and T. Kameda, An eﬃcient branch-and-bound algorithm for ﬁnding a maximum
clique with computational experiments, J. Global Optim., 37 (2007), pp. 95–111.
[59] E. Tomita, A. Tanaka, and H. Takahashi, The worst-case time complexity for generating
all maximal cliques and computational experiments, Theoret. Comput. Sci., 363 (2006),
pp. 28–42.
[60] A. L. Traud, P. J. Mucha, and M. A. Porter, Social structure of Facebook networks, Phys.
A, 391 (2012), pp. 4165–4180.
[61] M. A. Trick and D. S. Johnson, eds., Cliques, Coloring, and Satisﬁability: Second DIMACS
Implementation Challenge, AMS, New York, 1996.
[62] P. Mahadevan, D. Krioukov, M. Fomenkov, X. Dimitropoulos, A. Vahdat, and others
The Internet AS-level topology: Three data sources and one deﬁniitive metric, SIGCOMM,
36 (2006), pp. 17–26.
[63] C. Wilson, B. Boe, A. Sala, K. P. N. Puttaswamy, and B. Y. Zhao, User interactions insocial networks and their implications, in Proceedings of the Fourth EuroSys Conference,
ACM, New York, 2009, pp. 205–218.
[64] J. Xiang, C. Guo, and A. Aboulnaga, Scalable maximum clique computation using mapreduce, in Proceedings of the Conference on Data Engineering (ICDE), IEEE Press, Piscataway, NJ, 2013, pp. 74–85.
[65] Y. Xie and P. S. Yu, Max-clique: A top-down graph-based approach to frequent pattern mining,in Proceedings of the 10th IEEE International Conference on Data Mining (ICDM), IEEE
Press, Piscataway, NJ, 2010, pp. 1139–1144.
[66] J. Yang and J. Leskovec, Deﬁning and evaluating network communities based on groundtruth, in Proceedings of the 12th IEEE International Conference on Data Mining (ICDM),
IEEE Press, Piscataway, NJ, 2012, pp. 745–754.