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.