10.1. SOCIAL NETWORKS AS GRAPHS
357
A
B
D
E
G
F
C
Figure 10.1: Example of a small social network
as “friends,” is represented by the edges. For instance, B is friends with A, C,
and D.
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
7
2

= 21 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
diﬀerence 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 ﬁrst 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 examples, 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
