Database Reference
In-Depth Information
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.
EXAMPLE
10.6
Figure 10.4
is a breadth-first 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.
□
Figure 10.4
Step 1 of the Girvan-Newman Algorithm
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 final 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 edges above, since there could be several different 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
Y
1
, Y
2
, . . . , Y
k
. Let
p
i
be the number of shortest paths
