10.3. DIRECT DISCOVERY OF COMMUNITIES
371
of the baskets in which all those items appear form an instance of Ks,t.
4
1
a
b
c
d
2
3
Figure 10.10: The bipartite graph from Fig. 8.1
Example 10.11 : Recall the bipartite graph of Fig. 8.1, which we repeat here as
Fig. 10.10. The left side is the nodes {1, 2, 3, 4} and the right side is {a, b, c, d}.
The latter are the baskets, so basket a consists of “items” 1 and 4; that is,
a = {1, 4}. Similarly, b = {2, 3}, c = {1} and d = {3}.
If s = 2 and t = 1, we must ﬁnd itemsets of size 1 that appear in at least
two baskets. {1} is one such itemset, and {3} is another. However, in this tiny
example there are no itemsets for larger, more interesting values of s and t,
such as s = t = 2.
✷
10.3.4
Why Complete Bipartite Graphs Must Exist
We must now turn to the matter of demonstrating that any bipartite graph
with a suﬃciently high fraction of the edges present will have an instance of
Ks,t. In what follows, assume that the graph G has n nodes on the left and
another n nodes on the right. Assume the two sides have the same number of
nodes simpliﬁes the calculation, but the argument generalizes to sides of any
size. Finally, let d be the average degree of all nodes.
The argument involves counting the number of frequent itemsets of size t
that a basket with d items contributes to. When we sum this number over all
nodes on the right side, we get the total frequency of all the subsets of size t on
the left. When we divide by
n
t

, we get the average frequency of all itemsets
of size t. At least one must have a frequency that is at least average, so if this
average is at least s, we know an instance of Ks,t exists.
Now, we provide the detailed calculation. Suppose the degree of the ith
node on the right is di; that is, di is the size of the ith basket.
Then this
