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|2 - m|V|k2), 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|2 + 1/2|V|3/2log|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.

Meeting Name

IEEE 40th Conference on Local Computer Networks, LCN 2015 (2015: Oct. 26-29, Clearwater Beach, FL)


Computer Science

Keywords and Phrases

Algorithms; Costs; Knowledge management; Population dynamics; Structural properties; Betweenness centrality; Community detection; Community detection algorithms; Computational costs; Degree distributions; Large-scale network; Network structures; Real-world networks; Computer networks

International Standard Book Number (ISBN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2015 IEEE Computer Society, All rights reserved.

Publication Date

01 Oct 2015