Skip to main content

betweenness_centrality

docs-source

Abstract#

Centrality analysis provides information about the node’s importance for an information flow or connectivity of the network. Betweenness centrality is one of the most used centrality metrics. Betweenness centrality measures the extent to which a node lies on paths between other nodes in the graph. Thus, nodes with high betweenness may have considerable influence within a network under their control over information passing between others. The calculation of betweenness centrality is not standardized, and there are many ways to solve it. It is defined as the number of shortest paths in the graph that passes through the node divided by the total number of shortest paths. The implemented algorithm is described in the paper "A Faster Algorithm for Betweenness Centrality" 1.

1 A Faster Algorithm for Betweenness Centrality, Ulrik Brandes

TraitValue
Module typealgorithm
ImplementationC++
Graph directiondirected/undirected
Edge weightsunweighted
Parallelismparallel

Procedures#

get(directed, normalized, threads)#

Input:#

  • directed: bool(True) ➡ If False the direction of the edges is ignored
  • normalized: bool(True) ➡ If True the betweenness values are normalized by 2/((n-1)(n-2)) for graphs, and 1/((n-1)(n-2)) for directed graphs where n is the number of nodes.
  • threads: Integer(number of concurrent threads supported by the implementation) ➡ The number of threads used to calculate betweenness centrality.

Output:#

  • betweeenness_centrality: float ➡ Value of betweenness for a given node

  • node: Vertex ➡ Graph vertex for betweenness calculation

Usage:#

CALL betweenness_centrality.get()YIELD node, betweeenness_centrality;

Example#