pgr_betweennessCentrality - pgRouting Manual (3.7)

Description

The Brandes Algorithm takes advantage of the sparse graphs for evaluating the betweenness centrality score of all vertices.

Betweenness centrality measures the extent to which a vertex lies on the shortest paths between all other pairs of vertices. Vertices with a high betweenness centrality score may have considerable influence in a network by the virtue of their control over the shortest paths passing between them.

The removal of these vertices will affect the network by disrupting the it, as most of the shortest paths between vertices pass through them.

This implementation work for both directed and undirected graphs.

• Running time: \(\Theta(VE)\)

• Running space: \(\Theta(VE)\)

• Throws when there are no edges in the graph

Signatures

Summary

Example :

For a directed graph with edges \(\{1, 2, 3, 4\}\) .

SELECT * FROM pgr_betweennessCentrality(
'SELECT id, source, target, cost, reverse_cost
FROM edges where id < 5'
) ORDER BY vid;
 vid  centrality
-----+------------
   5           0
   6         0.5
   7           0
  10        0.25
  15           0
(5 rows)

Explanation

• The betweenness centrality are between parenthesis.

• The leaf vertices have betweenness centrality \(0\) .

• Betweenness centrality of vertex \(6\) is higher than of vertex \(10\) .

  • Removing vertex \(6\) will create three graph components.

  • Removing vertex \(10\) will create two graph components.

Parameters

Inner Queries

Result columns

See Also

• Boost’s betweenness_centrality

• Queries use the Sample Data network.

Indices and tables

• Index

• Search Page