406
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
The neighborhood of radius d for a node v is the set of nodes u for which
there is a path of length at most d from v to u. We denote this neighborhood
by N(v, d). For example, N(v, 0) is always {v}, and N(v, 1) is v plus the set of
nodes to which there is an arc from v. More generally, if V is a set of nodes,
then N(V, d) is the set of nodes u for which there is a path of length d or less
from at least one node in the set V .
The neighborhood proﬁle of a node v is the sequence of sizes of its neighbor-
hoods |N(v, 1)|, |N(v, 2)|, . . . . We do not include the neighborhood of distance
0, since its size is always 1.
A
B
D
E
G
F
C
Figure 10.24: Our small social network; think of it as a directed graph
Example 10.29 : Consider the undirected graph of Fig. 10.1, which we re-
produce here as Fig. 10.24.
To turn it into a directed graph, think of each
edge as a pair of arcs, one in each direction. For instance, the edge (A, B)
becomes the arcs A →B and B →A. First, consider the neighborhoods of
node A. We know N(A, 0) = {A}. Moreover, N(A, 1) = {A, B, C}, since there
are arcs from A only to B and C. Furthermore, N(A, 2) = {A, B, C, D} and
N(A, 3) = {A, B, C, D, E, F, G}. Neighborhoods for larger radius are all the
same as N(A, 3).
On the other hand, consider node B. We ﬁnd N(B, 0) = {B}, N(B, 1) =
{A, B, C, D}, and N(B, 2) = {A, B, C, D, E, F, G}. We know that B is more
central to the network than A, and this fact is reﬂected by the neighborhood
proﬁles of the two nodes. Node A has proﬁle 3, 4, 7, 7, . . ., while B has proﬁle
4, 7, 7, . . . . Evidently, B is more central than A, because at every distance, its
neighborhood is at least as large as that of A. In fact, D is even more central
than B, because its neighborhood proﬁle 5, 7, 7, . . . dominates the proﬁle of each
of the nodes.
✷
10.8.2
The Diameter of a Graph
The diameter of a directed graph is the smallest integer d such that for every
two nodes u and v there is a path of length d or less from u to v. In a directed
graph, this deﬁnition only makes sense if the graph is strongly connected; that
is, there is a path from any node to any other node.
Recall our discussion
of the Web in Section 5.1.3, where we observed that there is a large strongly
