Examining indicators of complex network vulnerability across diverse attack scenarios

Abstract

Complex networks capture the structure, dynamics, and relationships among entities in real-world networked systems, encompassing domains like communications, society, chemistry, biology, ecology, politics, etc. Analysis of complex networks lends insight into the critical nodes, key pathways, and potential points of failure that may impact the connectivity and operational integrity of the underlying system. In this work, we investigate the topological properties or indicators, such as shortest path length, modularity, efficiency, graph density, diameter, assortativity, and clustering coefficient, that determine the vulnerability to (or robustness against) diverse attack scenarios. Specifically, we examine how node- and link-based network growth or depletion based on specific attack criteria affect their robustness gauged in terms of the largest connected component (LCC) size and diameter. We employ partial least squares discriminant analysis to quantify the individual contribution of the indicators on LCC preservation while accounting for the collinearity stemming from the possible correlation between indicators. Our analysis of 14 complex network datasets and 5 attack models invariably reveals high modularity and disassortativity to be prime indicators of vulnerability, corroborating prior works that report disassortative modular networks to be particularly susceptible to targeted attacks. We conclude with a discussion as well as an illustrative example of the application of this work in fending off strategic attacks on critical infrastructures through models that adaptively and distributively achieve network robustness.

Figure 1

A schematic representation of the approach adopted in this study, where the goal is to pinpoint the topological properties or indicators that explain the robustness or vulnerability of complex networks to diverse network attack models.

Figure 2

Partial least squares discriminant analysis (DA) coefficients calculated from the features consisting of all network indicators and labels gauging the number of link removals to make the largest connected component half its original size.

Figure 3

Measuring the percolation of the network using different growing models. Edges are weighted and added based on RND, PA, BPA, CPA, CcPA, and iPA models.

Figure 4

Node and edge robustness ($R_n,R_e$) of two sample networks (facebook 0 and arenas-email). Each network is attacked by removing (10%, 20%, 30%, 40%, and 50%) of the nodes, using high (1- degree, 2- betweenness, 3- closeness, and 4- clustering coefficient) values.

Figure 5

Example of network attack and reconstruction on a complete 30-node network: assortativity-based reconstruction after (a) link removal to make the number of largest connected component (LCC) exceed 1 (b) link removal to make the size of LCC half with respect to original networks; combined reconstruction based on assortativity and modularity (c) link removal to make the number of LCC exceed 1 and (d) link removal to make the size of LCC half with respect to original networks.