title: Two betweenness centrality measures based on Randomized Shortest Paths.
abstract: This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortest paths, but also take into account longer paths depending on an inverse temperature parameter. RSP's have previously proven to be useful in defining distance measures on networks. In this work we study their utility in quantifying the importance of the nodes of a network. The proposed RSP betweenness centralities combine, in an optimal way, the ideas of using the shortest and purely random paths for analysing the roles of network nodes, avoiding issues involving these two paradigms. We present the derivations of these measures and how they can be computed in an efficient way. In addition, we show with real world examples the potential of the RSP betweenness centralities in identifying interesting nodes of a network that more traditional methods might fail to notice.
authors.affiliation: Université catholique de Louvain, ICTEAM/LSM, Place des Doyens 1, 1348 Louvain-la-Neuve, Belgium.|Aalto University, Department of Computer Science, P.O.Box 15400, FI-00076 Aalto, Finland.
authors.forename: Ilkka
authors.initials: I
authors.lastname: Kivimäki
authors.affiliation: Université catholique de Louvain, ICTEAM/LSM, Place des Doyens 1, 1348 Louvain-la-Neuve, Belgium.
authors.forename: Bertrand
authors.initials: B
authors.lastname: Lebichot
authors.affiliation: Aalto University, Department of Computer Science, P.O.Box 15400, FI-00076 Aalto, Finland.
authors.forename: Jari
authors.initials: J
authors.lastname: Saramäki
authors.affiliation: Université catholique de Louvain, ICTEAM/LSM, Place des Doyens 1, 1348 Louvain-la-Neuve, Belgium.
authors.forename: Marco
authors.initials: M
authors.lastname: Saerens
references.citation: Neural Comput. 2009 Aug;21(8):2363-404
references.pmid: 19323635
references.citation: Psychometrika. 1966 Dec;31(4):581-603
references.pmid: 5232444
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 May;71(5 Pt 2):056103
references.pmid: 16089598
references.citation: Phys Rev Lett. 2001 Dec 31;87(27 Pt 1):278701
references.pmid: 11800921
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Oct;78(4 Pt 2):046110
references.pmid: 18999496
references.citation: Neural Netw. 2017 Jun;90:90-111
references.pmid: 28458082
references.citation: J Anim Ecol. 2016 Jan;85(1):32-42
references.pmid: 25950737
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Jul;64(1 Pt 2):016132
references.pmid: 11461356