10.6. SIMRANK
397
Another measure of the goodness of a community C is the conductance. To
deﬁne conductance, we need ﬁrst to deﬁne the volume of a community C, which
is the smaller of the sum of the degress of the nodes in C and the sum of the
degrees of the nodes not in C. Then the conductance of C is the ratio of the
number of edges with exactly one end in C divided by the volume of C. The
intuitive idea behind conductance is that it looks for sets C that are neither too
small nor too large, and yet can be disconnected from the network by cutting
a relatively small number of edges. Small conductance suggests a closely knit
community.
When we consider the sequence of communities formed by adding one node
at a time, in order of their simrank, we often ﬁnd that there are several points
in the sequence where the conductance is a local minimum. These are the best
choices for a community containing the source node. If there is more than one
local minimum, then there are several communities, one nested within another,
to which the source node can be said to belong.
Example 10.27 : Let us repeat Example 10.26, but use conductance as the
criterion for goodness of a community. Recall the order in which we add nodes
is Picture1, Sky, Tree, Picture3, Picture2. Let Ci be the community containing
the ﬁrst i of these nodes, and let ci be the conductance of that community.
The ﬁrst possibility is C1 consisting of only the node Picture1. There are
two edges with exactly one end in C1. The volume of C1 is the smaller of 2 (the
degree of its one node) and 8 (the sum of the degrees of the other four nodes.
Thus, c1 = 2/ min(2, 8) = 1.
Now consider C2 = {Picture1, Sky}. There are three edges that have exactly
one end in C2. The volume of C2 is the smaller of the sum of the degrees of the
two nodes in C2 (i,e., 2 + 3 = 5) and the sum of the degrees of the other three
nodes, which is also 5. Thus, c2 = 3/ min(5, 5) = 3/5.
Now, consider adding Tree to form C3 = {Picture1, Sky, T ree}. The num-
ber of edges with exactly one end in C3 is three. The sum of the degrees of the
three nodes is 2+3+2 = 7, while the sum of the degrees of the other two nodes
is three. Thus, c3 = 3/ min(7, 3) = 1. You may continue this sequence and ﬁnd
that c4 = 1/ min(9, 1) = 1. In this case, there is only one minimum, and that
is c2 = 3/5. We thus conclude that the “best” community containing Picture1
is C2 = {Picture1, Sky}.
✷
10.6.6
Exercises for Section 10.6
Exercise 10.6.1: If, in Fig. 10.22 you start the walk from Picture 2, what will
be the similarity to Picture 2 of the other two pictures? Which do you expect
to be more similar to Picture 2?
Exercise 10.6.2: If, in Fig. 10.22 you start the walk from Picture 3, what do
you expect the similarity to the other two pictures to be?
