P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-06 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:15
148 Community AnalysisAlgorithm 6.1Brute-Force Clique Identification
Require: Adjacency MatrixA, Vertexvx
1: return Maximal CliqueCcontainingvx
2: CliqueQueue={{vx}};
3: whileCliqueQueue has not changeddo
4: C=pop(CliqueQueue);
5: vlast=Last node added to C;
6: N(vlast)={vi|Avlast,vi= 1 }.
7: for allvtemp∈N(vlast)do
8: ifC⋃
{vtemp}is a cliquethen
9: push(CliqueQueue,C⋃
{vtemp});
10: end if
11: end for
12: end while
13: Return the largest clique fromCliqueQueueBrute-force clique identification.The brute force method can find all
maximal cliques in a graph. For each vertexvx, we try to find the maxi-
mal clique that contains nodevx. The brute-force algorithm is detailed in
Algorithm6.1.
The algorithm starts with an empty queue of cliques. This queue is
initialized with the nodevxthat is being analyzed (a clique of size 1). Then,
from the queue, a clique is popped (C). The last node added to cliqueC
is selected (vlast). All the neighbors ofvlastare added to the popped clique
Csequentially, and if the new set of nodes creates a larger clique (i.e., the
newly added node is connected to all of the other members), then the new
clique is pushed back into the queue. This procedure is followed until nodes
can no longer be added.
The brute-force algorithm becomes impractical for large networks. For
instance, for a complete graph of only 100 nodes, the algorithm will generate
2100 different cliques starting from any node in the graph (why?).
The performance of the brute-force algorithm can be enhanced by prun-
ing specific nodes and edges. If the cliques being searched for are of size
kor larger, we can simply assume that the clique, if found, should contain
nodes that have degrees equal to or more thank−1. We can first prune all
nodes (and edges connected to them) with degrees less thank−1. Due to
the power-law distribution of node degrees, many nodes exist with small
degrees (1, 2, etc.). Hence, for a large enoughkmany nodes and edges