Bartolucci, Silvia;
Caccioli, Fabio;
Caravelli, Francesco;
Vivo, Pierpaolo;
(2024)
Distribution of centrality measures on undirected random networks via the cavity method.
Proceedings of the National Academy of Sciences
, 121
(40)
, Article e2403682121. 10.1073/pnas.2403682121.
Preview |
PDF
Distribution of centrality measures on undirected random networks via the cavity method.pdf - Published Version Download (6MB) | Preview |
Abstract
The Katz centrality of a node in a complex network is a measure of the node’s importance as far as the flow of information across the network is concerned. For ensembles of locally tree-like undirected random graphs, this observable is a random variable. Its full probability distribution is of interest but difficult to handle analytically because of its “global” character and its definition in terms of a matrix inverse. Leveraging a fast Gaussian Belief Propagation-Cavity algorithm to solve linear systems on tree-like structures, we show that i) the Katz centrality of a single instance can be computed recursively in a very fast way, and ii) the probability P(K ) that a random node in the ensemble of undirected random graphs has centrality K satisfies a set of recursive distributional equations, which can be analytically characterized and efficiently solved using a population dynamics algorithm. We test our solution on ensembles of ErdősRényi and Scale Free networks in the locally tree-like regime, with excellent agreement. The analytical distribution of centrality for the configuration model conditioned on the degree of each node can be employed as a benchmark to identify nodes of empirical networks with over- and underexpressed centrality relative to a null baseline. We also provide an approximate formula based on a rank-1 projection that works well if the network is not too sparse, and we argue that an extension of our method could be efficiently extended to tackle analytical distributions of other centrality measures such as PageRank for directed networks in a transparent and user-friendly way.
| Type: | Article |
|---|---|
| Title: | Distribution of centrality measures on undirected random networks via the cavity method |
| Location: | United States |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1073/pnas.2403682121 |
| Publisher version: | https://doi.org/10.1073/pnas.2403682121 |
| Language: | English |
| Additional information: | © 2024 the Author(s). Published by PNAS. This open access article is distributed under Creative Commons Attribution License 4.0 (https://creativecommons.org/licenses/by/4.0/). |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10204212 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
