pgr_betweennessCentrality

pgr_betweennessCentrality - Calculates the relative betweeness centrality using Brandes Algorithm

Boost Graph Inside

Availability

• Version 3.7.0

  • New experimental function:

    • pgr_betweennessCentrality

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

pgr_betweennessCentrality(Edges SQL, [directed])

Returns set of (vid, centrality)

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

Parameter	Type	Default	Description
Edges SQL	TEXT		Edges SQL as described below.

Optional parameters

Column	Type	Default	Description
directed	BOOLEAN	true	When true the graph is considered Directed When false the graph is considered as Undirected.

Inner Queries

Edges SQL

Column	Type	Default	Description
source	ANY-INTEGER		Identifier of the first end point vertex of the edge.
target	ANY-INTEGER		Identifier of the second end point vertex of the edge.
cost	ANY-NUMERICAL		Weight of the edge (source, target)
reverse_cost	ANY-NUMERICAL	-1	Weight of the edge (target, source) When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result columns

Column	Type	Description
vid	BIGINT	Identifier of the vertex.
centrality	FLOAT	Relative betweenness centrality score of the vertex (will be in range [0,1])

See Also

• Boost’s betweenness_centrality

• Queries use the Sample Data network.

Indices and tables

• Index

• Search Page