Complex Networks

96 

Complex Networks: An Algorithmic Perspective

In the first step of the algorithm, all of the shortest paths from each vertex to

all other vertices and predecessor vertices on these shortest paths are found. In the

second step of the algorithm, for every vertex s ∈ V, the dependencies

δ

(v) for all

v ∈ V are computed using the shortest paths trees data and predecessor sets along

these paths. In the last step, the sum of all dependency values are computed to give

betweenness centrality values of vertices.

The edge betweenness value of an edge e in a graph G is defined as the number

of shortest paths that pass through e [16]. If there is more than one