Betweenness centrality

Definition

The betweenness centrality of a node v is given by the expression:

:g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}}

where \sigma_{st} is the total number of shortest paths from node s to node t and \sigma_{st}(v) is the number of those paths that pass through v (not where v is an end point).

The betweenness centrality of a node scales with the number of pairs of nodes as suggested by the summation indices. Therefore, the calculation may be rescaled by dividing through by the number of pairs of nodes not including v, so that g \in [0,1]. The division is done by (N-1)(N-2) for directed graphs and (N-1)(N-2)/2 for undirected graphs, where N is the number of nodes in the giant component. Note that this scales for the highest possible value, where one node is crossed by every single shortest path. This is often not the case, and a normalization can be performed without a loss of precision :\mbox{normal}(g(v)) = \frac{g(v) - \min(g)}{\max(g) - \min(g)} which results in: :\max(\mbox{normal}) = 1 :\min(\mbox{normal}) = 0 Note that this will always be a scaling from a smaller range into a larger range, so no precision is lost.

The load distribution in real and model networks

Model networks

--

, Squares:\gamma=2.5, Diamonds:\gamma=3.0, X's:\gamma=4.0, Triangles:\gamma= \infin ]]

-- It has been shown that the load distribution of a scale-free network follows a power law given by a load exponent \delta, :P(g) \approx g^{-\delta} (1) this implies the scaling relation to the degree of the node, :g(k) \approx k^\eta. Where g(k) is the average load of vertices with degree k. The exponents \delta and \eta are not independent since equation (1) implies :P(g)= \int P(k) \delta (g-k^\eta) dk For large g, and therefore large k, the expression becomes :P(g\gg1)= \int k^{-\gamma} \delta (g-k^\eta) dk :\sim g^{-1-\frac{\gamma -1}{\eta}} which proves the following equality: :\eta=\frac{\gamma -1}{\delta -1}

The important exponent appears to be \eta which describes how the betweenness centrality depends on the connectivity. The situation which maximizes the betweenness centrality for a vertex is when all shortest paths are going through it, which corresponds to a tree structure (a network with no clustering). In the case of a tree network the maximum value of \eta = 2 is reached. :\eta = 2 \rarr \delta = \frac{\gamma +1}{2} This maximal value of \eta (and hence minimum of \delta) puts bounds on the load exponents for networks with non-vanishing clustering. :\eta \le 2 \rarr \delta \ge \frac{\gamma +1}{2} In this case, the exponents \delta , \eta are not universal and depend on the different details (average connectivity, correlations, etc.)

Real networks

Real world scale free networks, such as the internet, also follow a power law load distribution. This is an intuitive result. Scale free networks arrange themselves to create short path lengths across the network by creating a few hub nodes with much higher connectivity than the majority of the network. These hubs will naturally experience much higher loads because of this added connectivity.

Weighted networks

In a weighted network the links connecting the nodes are no longer treated as binary interactions, but are weighted in proportion to their capacity, influence, frequency, etc., which adds another dimension of heterogeneity within the network beyond the topological effects. A node's strength in a weighted network is given by the sum of the weights of its adjacent edges.

:s_{i} = \sum_{j=1}^{N} a_{ij}w_{ij}

With a_{ij} and w_{ij} being adjacency and weight matrices between nodes i and j, respectively. Analogous to the power law distribution of degree found in scale free networks, the strength of a given node follows a power law distribution as well.

:s(k) \approx k^\beta

A study of the average value s(b) of the strength for vertices with betweenness b shows that the functional behavior can be approximated by a scaling form:

s(b)\approx b^{\alpha}

Percolation centrality

Percolation centrality is a version of weighted betweenness centrality, but it considers the 'state' of the source and target nodes of each shortest path in calculating this weight. Percolation of a 'contagion' occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a 'contagion' spreads over the links of a complex network, altering the 'states' of the nodes as it spreads, either recoverably or otherwise. For example, in an epidemiological scenario, individuals go from 'susceptible' to 'infected' state as the infection spreads. The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads. The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network. This measure was proposed by .

