Skip to main content

Betweenness Centrality

Description​

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" by Ulrik Brandes of the University of Konstanz.

drawing

A larger circle means larger betweenness centrality. The middle one has the largest amount of shortest paths flowing through it.

Materials​

Implementation​

Betweenness
Centrality

Betweenness
Centrality

Betweenness Centrality is implemented as part of the MAGE project. Be sure to check it out in the link above. ☝️

Blog posts​

Betweenness
Centrality

In recent years, researchers have proved that essential proteins often have a correlation with disease genes. Therefore, the identification of essential proteins is the foundation for disease diagnosis and treatment. Drug design methods heavily rely on detecting essential proteins to find drug targets.

Playground​

Betweenness
Centrality

Use cases​

Social
networks

The metric of betweenness centrality can be used on a macro and micro scale in social networks. On a macro scale, a high measure will indicate the position of power (due to the large flow of information). On the other hand, on a micro-scale, a high measure represents the strength of a relationship with a narrow circle of friends.

Bioinformatics

Protein-protein interaction networks were created to get a better insight into how proteins interact with each other.

Transportation

Maybe the most important usage of this algorithm is transportation. In a complex and urban transportation network, centrality measurement can reveal the main bottlenecks and congestions within the system. Such can help to organize the infrastructure of a big city, as well as the amount spent in optimizing such routes.