370
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
graph and denoted Ks, 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 guar-
antee 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 ﬁnd 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 ﬁnd-
ing in ordinary 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 identiﬁed 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 ﬁnd instances
of Ks,t within it. It is possible to view the problem of ﬁnding instances of Ks,t
within G as one of ﬁnding frequent itemsets. For this purpose, let the “items”
be the nodes on one side of G, which we shall call the left side. We assume that
the instance of Ks,t we are looking for has t nodes on the left side, and we shall
also assume for eﬃciency that t ≤s. The “baskets” correspond to the nodes
on the other side of G (the right side). The members of the basket for node v
are the nodes of the left side to which v is connected. Finally, let the support
threshold be s, the number of nodes that the instance of Ks,t has on the right
side.
We can now state the problem of ﬁnding instances of Ks,t as that of ﬁnding
frequent itemsets F of size t. That is, if a set of t nodes on the left side is
frequent, then they all occur together in at least s baskets. But the baskets
are the nodes on the right side. Each basket corresponds to a node that is
connected to all t of the nodes in F. Thus, the frequent itemset of size t and s
1It is important to understand that we do not mean a generated subgraph – one formed
by selecting some nodes and including all edges. In this context, we only require that there
be edges between any pair of nodes on diﬀerent sides. It is also possible that some nodes on
the same side are connected by edges as well.
