Skip to main content
Leveraging Network Structure in Centrality Evaluation of Large Scale Networks
Proceedings of the IEEE 40th Conference on Local Computer Networks (2015, Clearwater Beach, FL)
  • Sima Das
  • Sajal K. Das, Missouri University of Science and Technology

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
Citation Information
Sima Das and Sajal K. Das. "Leveraging Network Structure in Centrality Evaluation of Large Scale Networks" Proceedings of the IEEE 40th Conference on Local Computer Networks (2015, Clearwater Beach, FL) (2015) p. 579 - 586
Available at: