10.2. CLUSTERING OF SOCIAL-NETWORK GRAPHS
365
edges above, since there could be several diﬀerent shortest paths to the node.
The rules for the calculation are as follows:
1. Each leaf in the DAG (a leaf is a node with no DAG edges to nodes at
levels below) gets a credit of 1.
2. Each node that is not a leaf gets a credit equal to 1 plus the sum of the
credits of the DAG edges from that node to the level below.
3. A DAG edge e entering node Z from the level above is given a share of the
credit of Z proportional to the fraction of shortest paths from the root to
Z that go through e. Formally, let the parents of Z be Y1, Y2, . . . , Yk. Let
pi be the number of shortest paths from the root to Yi; this number was
computed in Step 2 and is illustrated by the labels in Fig. 10.4. Then the
credit for the edge (Yi, Z) is the credit of Z times pi divided by Pk
j=1 pj.
After performing the credit calculation with each node as the root, we sum
the credits for each edge. Then, since each shortest path will have been discov-
ered twice – once when each of its endpoints is the root – we must divide the
credit for each edge by 2.
Example 10.8 : Let us perform the credit calculation for the BFS presentation
of Fig. 10.4. We shall start from level 3 and proceed upwards. First, A and C,
being leaves, get credit 1. Each of these nodes have only one parent, so their
credit is given to the edges (B, A) and (B, C), respectively.
E
D
F
B
G
A
C
1
1
3
1
1
1
Figure 10.5: Final step of the Girvan-Newman Algorithm – levels 3 and 2
At level 2, G is a leaf, so it gets credit 1. B is not a leaf, so it gets credit
equal to 1 plus the credits on the DAG edges entering it from below. Since
both these edges have credit 1, the credit of B is 3. Intuitively 3 represents the
fact that all shortest paths from E to A, B, and C go through B. Figure 10.5
shows the credits assigned so far.
