Compute betweenness centrality for an undirected graph
an instance of the
Brandes.betweenness.centrality computes the betweenness centrality of
each vertex or each edge in the graph, using an algorithm by U. Brandes.
Betweenness centrality of a vertex
v is calculated as follows:
N_st(v) = no. of shortest paths from
t that pass through
N_st = no. of shortest paths from
betweenness centrality of
sum(N_st(v)/N_st) for all vertices
Betweenness centrality of an edge is calculated similarly.
The relative betweenness centrality for a vertex is to scale the betweenness
centrality of the given vertex by
2/(n**2 - 3n + 2) where
the no. of vertices in the graph.
Central point dominance measures the maximum betweenness of any vertex in the graph.
See documentation on brandes betweenness centrality in Boost Graph Library for more details.
A list of
betweenness centrality of each vertex
betweenness centrality of each edge
relative betweenness centrality of each vertex
maximum betweenness of any point in the graph
Li Long <email@example.com>
Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )
The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8
1 2 3 4 5