366
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Now, let us proceed to level 1.
B has only one parent, D, so the edge
(D, B) gets the entire credit of B, which is 3. However, G has two parents, D
and F. We therefore need to divide the credit of 1 that G has between the edges
(D, G) and (F, G). In what proportion do we divide? If you examine the labels
of Fig. 10.4, you see that both D and F have label 1, representing the fact that
there is one shortest path from E to each of these nodes. Thus, we give half
the credit of G to each of these edges; i.e., their credit is each 1/(1 + 1) = 0.5.
Had the labels of D and F in Fig. 10.4 been 5 and 3, meaning there were ﬁve
shortest paths to D and only three to F, then the credit of edge (D, G) would
have been 5/8 and the credit of edge (F, G) would have been 3/8.
E
D
F
B
G
A
C
1
1
3
1
1
1
0.5
0.5
4.5
1.5
3
4.5
1.5
Figure 10.6: Final step of the Girvan-Newman Algorithm – completing the
credit calculation
Now, we can assign credits to the nodes at level 1. D gets 1 plus the credits
of the edges entering it from below, which are 3 and 0.5. That is, the credit of D
is 4.5. The credit of F is 1 plus the credit of the edge (F, G), or 1.5. Finally, the
edges (E, D) and (E, F) receive the credit of D and F, respectively, since each
of these nodes has only one parent. These credits are all shown in Fig. 10.6.
The credit on each of the edges in Fig. 10.6 is the contribution to the be-
tweenness of that edge due to shortest paths from E. For example, this contri-
bution for the edge (E, D) is 4.5.
✷
To complete the betweenness calculation, we have to repeat this calculation
for every node as the root and sum the contributions. Finally, we must divide
by 2 to get the true betweenness, since every shortest path will be discovered
twice, once for each of its endpoints.
10.2.5
Using Betweenness to Find Communities
The betweenness scores for the edges of a graph behave something like a distance
measure on the nodes of the graph. It is not exactly a distance measure, because
