Understanding Vulnerability of Communities in Complex Networks

Abstract

In this paper, we study the crucial elements of complex networks, namely nodes, and edges and their properties such as their community structure, which play an important role in dictating the robustness of the network towards structural perturbations. Specifically, we want to identify all vital nodes, which when removed would lead to a large change in the underlying community structure of the network. This problem is extremely important because the community structure of a network allows deep underlying insights into how function of a network and its topology affect each other. Moreover, it even provides a way to condense large graphs into smaller graphs where each community acts as a meta node and hence aids in easier network analysis. If this community structure was to be compromised by either accidental or intentional perturbations to the network, that would make such analysis difficult. Since the problem of identifying such vital nodes is computationally intractable, we propose some heuristics that allow us to find solutions close to the optimal solution. To certify the effectiveness of our approach, we first test these heuristics on small networks, and then move to larger networks to show that we achieve similar results. The results reveal that the proposed approaches are effective to analyze the vulnerability of communities in graphs irrespective of their size and scale. From the application point of view, we show that the proposed algorithm is scalable and can be applied to the information diffusion task to curtail the spread of active nodes which was observed empirically. Additionally, we show the performance of our algorithm through an extrinsic evaluation -- we employ two tasks, like prediction and information diffusion, and show that the effect of our algorithm on these tasks is higher than the other baselines.

References in corpus (31)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Functional cartography of complex metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Detecting the overlapping and hierarchical community structure of complex networks
• Attack vulnerability of complex networks
• Finding statistically significant communities in networks
• CFinder: Locating cliques and overlapping modules in biological networks
• An information-theoretic framework for resolving community structure in complex networks
• An O(m) Algorithm for Cores Decomposition of Networks
• Mixture models and exploratory analysis in networks
• Fuzzy communities and the concept of bridgeness in complex networks
• Detecting highly overlapping community structure by greedy clique expansion
• Weighted network modules
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Community detection and graph partitioning
• Enhancing community detection using a network weighting strategy
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Spectral tripartitioning of networks
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Towards Linear Time Overlapping Community Detection in Social Networks
• Leveraging disjoint communities for detecting overlapping community structure
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks