Centrality Measures for Networks with Community Structure

Abstract

Understanding the network structure, and finding out the influential nodes is a challenging issue in the large networks. Identifying the most influential nodes in the network can be useful in many applications like immunization of nodes in case of epidemic spreading, during intentional attacks on complex networks. A lot of research is done to devise centrality measures which could efficiently identify the most influential nodes in the network. There are two major approaches to the problem: On one hand, deterministic strategies that exploit knowledge about the overall network topology in order to find the influential nodes, while on the other end, random strategies are completely agnostic about the network structure. Centrality measures that can deal with a limited knowledge of the network structure are required. Indeed, in practice, information about the global structure of the overall network is rarely available or hard to acquire. Even if available, the structure of the network might be too large that it is too much computationally expensive to calculate global centrality measures. To that end, a centrality measure is proposed that requires information only at the community level to identify the influential nodes in the network. Indeed, most of the real-world networks exhibit a community structure that can be exploited efficiently to discover the influential nodes. We performed a comparative evaluation of prominent global deterministic strategies together with stochastic strategies with an available and the proposed deterministic community-based strategy. Effectiveness of the proposed method is evaluated by performing experiments on synthetic and real-world networks with community structure in the case of immunization of nodes for epidemic control.

30 pages, 4 figures. Accepted for publication in Physica A. arXiv admin note: text overlap with arXiv:1411.6276

References in corpus (9)

• Uncovering the overlapping community structure of complex networks in nature and society
• Benchmark graphs for testing community detection algorithms
• Efficient Immunization Strategies for Computer Networks and Populations
• Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design
• Comparative Evaluation of Community Detection Algorithms: A Topological Approach
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Nonlinear spread of rumor and inoculation strategies in the nodes with degree dependent tie strength in complex networks
• Fast Multi-Scale Community Detection based on Local Criteria within a Multi-Threaded Algorithm

Cited by in corpus (13)

• On community structure in complex networks: challenges and opportunities
• Centrality in Modular Networks
• Measuring Node Contribution to Community Structure with Modularity Vitality
• Characterizing the Interactions Between Classical and Community-aware Centrality Measures in Complex Networks
• Comparative evaluation of community-aware centrality measures
• A blockchain based Secure and Trusted framework for Information Propagation on Online Social Networks
• Interplay Between Hierarchy and Centrality in Complex Networks
• Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure
• Group based Centrality for Immunization of Complex Networks
• Comparing Community-aware Centrality Measures in Online Social Networks
• Influence-based Community Partition with Sandwich Method for Social Networks
• Identifying Influential Nodes Using Overlapping Modularity Vitality
• Being Central on the Cheap: Stability in Heterogeneous Multiagent Centrality Games