Leveraging Network Structure in Centrality Evaluation of Large Scale Networks

Evaluating influential nodes is one of the fundamental problems in large scale networks having wide range of applications. The centrality metric, in particular betweenness centrality plays a significant role in ranking influential nodes. Existing exact algorithms for evaluating betweenness centrality metric consider the entire network and hence incur high computational cost. In this paper, we reduce computational cost by leveraging network structural properties. We propose a community detection algorithm that uses right-skewed nature of degree distribution with incremental accumulation and semi-local optimal node selection giving computational cost O (| V | ² - m | V | k ² ), where k , | V | and m represent average degree, number of vertices and modularity respectively. Additionally, we use predefined upper bound ( O (√| V |)) on the number and size of communities to propose an algorithm for evaluating exact betweenness centrality indices that exploit the dense intra-modular and sparse intermodular connections of large scale networks, leading to the computational cost of O (| V | ² + 1/2| V | ^3/2 log | V |). We validate our algorithms using real world networks. The computational cost incurred due to community detection and betweenness centrality evaluation holds irrespective of graph density and out performs existing exact algorithms. To the best of our knowledge this is the first work to leverage structural properties in community detection and exact betweenness centrality evaluation over large scale networks.