Fast Estimation of Closeness Centrality Ranking
MetadataShow full item record
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 O(n · m + n), where n represents total number of nodes, and m 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 O(α · m) time complexity, where α = 3. We also propose an extended improved method using uniform sampling technique. This method better estimates the rank and it has the time complexity O(α · m), where α ≈ 10-100. 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.
The article of record as published may be found at http://dx.doi.org/10.1145/3110025.3110064
Showing items related by title, author, creator and subject.
Saxena, Akrati; Gera, Ralucca; Iyengar, S.R.S. (2017-06-07);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 ...
Roginski, Jonathan W. (Monterey, CA; Naval Postgraduate School, 2018-06);This research provides an innovative approach to identifying the influence of vertices on the topology of a graph by introducing and exploring the neighbor matrix and distance centrality. The neighbor matrix depicts the ...
Castro, Victor G. (Monterey, California: Naval Postgraduate School, 2017-06);The Global Combat Support System-Marine Corps (GCSS-MC) system enables the logistics and supply chain management system for the United States Marine Corps. This system allows leaders, operators, maintainers, and suppliers ...