10.3. DIRECT DISCOVERY OF COMMUNITIES
369
A
B
C
D
E
G
H
F
I
Figure 10.9: Graph for exercises
10.3.1
Finding Cliques
Our ﬁrst thought about how we could ﬁnd sets of nodes with many edges
between them is to start by ﬁnding a large clique (a set of nodes with edges
between any two of them). However, that task is not easy. Not only is ﬁnding
maximal cliques NP-complete, but it is among the hardest of the NP-complete
problems in the sense that even approximating the maximal clique is hard.
Further, it is possible to have a set of nodes with almost all edges between
them, and yet have only relatively small cliques.
Example 10.10 : Suppose our graph has nodes numbered 1, 2, . . ., n and there
is an edge between two nodes i and j unless i and j have the same remain-
der when divided by k. Then the fraction of possible edges that are actually
present is approximately (k −1)/k. There are many cliques of size k, of which
{1, 2, . . ., k} is but one example.
Yet there are no cliques larger than k. To see why, observe that any set of
k + 1 nodes has two that leave the same remainder when divided by k. This
point is an application of the “pigeonhole principle.” Since there are only k
diﬀerent remainders possible, we cannot have distinct remainders for each of
k + 1 nodes. Thus, no set of k + 1 nodes can be a clique in this graph.
✷
10.3.2
Complete Bipartite Graphs
Recall our discussion of bipartite graphs from Section 8.3.
A complete bipartite
graph consists of s nodes on one side and t nodes on the other side, with all st
possible edges between the nodes of one side and the other present. We denote
this graph by Ks,t. You should draw an analogy between complete bipartite
graphs as subgraphs of general bipartite graphs and cliques as subgraphs of
general graphs. In fact, a clique of s nodes is often referred to as a complete
