Database Reference
In-Depth Information
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
.
EXAMPLE
10.13 Suppose there is a community with 100 nodes on each side, and the aver-
age degree of nodes is 50; i.e., half the possible edges exist. This community will have an
instance of
K
s,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
we see that for the case
t
= 4 we need
That
is,
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 in-
stance of
K
6
.
4
exists in this community.
□
10.3.5
Exercises for Section 10.3
instances of
K
s,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 2
n
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
K
s,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 different pair (
s
′,
t
′) such that both
s
′ ≥
s
and
t
′ ≥
t
hold.
