372
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
basket contributes to
di
t

itemsets of size t. The total contribution of the n
nodes on the right is P
i
di
t

. The value of this sum depends on the di’s, of
course. However, we know that the average value of di is d. It is known that
this sum is minimized when each di is d. We shall not prove this point, but a
simple example will suggest the reasoning: since
di
t

grows roughly as the tth
power of di, moving 1 from a large di to some smaller dj will reduce the sum
of
di
t

+
dj
t

.
Example 10.12 : Suppose there are only two nodes, t = 2, and the average
degree of the nodes is 4. Then d1+d2 = 8, and the sum of interest is
d1
2

+
d2
2

.
If d1 = d2 = 4, then the sum is
4
2

+
4
2

= 6 + 6 = 12. However, if d1 = 5 and
d2 = 3, the sum is
5
2

+
3
2

= 10 + 3 = 13. If d1 = 6 and d2 = 2, then the sum
is
6
2

+
2
2

= 15 + 1 = 16.
✷
Thus, in what follows, we shall assume that all nodes have the average degree
d. So doing minimizes the total contribution to the counts for the itemsets, and
thus makes it least likely that there will be a frequent itemset (itemset with
with support s or more) of size t. Observe the following:
• The total contribution of the n nodes on the right to the counts of the
itemsets of size t is n
d
t

.
• The number of itemsets of size t is
n
t

.
• Thus, the average count of an itemset of size t is n
d
t

/
n
t

; this expression
must be at least s if we are to argue that an instance of Ks,t exists.
If we expand the binomial coeﬃcients in terms of factorials, we ﬁnd
n
d
t

/
n
t

= nd!(n −t)!t!/
(d −t)!t!n!

=
n(d)(d −1) · · · (d −t + 1)/
n(n −1) · · · (n −t + 1)

To simplify the formula above, let us assume that n is much larger than d, and
d is much larger than t. Then d(d −1) · · · (d −t + 1) is approximately dt, and
n(n −1) · · · (n −t + 1) is approximately nt. We thus require that
n(d/n)t ≥s
That is, if there is a community with n nodes on each side, the average degree
of the nodes is d, and n(d/n)t ≥s, then this community is guaranteed to have
a complete bipartite subgraph Ks,t. Moreover, we can ﬁnd the instance of Ks,t
eﬃciently, using the methods of Chapter 6, even if this small community is
embedded in a much larger graph. That is, we can treat all nodes in the entire
graph as baskets and as items, and run A-priori or one of its improvements on
the entire graph, looking for sets of t items with support s.
