brandes.betweenness.centrality
Compute betweenness centrality for an undirected graph
Compute betweenness centrality for an undirected graph
 Keywords
 models
Usage
brandes.betweenness.centrality(g)
Arguments
 g
 an instance of the
graph
class withedgemode
“undirected”
Details
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 s
to t
that pass through v
,
N_st
= no. of shortest paths from s
to t
,
betweenness centrality of v
= sum(N_st(v)/N_st)
for all vertices s
!= v
!= t
.
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 n
is
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.
Value

A list of
 betweenness.centrality.vertices
 betweenness centrality of each vertex
 betweenness.centrality.edges
 betweenness centrality of each edge
 relative.betweenness.centrality.vertices
 relative betweenness centrality of each vertex
 dominance
 maximum betweenness of any point in the graph
References
Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )
The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, LieQuan Lee, and Andrew Lumsdaine; (AddisonWesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0201729148
See Also
Examples
con < file(system.file("XML/conn.gxl",package="RBGL"), open="r")
coex < fromGXL(con)
close(con)
coex < ugraph(coex)
brandes.betweenness.centrality(coex)