Mining Social-Network Graphs - Mining of Massive Datasets - page 340

the “pigeonhole principle.” Since there are only k different 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 con-
sists 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 K s,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 graph and denoted K s , while a complete bipartite subgraph is sometimes called a
bi-clique .
While as we saw in Example 10.10 , it is not possible to guarantee that a graph with many
edges necessarily has a large clique, it is possible to guarantee that a bipartite graph with
many edges has a large complete bipartite subgraph. 1 We can regard a complete bipartite
subgraph (or a clique if we discovered a large one) as the nucleus of a community and add
to it nodes with many edges to existing members of the community. If the graph itself is
k -partite as discussed in Section 10.1.4 , then we can take nodes of two types and the edges
between them to form a bipartite graph. In this bipartite graph, we can search for complete
bipartite subgraphs as the nuclei of communities. For instance, in Example 10.2 , we could
focus on the tag and page nodes of a graph like Fig. 10.2 and try to find communities of
tags and Web pages. Such a community would consist of related tags and related pages that
deserved many or all of those tags.
However, we can also use complete bipartite subgraphs for community finding in ordin-
ary graphs where nodes all have the same type. Divide the nodes into two equal groups
at random. If a community exists, then we would expect about half its nodes to fall into
each group, and we would expect that about half its edges would go between groups. Thus,
we still have a reasonable chance of identifying a large complete bipartite subgraph in the
community. To this nucleus we can add nodes from either of the two groups, if they have
edges to many of the nodes already identified as belonging to the community.

10.3.3 Finding Complete Bipartite Subgraphs

Suppose we are given a large bipartite graph G , and we want to find instances of K s,t within
it. It is possible to view the problem of finding instances of K s,t within G as one of finding
frequent itemsets. For this purpose, let the “items” be the nodes on one side of G , which we