Mining Social-Network Graphs - Mining of Massive Datasets - page 328

Is this graph really typical of a social network, in the sense that it exhibits locality of
relationships? First, note that the graph has nine edges out of the pairs of nodes that
could have had an edge between them. Suppose X , Y , and Z are nodes of Fig. 10.1 , with
edges between X and Y and also between X and Z . What would we expect the probability
of an edge between Y and Z to be? If the graph were large, that probability would be very
close to the fraction of the pairs of nodes that have edges between them, i.e., 9/21 = .429 in
this case. However, because the graph is small, there is a noticeable difference between the
true probability and the ratio of the number of edges to the number of pairs of nodes. Since
we already know there are edges ( X, Y ) and ( X, Z ), there are only seven edges remaining.
Those seven edges could run between any of the 19 remaining pairs of nodes. Thus, the
probability of an edge ( Y, Z ) is 7/19 = .368.
Now, we must compute the probability that the edge ( Y, Z ) exists in Fig. 10.1 , given that
edges ( X, Y ) and ( X, Z ) exist. What we shall actually count is pairs of nodes that could be Y
and Z , without worrying about which node is Y and which is Z . If X is A , then Y and Z must
be B and C , in some order. Since the edge ( B, C ) exists, A contributes one positive example
(where the edge does exist) and no negative examples (where the edge is absent). The cases
where X is C , E , or G are essentially the same. In each case, X has only two neighbors, and
the edge between the neighbors exists. Thus, we have seen four positive examples and zero
negative examples so far.
Now, consider X = F . F has three neighbors, D , E , and G . There are edges between two of
the three pairs of neighbors, but no edge between G and E . Thus, we see two more positive
examples and we see our first negative example. If X = B , there are again three neighbors,
but only one pair of neighbors, A and C , has an edge. Thus, we have two more negative ex-
amples, and one positive example, for a total of seven positive and three negative. Finally,
when X = D , there are four neighbors. Of the six pairs of neighbors, only two have edges
between them.
Thus, the total number of positive examples is nine and the total number of negative
examples is seven. We see that in Fig. 10.1 , the fraction of times the third edge exists is
thus 9/16 = .563. This fraction is considerably greater than the .368 expected value for that
fraction. We conclude that Fig. 10.1 does indeed exhibit the locality expected in a social
network.

□

10.1.3 Varieties of Social Networks

There are many examples of social networks other than “friends” networks. Here, let us
enumerate some of the other examples of networks that also exhibit locality of relation-
ships.