BetweennessCentrality

BetweennessCentrality[g]
gives a list of betweenness centralities for the vertices in the graph g.

DetailsDetails

  • BetweennessCentrality will give high centralities to vertices that are on many shortest paths of other vertex pairs.
  • BetweennessCentrality for a vertex in a connected graph is given by , where is the number of shortest paths from to and is the number of shortest paths from to passing through .
  • The ratio is taken to be zero when there is no path from to .
  • BetweennessCentrality works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Background
Background

  • BetweennessCentrality returns a list of non-negative machine numbers ("betweenness centralities") that approximate particular centrality measures of the vertices of a graph. Betweenness centralities lie between and inclusive, where is the number of vertices in a graph. A betweenness centrality is a measure of the centrality of a node in a network based on the number of shortest paths that pass through it. BetweennessCentrality therefore identifies nodes in the network that are crucial for information flow. This measure was introduced by the sociologist Linton Freeman in 1977 and has found applications in social networks, transportation, biology, and social sciences.
  • For a vertex in a connected graph, the betweenness centrality is given by , where is the number of shortest paths from to , and is the number of shortest paths from to passing through . Here, the ratio is taken to be zero when there is no path from to .
  • BetweennessCentrality is a global centrality measure. Other prominent centrality measures that identify different properties of graphs include ClosenessCentrality and DegreeCentrality. EdgeBetweennessCentrality applies the same betweenness concept to find the edge-based betweenness centrality.

ExamplesExamplesopen allclose all

Basic Examples  (2)Basic Examples  (2)

Compute betweenness centralities:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

Highlight:

In[3]:=
Click for copyable input
Out[3]=

Rank vertices. Highest-ranked vertices are on many shortest paths of other vertex pairs:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=
In[3]:=
Click for copyable input
Out[3]=
Introduced in 2010
(8.0)
| Updated in 2014
(10.0)