10.3. DIRECT DISCOVERY OF COMMUNITIES
373
Example 10.13 : Suppose there is a community with 100 nodes on each side,
and the average degree of nodes is 50; i.e., half the possible edges exist. This
community will have an instance of Ks,t, provided 100(1/2)t ≥s. For example,
if t = 2, then s can be as large as 25. If t = 3, s can be 11, and if t = 4, s can
be 6.
Unfortunately, the approximation we made gives us a bound on s that is a
little too high. If we revert to the original formula n
d
t

/
n
t

≥s, we see that
for the case t = 4 we need 100
50
4

/
100
4

≥s. That is,
100 × 50 × 49 × 48 × 47
100 × 99 × 98 × 97
≥s
The expression on the left is not 6, but only 5.87. However, if the average
support for an itemset of size 4 is 5.87, then it is impossible that all those
itemsets have support 5 or less. Thus, we can be sure that at least one itemset
of size 4 has support 6 or more, and an instance of K6.4 exists in this community.
✷
10.3.5
Exercises for Section 10.3
Exercise 10.3.1: For the running example of a social network from Fig. 10.1,
how many instances of Ks,t are there for:
(a) s = 1 and t = 3.
(b) s = 2 and t = 2.
(c) s = 2 and t = 3.
Exercise 10.3.2: Suppose there is a community of 2n nodes.
Divide the
community into two groups of n members, at random, and form the bipartite
graph between the two groups. Suppose that the average degree of the nodes of
the bipartite graph is d. Find the set of maximal pairs (t, s), with t ≤s, such
that an instance of Ks,t is guaranteed to exist, for the following combinations
of n and d:
(a) n = 20 and d = 5.
(b) n = 200 and d = 150.
(c) n = 1000 and d = 400.
By “maximal,” we mean there is no diﬀerent pair (s′, t′) such that both s′ ≥s
and t′ ≥t hold.