Percolation centrality is defined for a given node, at a given time, as the proportion of 'percolated paths' that go through that node. A 'percolated path' is a shortest path between a pair of nodes, where the source node is percolated (e.g., infected). The target node can be percolated or non-percolated, or in a partially percolated state.

:PC^t(v)= \frac{1}{N-2}\sum_{s \neq v \neq r}\frac{\sigma_{sr}(v)}{\sigma_{sr}}\frac{{x^t}_s}{{\sum {[{x^t}_i}]}-{x^t}_v}

where \sigma_{sr} is total number of shortest paths from node s to node r and \sigma_{sr}(v) is the number of those paths that pass through v. The percolation state of the node i at time t is denoted by {x^t}_i and two special cases are when {x^t}_i=0 which indicates a non-percolated state at time t whereas when {x^t}_i=1 which indicates a fully percolated state at time t. The values in between indicate partially percolated states ( e.g., in a network of townships, this would be the percentage of people infected in that town).

The attached weights to the percolation paths depend on the percolation levels assigned to the source nodes, based on the premise that the higher the percolation level of a source node is, the more important are the paths that originate from that node. Nodes which lie on shortest paths originating from highly percolated nodes are therefore potentially more important to the percolation. The definition of PC may also be extended to include target node weights as well. Percolation centrality calculations run in O(|V||E|) time with an efficient implementation adapted from Brandes' algorithm. If the calculation needs to consider target node weights, the worst case time is O(|V|^3).

Algorithms

Calculating the betweenness and closeness centralities of all the vertices in a graph involves calculating the shortest paths between all pairs of vertices on a graph, which takes \Theta(|V|^3) time with the Floyd–Warshall algorithm, modified to not only find one but count all shortest paths between two nodes. On a sparse graph, Johnson's algorithm or Brandes' algorithm may be more efficient, both taking O(|V|^2 \log |V| + |V| |E|) time. On unweighted graphs, calculating betweenness centrality takes O(|V| |E|) time using Brandes' algorithm.

In calculating betweenness and closeness centralities of all vertices in a graph, it is assumed that graphs are undirected and connected with the allowance of loops and multiple edges. When specifically dealing with network graphs, often graphs are without loops or multiple edges to maintain simple relationships (where edges represent connections between two people or vertices). In this case, using Brandes' algorithm will divide final centrality scores by 2 to account for each shortest path being counted twice.

Another algorithm generalizes the Freeman's betweenness computed on geodesics and Newman's betweenness computed on all paths, by introducing a hyper-parameter controlling the trade-off between exploration and exploitation. The time complexity is the number of edges times the number of nodes in the graph.

An approximate, probabilistic estimation of betweenness centralities can be obtained much faster by sampling paths using a bidirectional breadth-first search.

Applications

Social networks

In social network analysis, betweenness centrality can have different implications. From a macroscopic perspective, bridging positions or "structural holes" (indicated by high betweenness centrality) reflect power, because they allow the person on the bridging position to exercise control (e.g., decide whether to share information or not) over the persons it connects between. From the microscopic perspective of ego networks (i.e., only considering first-degree connections), in online social networks a high betweenness centrality coincides with nominations of closest friends (i.e., strong interpersonal ties), because it reflects social capital investments into the relationship when distant social circles (e.g., family and university) are bridged (often resulting from an introduction by ego).

River networks

Betweenness centrality has been used to analyze the topological complexity of river networks as well as their use in maritime trade.

Related concepts

Betweenness centrality is related to a network's connectivity, in so much as high betweenness vertices have the potential to disconnect graphs if removed (see cut set).

References

Bibliography

References

1. "Calculating the Betweenness Centrality in Gephi".
2. K.-I. Goh, B. Kahng, and D. Kim PhysRevLett.87.278701
3. M. Barthélemy. Betweenness centrality in large complex networks. Eur. Phys. J. B 38, 163–168 (2004)
4. Kwang-Il Goh, Eulsik Oh, Hawoong Jeong, Byungnam Kahng, and Doochul Kim. Classification of scale-free networks. PNAS (2002) vol. 99 no. 2
5. Eiland, Murray. (2020). "Networks of Rome, Byzantium, and China". Antiqvvs.