User Tools

Site Tools


algorithms:betweenness

Betweenness Centrality

Node betweenness is a number in the [0, 1] interval equal to the fraction of all the shortest paths in the network that pass through that node. A value close to 1 indicates that the node has a key role in the transmission of information across the network. Nodes with high betweenness, if removed, reduce noticeably the rate of spreading phenomena. A link property considered as distance and parallel edges can be taken into account in the shortest paths calculation.

Similarly, we define the link betweenness as the number of shortest paths that include that link, ranking the links according to their ability to transmit information. Since their computation is very similar, node and link betweenness are calculated together.

Input Parameter Type Default Description
Distance Property text None Link property used as a distance. The property values should be positive numbers.


The following plot shows the node betweenness for a social network. It identifies (surrounded by a black dashed line) ego nodes that are in the center of a community, and bridge nodes (surrounded by a pink line) that act as bridges between different groups of people. Those are the key nodes in terms of gossip spreading and ability to introduce unknown people.



The next picture shows the same network with the links colored according to their betweenness values. Blueindicates low values (the majority of them), while red highlights the most important links according to betweenness. We may interpret them as the most important channels for information transmission.



References:

  • M.E.J. Newman, Networks, an introduction, Oxford University Press, 2010, ISBN: 978-0-19-920665-0, sec. 10.3.
algorithms/betweenness.txt · Last modified: 2018/12/20 14:22 by systems