364
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Edges between levels are called DAG edges (“DAG” stands for directed,
acyclic graph).
Each DAG edge will be part of at least one shortest path
from root X. If there is a DAG edge (Y, Z), where Y is at the level above Z
(i.e., closer to the root), then we shall call Y a parent of Z and Z a child of Y ,
although parents are not necessarily unique in a DAG as they would be in a
tree.
E
D
F
B
G
A
C
1
1
2
1
1
1
1
Level 1
Level 2
Level 3
Figure 10.4: Step 1 of the Girvan-Newman Algorithm
Example 10.6 : Figure 10.4 is a breadth-ﬁrst presentation of the graph of Fig.
10.3, starting at node E. Solid edges are DAG edges and dashed edges connect
nodes at the same level.
✷
The second step of the GN algorithm is to label each node by the number of
shortest paths that reach it from the root. Start by labeling the root 1. Then,
from the top down, label each node Y by the sum of the labels of its parents.
Example 10.7 : In Fig. 10.4 are the labels for each of the nodes. First, label
the root E with 1. At level 1 are the nodes D and F. Each has only E as a
parent, so they too are labeled 1. Nodes B and G are at level 2. B has only
D as a parent, so B’s label is the same as the label of D, which is 1. However,
G has parents D and F, so its label is the sum of their labels, or 2. Finally, at
level 3, A and C each have only parent B, so their labels are the label of B,
which is 1.
✷
The third and ﬁnal step is to calculate for each edge e the sum over all nodes
Y of the fraction of shortest paths from the root X to Y that go through e.
This calculation involves computing this sum for both nodes and edges, from
the bottom. Each node other than the root is given a credit of 1, representing
the shortest path to that node. This credit may be divided among nodes and
