Characterising Centralities in Sparse Networks: a Cavity Approach

07 June 2024
3:00 pm - 4:00 pm


CSH Salon


Complexity Science Hub


Characterising Centralities in Sparse Networks: a Cavity Approach

Centrality measures allow us to identify important nodes in networked systems. The Katz centrality of a node is for instance a measure of the node’s importance as far as the flow of information across the network is concerned. For ensembles of 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 a tree-like structure, we show that the Katz centrality of a single instance can be computed recursively in a very fast way and we characterize its probability distribution. Our results help explain the connection between degree and centrality: for sparse networks, centralities follow a multimodal distribution where different peaks correspond to different degrees. This finding suggests that the functionality of empirical networks may be related to nodes with over/under-expressed centrality, and we provide a novel methodology for the efficient identification of such nodes.



Silvia Bartolucci

0 Pages 0 Press 0 News 0 Events 0 Projects 0 Publications 0 Person 0 Visualisation 0 Art


CSH Newsletter

Choose your preference
Data Protection*