Distributed assessment of the closeness centrality ranking in complex networks

Abstract

We propose a method for the Distributed Assessment of the Closeness CEntrality Ranking (DACCER) in complex networks. DACCER computes centrality based only on localized information restricted to a given neighborhood around each node, thus not requiring full knowledge of the network topology. We show that the node centrality ranking computed by DACCER is highly correlated with the node ranking based on the traditional closeness centrality, which requires high computational costs and full knowledge of the network topology. This outcome is quite useful given the vast potential applicability of closeness centrality, which is seldom applied to large-scale networks due to its high computational costs. Results indicate that DACCER is simple, yet efficient, in assessing node centrality while allowing a distributed implementation that contributes to its performance. This also contributes to the practical applicability of DACCER in the analysis of large-scale complex networks, as we show using in our experimental evaluation both synthetically generated networks and traces of real-world networks of different kinds and scales.