Leveraging Network Structure in Centrality Evaluation of Large Scale Networks
Abstract
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.
Recommended Citation
S. Das and S. 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), pp. 579 - 586, IEEE Computer Society, Oct 2015.
The definitive version is available at https://doi.org/10.1109/LCN.2015.7366373
Meeting Name
IEEE 40th Conference on Local Computer Networks, LCN 2015 (2015: Oct. 26-29, Clearwater Beach, FL)
Department(s)
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)
978-1-4673-6770-7
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2015 IEEE Computer Society, All rights reserved.
Publication Date
01 Oct 2015
