Closeness centrality is one way of measuring how central a node is in the given network. The closeness centrality measure assigns a centrality value to each node based on its accessibility to the whole network. In real life applications, we are mainly interested in ranking nodes based on their centrality values. The classical method to compute the rank of a node first computes the closeness centrality of all nodes and then compares them to get its rank. Its time complexity is @math , where @math represents total number of nodes, and @math represents total number of edges in the network. In the present work, we propose a heuristic method to fast estimate the closeness rank of a node in @math time complexity, where @math . We also propose an extended improved method using uniform sampling technique. This method better estimates the rank and it has the time complexity @math , where @math . This is an excellent improvement over the classical centrality ranking method. The efficiency of the proposed methods is verified on real world scale-free social networks using absolute and weighted error functions.
studied the correlation of closeness centrality with the local neighborhood volume of the node @cite_25 . The ranking based on local neighborhood volume is named as DACCER (Distributed Assessment of the Closeness CEntrality Ranking) and is highly correlated with closeness centrality ranking in both real world and synthetic networks.
@cite_25
2044141740
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 limited neighborhood around each node, thus not requiring full knowledge of the network topology. We indicate 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 by the entity responsible for calculating the centrality. 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 to the analysis of large complex networks, as indicated in our experimental evaluation using both synthetically generated networks and real-world network traces of different kinds and scales.