Database Reference
In-Depth Information
10.6 Simrank
In this section, we shall take up another approach to analyzing social-network graphs. This
technique, called “simrank,” applies best to graphs with several types of nodes, although it
can in principle be applied to any graph. The purpose of simrank is to measure the similar-
ity between nodes of the same type, and it does so by seeing where random walkers on the
graph wind up when starting at a particular node. Because calculation must be carried out
once for each starting node, it is limited in the sizes of graphs that can be analyzed com-
pletely in this manner.
10.6.1
Random Walkers on a Social Graph
Recall our view of PageRank in
Section 5.1
as reflecting what a “random surfer” would do
if they walked on the Web graph. We can similarly think of a person “walking” on a social
network. The graph of a social network is generally undirected, while the Web graph is dir-
ected. However, the difference is unimportant. A walker at a node
N
of an undirected graph
will move with equal probability to any of the
neighbors
of
N
(those nodes with which
N
shares an edge).
reproduce here as
Fig. 10.21
.
At the first step, it would go either to
U
1
or
W
1
. If to
W
1
, then
it would next either come back to
T
1
or go to
T
2
. If the walker first moved to
U
1
, it would
wind up at either
T
1
,
T
2
, or
T
3
next.
Figure 10.21
Repeat of
Fig. 10.2
We conclude that, starting at
T
1
, there is a good chance the walker would visit
T
2
, at least
initially, and that chance is better than the chance it would visit
T
3
or
T
4
. It would be inter-
esting if we could infer that tags
T
1
and
T
2
are therefore related or similar in some way. The
evidence is that they have both been placed on a common Web page,
W
1
, and they have
also been used by a common tagger,
U
1
.
However, if we allow the walker to continue traversing the graph at random, then the
probability that the walker will be at any particular node does not depend on where it starts
