390
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
10.6.1
Random Walkers on a Social Graph
Recall our view of PageRank in Section 5.1 as reﬂecting what a “random surfer”
would do if they walked on the Web graph. We can similarly think of a per-
son “walking” on a social network. The graph of a social network is generally
undirected, while the Web graph is directed. However, the diﬀerence is unim-
portant. 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).
Suppose, for example, that such a walker starts out at node T1 of Fig. 10.2,
which we reproduce here as Fig. 10.21. At the ﬁrst step, it would go either to
U1 or W1. If to W1, then it would next either come back to T1 or go to T2. If
the walker ﬁrst moved to U1, it would wind up at either T1, T2, or T3 next.
U
U
T
T
T
T
W
W
W
1
1
1
2
2
2
3
3
4
Figure 10.21: Repeat of Fig. 10.2
We conclude that, starting at T1, there is a good chance the walker would
visit T2, at least initially, and that chance is better than the chance it would
visit T3 or T4. It would be interesting if we could infer that tags T1 and T2 are
therefore related or similar in some way. The evidence is that they have both
been placed on a common Web page, W1, and they have also been used by a
common tagger, U1.
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 out. This conclusion comes from the theory of Markov
processes that we mentioned in Section 5.1.2, although the independence from
the starting point requires additional conditions besides connectedness that the
graph of Fig. 10.21 does satisfy.
