Title: Algorithms for fast estimation of social network centrality measures

Authors: Ashok Kumar; R. Chulaka Gunasekara; Kishan G. Mehrotra; Chilukuri K. Mohan

Addresses: Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY 13244, USA ' Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY 13244, USA ' Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY 13244, USA ' Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY 13244, USA

Abstract: Centrality measures are extremely important in the analysis of social networks, with applications such as the identification of the most influential individuals for effective target marketing. Eigenvector centrality and PageRank are among the most useful centrality measures, but computing these measures can be prohibitively expensive for large social networks. This paper explores multiple approaches to improve the computational effort required to compute relative centrality measures. First, we show that small neural networks can be effective in fast estimation of the relative ordering of vertices in a social network based on these centrality measures. Then, we show how network sampling can be used to reduce the running times for calculating the ordering of vertices; degree centrality-based sampling reduces the running time of the key node identification problem. Finally, we propose the approach of incremental updating of centrality measures in dynamic networks.

Keywords: social network; centrality; eigenvector centrality; PageRank; network sampling; incremental updating.

DOI: 10.1504/IJBDI.2018.094971

International Journal of Big Data Intelligence, 2018 Vol.5 No.4, pp.216 - 227

Received: 22 Jun 2016
Accepted: 15 Feb 2017
Published online: 28 Sep 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article