Shortest-Paths Betweenness Centrality


Ratio of the number of shortest paths passing through a node v out of all shortest paths between all node pairs in a network:
Shortest-Paths Betweenness Centrality
σst is the number of shortest paths between node s and t and σst(v) is the number of shortest paths passing on a node v out σst

The S.-P. Betweenness is a node centrality index. It is similar to the stress but provides a more elaborated and informative centrality index. It is calculated considering couples of nodes (v1, v2) and counting the number of shortest paths linking v1 and v2 and passing through a node n. Then, the value is related to the total number of shortest paths linking v1 and v2. Thus, a node can be traversed by only one path linking v1 and v2, but if this path is the only connecting v1 and v2 the node n will score a higher betweenness value (in the stress computation would have had a low score). Thus, a high S.-P. Betweenness score means that the node, for certain paths, is crucial to maintain node connections. Notably, to know the number of paths for which the node is critical it is necessary to look at the stress. Thus, stress and S.-P. Betweenness can be used to gain complementary information. Further information could be gained by referring the S.-P. Betweenness to node couples, thus quantifying the importance of a node for two connected nodes. Also here, high and low values are more meaningful when compared to the average S.-P. Betweenness value of the graph G calculated by averaging the S.-P. Betweenness values of all nodes in the graph.

The S.-P. Betweenness of a node in a biological network, for instance a protein-signaling network, can indicate the relevance of a protein as functionally capable of holding together communicating proteins. The higher the value the higher the relevance of the protein as organizing regulatory molecule. The S.-P. Betweenness of a protein effectively indicates the capability of a protein to bring in communication distant proteins. In signaling modules, proteins with high S.-P. Betweenness are likely crucial to maintain functionally and coherence of signaling mechanisms. [SCARDONI, G.,]

ABRA - Approximating Betweenness Centrality
Approximating Betweenness Centrality
Bromberger, S., Klymko, C., Henderson, K., Pearce, R. and Sanders, G., Improving Estimation of Betweenness Centrality for Scale-Free Graphs.
Incremental Betweenness Centrality
Jamour, F., Skiadopoulos, S. and Kalnis, P., 2017. Parallel Algorithm for Incremental Betweenness Centrality on Large Graphs. IEEE Transactions on Parallel and Distributed Systems.

Matta, J., 2017, November. A Comparison of Approaches to Computing Betweenness Centrality for Large Graphs. In International Workshop on Complex Networks and their Applications (pp. 3-13). Springer, Cham.
Bentert, M., Dittmann, A., Kellerhals, L., Nichterlein, A. and Niedermeier, R., 2018. Towards Improving Brandes' Algorithm for Betweenness Centrality. arXiv preprint arXiv:1802.06701.



  • SCARDONI, G., LAUDANNA, C., TOSADORI, G., FABBRI, F. & FAIZAAN, M. CentiScaPe: Network centralities for Cytoscape.
  • SCARDONI, G., PETTERLINI, M. & LAUDANNA, C. 2009. Analyzing biological network parameters with CentiScaPe. Bioinformatics, 25, 2857-2859. DOI: 10.1093/bioinformatics/btp517 Publisher web site Endnote RIS file
  • FREEMAN, L. C. 1977. A set of measures of centrality based on betweenness. Sociometry, 35-41.
  • Chehreghani, M.H., Bifet, A. and Abdessalem, T., 2017. Efficient Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs. arXiv preprint arXiv:1708.08739.


There are no comment yet.

Add your comment

Sum of    and