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.
@cite_24: This paper develops a quantitative method to measure the vulnerability of community structure with emphasis on both internal and external connectivity characteristics of the community. In particular, the number of links between communities and the strength of links connecting two communities are considered as external factors, while the connection density, the degree of gateway nodes, as well as the strength of links within each community are treated as internal factors. A non-linear weighted function is used to combine the internal factors with external factors. Then the developed method is used to illustrate the vulnerability analysis of community structure of a power transmission grid, a karate club network, and an air transportation network. The results reveal that the proposed measure is effective in differentiating the vulnerability level of community structure in a variety of networks.
@cite_27: Many networks contain community structures, or collections of densely connected nodes with sparse connections to other dense groups in the network. Communities may coalesce for a number of reasons, including friendships in a social network, physical connections in an infrastructure network, or spatial distribution in a neighborhood. Several approaches have been proposed to identify communities and compare the partition of networks into communities. This work explores community structures from the perspective of their resilience, or their ability to withstand degradation in network performance and recover to a desired level of network performance. In this context, network performance is defined as the similarity of a network partition (or the characterization of the network into community structures) formed after the disconnection of one or more links to the initial partition. This work provides an approach to measure how the initial set of community structures survive after a disruption and how these structures return after restoration commences. The approach is illustrated with an electric power network case study.
@cite_20: A common theme in analysis and evaluation of network-based critical infrastructure is the assessment of system vulnerability. Graph theoretic, simulation, and optimization-based techniques have played a significant role in examining potential network vulnerabilities given the insights they can provide for mitigating facility loss and prioritizing fortification efforts. Central to these approaches is the concept of facility (arcâ€”node) importance or criticality to system survivability. Assessments of network vulnerability can dramatically differ based on how facility importance is characterized. In this review, various approaches for assessing facility importance and network vulnerability are examined. The key differences in these approaches are the ways in which a facility's role in maintaining network operability is evaluated given arcâ€”node disruption. Comparative results suggest significant differences exist among measures of facility importance and network performance. Furthermore, the subsequent incongruities in these measures and their implications need to be clearly understood to support interdiction risk and vulnerability assessment for critical infrastructures.
@cite_27 proposed an approach where the resilience of the community structure is quantified by first introducing disruption in the original network and measuring the change in the community structure temporally i.e., after the disconnection and during the restoration process. @cite_20 provide a review of various approaches that make use of the facility importance concept to understand the system wide vulnerability. @cite_24 proposed a new vulnerability metric where they considered a combination of external and internal factors such as connection density etc. These methods allow us to quantify the vulnerability of a community, but does not provide us with a set of nodes that contribute to the vulnerability of the community itself.