396
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
probability rather than certainly move at each step) is not important.
the
walkers will still distribute themselves eventually as they would if they took a
synchronous random walk. But the distribution of residuals is not the answer
that the algorithm gives. Rather, the answer is the vector r when the algorithm
terminates. In fact, the values that get moved from q to r are fraction 1 −β of
the values of the residuals at random times, depending on the order in which
we select nodes to be U. However, the true PageRank for any node V is the
probability that a walker is at node V at a random time, given that it started
out at the source S. By picking U at random (among nodes with suﬃciently
large residual), we are simulating the selection of a random time at which to
view each walker, and therefore, getting approximately the correct distribution
of the walkers.
10.6.5
Application of Simrank to Finding Communities
An interesting application of simrank is ﬁnding the communities to which a
given node (the source node) belongs. We could then ﬁnd all the reasonable
communities in a network by selecting as source nodes those nodes that have
not yet been assigned to any community, or that have been assigned to only a
small number of communities.
Suppose we start with source node S and ﬁnd the simrank for all the nodes
for this source. We could use either the exact or approximate simrank algorithm
to do so. Then, order the nodes other than S by their simrank, and consider
adding each, highest simrank ﬁrst, to a community containing S. We need to
know when to stop adding nodes, so we need a stopping criterion. A simple
approach is to add nodes until the density of edges – the fraction of edges
that connect nodes in the community divided by the number of possible edges
connecting nodes in the community (i.e.,
n
2

for an n-node community) – goes
below a threshold.
Example 10.26 : Let us consider the very simple network from Fig. 10.22. We
shall use Picture1 as the source node, so we are trying to ﬁnd good communities
containing that node.
The network is too small to give a reasonable set of
communities, but it will serve for an example of the algorithm.
We learned from Example 10.23 that with Picture1 as the source node, the
simrank values for the ﬁve nodes are in the order Picture1, Sky, Tree, Picture3,
Picture2. The community consisting of the ﬁrst two nodes on this list has a
density of 1, since the one possible edge between Picture1 and Sky is indeed
present. When we add the third node, Tree, the density falls to 2/3, since only
two of the possible three edges are present. Adding the fourth node, Picture3,
keeps the density at 2/3; now four of the six possible edges are present. If we
add the last node, the density is down to 1/2 – ﬁve of the ten possible edges are
present in the entire network. If our threshold in density is greater than 2/3,
then we would pick only the ﬁrst two nodes as the community, while if we have
a threshhold t, with 2/3 ≥t > 1/2, then we would pick the ﬁrst four nodes as
the community.
✷
