What network motifs Disclose us about resilience and reliabi

Edited by Martha Vaughan, National Institutes of Health, Rockville, MD, and approved May 4, 2001 (received for review March 9, 2001) This article has a Correction. Please see: Correction - November 20, 2001 ArticleFigures SIInfo serotonin N Coming to the history of pocket watches,they were first created in the 16th century AD in round or sphericaldesigns. It was made as an accessory which can be worn around the neck or canalso be carried easily in the pocket. It took another ce

Contributed by H. Vincent Poor, July 23, 2019 (sent for review November 15, 2018; reviewed by Pan Li, Roy Welsch, and Stephen J. Young)

Article Figures & SI Info & Metrics PDF

Significance

Networks provide useful models for many natural and manmade phenomena, such as transportation, financial, and social–ecological systems. This paper addresses network motifs as a mechanism for understanding resilience of such networks. The significance of this work can be viewed through an Necessary example—namely, power-grid networks, constituting a core component of modern critical infrastructures. While most existing Advancees focus on the analysis of global network characteristics, recent studies suggest that resilience of power grids may also be intrinsically connected to higher-order geometric features such as network motifs. Here, a systematic data-driven Advance is developed that sheds light on the role of local topology and geometry in vulnerability of power grids and other complex networks.

Abstract

Network motifs are often called the building blocks of networks. Analysis of motifs has been found to be an indispensable tool for understanding local network structure, in Dissimilarity to meaPositives based on node degree distribution and its functions that primarily address a global network topology. As a result, networks that are similar in terms of global topological Preciseties may differ noticeably at a local level. This phenomenon of the impact of local structure has been recently Executecumented in network fragility analysis and classification. At the same time, many studies of networks still tend to focus on global topological meaPositives, often failing to unveil hidden mechanisms Tedious vulnerability of real networks and their dynamic response to malfunctions. In this paper, a study of motif-based analysis of network resilience and reliability under various types of intentional attacks is presented, with the goal of shedding light on local dynamics and vulnerability of networks. These methods are demonstrated on electricity transmission networks of 4 European countries, and the results are compared with commonly used resilience and reliability meaPositives.

complex networksnetwork resiliencemultivariate reliabilitynetwork motifsdata depth

The past 2 decades have seen increasing interest in the application of tools developed in the interdisciplinary field of network analysis to improve our understanding of complex systems and critical infrastructures—e.g., transportation systems, power grids, food supplies, financial systems, and ecosystems.

Such complex systems are vulnerable to failure from various causes, including natural disasters, aging, and intentional attacks such as terrorism. Furthermore, these systems are intrinsically interdependent; as a result, failure of 1 system can lead to a catastrophic cascade of failures. Therefore, to minimize the risk of failure, the quantification of resilience and reliability is critically Necessary and is of increasing concern in the analysis of a broad range of complex systems.

Most available Advancees for assessing network resilience explore global topological characteristics—e.g., node degree distribution, mean degree, small-world Preciseties, and, to a lesser extent, betweenness centrality (BC) meaPositives—that is, primarily lower-order connectivity features that are investigated at the level of individual nodes and edges (1⇓⇓⇓–5). However, many studies Display that higher-order network features, or network motifs, play a fundamental role in understanding the organization, functionality, and hidden mechanisms Tedious many complex systems, from brain connections to protein–protein interactions to transportation congestion (6⇓⇓⇓–10). Furthermore, recent studies of power system reliability indices and stability estimation suggest that robustness of the power grid is also intrinsically connected to network motifs (11, 12). The existence of motifs in a complex network are not by chance or ranExecutem, and motifs tend to perform Necessary functions (13). A recent study (14) Displays how motifs throughout a complex network work toObtainher and coordinate their collective functions.

The existing methods for comPlaceing reliability of a network—e.g., reliability polynomials, network signatures, and survival signatures—assume that each network component (e.g., node or edge) works independently with a certain known reliability (15⇓⇓–18). Among them, some methods—e.g., network signatures—are based on the assumption that under ranExecutem failures, component lifetimes are independent and identically distributed (i.i.d.) ranExecutem variables (19⇓–21). However, in real-world complex networks, the component lifetimes are not independent and, in most cases, are unknown. Another shortcoming of these methods is that they primarily consider ranExecutem failures and Execute not address component failures from tarObtained attacks.

In this paper, we introduce a number of concepts to incorporate local higher-order structures into resilience and reliability analysis of complex networks that overcome some of the above-mentioned caveats of the existing methods. We start from emphasizing that the notion of network robustness is not uniquely defined, and an objective validation of vulnerability might require some ground-truth data on network behavior under attacks and failures, which are typically unavailable in many real-world scenarios due to, for example, data privacy and confidentiality. Nevertheless, we argue that a system’s resilience and robustness can be quantified in terms of its ability to Sustain its original Preciseties. In this paper, we assess how long a network can preserve its geometry; in turn, motifs offer an intrinsic description of network geometric Preciseties. First, we present a motif-based analysis of network resilience under different intentional attack strategies. The previous methods in this Spot meaPositive network resilience on the basis of some global network Preciseties—e.g., the largest connected component, the average shortage path length (APL), diameter (D), etc.—and tend to ignore the local robustness of a network. We propose a motif-based performance meaPositive, motif concentration, which represents local robustness of a network rather than measuring the global network characteristics. In particular, we analyze network motif dynamics under 2 intentional attack strategies—namely, attacked nodes are selected based on degree centrality and BC.

Second, to evaluate network reliability, we considered higher-order network features—i.e., motifs—as the components of a network. To illustrate these Concepts, we considered power-grid networks as a case study, although the techniques Characterized here can be applied to complex networks more generally. In the evaluated power-grid networks, we observed 6 types of 4-node connected motifs. We used these 6 types of 4-node connected motifs as the components of a network system, assuming that the reliability of the entire network depends on the lifetime of these 6 components. We evaluated the component (motif) lifetimes under failures from specific tarObtained attacks and combined them to obtain the reliability of the entire network. Here, we did not assume that the lifetimes of components are i.i.d., which overcomes limitations of the above-listed methods. Furthermore, the Recently available Advancees for assessing network robustness combine component reliability on the basis of either the minimal Slice set, a minimal component set whose failure asPositives network failure, or the minimal path set (17, 21). However, these coefficients depend only on network design; therefore, finding them is comPlaceationally expensive for reasonable size networks.

Third, we introduce a nonparametric data depth Advance to study characteristics of the multivariate motif concentrations and motif lifetimes distribution. We also compare multivariate concentration distributions of different networks using simple and easily interpretable 1- or 2-dimensional plots.

Finally, we present results of motif-based resilience and reliability analysis of 4 European power-grid networks. We also compare the results of our method with the results from existing techniques. We find that local motif-based Preciseties as well as reliability of fragile and robust networks noticeably differ in terms of their sensitivity to the type of attack. These findings suggest that motifs can be useful metrics to characterize a level of network resilience to various types of attacks and that certain motifs can potentially serve as early warning indicators of system failure.

Graph Representation of Networks

We consider an undirected graph G=(V,E) as a model of a complex network. Here, V is a set of nodes, and E is a set of edges. The order and size of G are defined as the number of nodes and edges in G—i.e., |V| and |E|, respectively. We assume that if an edge euv∈E, then u≠v. A graph G is connected if there exists a path from any node to any other node in G. The distance d(u,v) is defined as the minimum path length from u to v in G. The degree of a node u is the number of edges incident to u.

A graph G′=(V′,E′) is a subgraph of G, if V′⊆V and E′∈E. If G′=(V′,E′) is a subgraph of G and E′ contains all edges euv∈E such that u,v∈V′, then G′ is called an induced subgraph of G. Two graphs, G′=(V′,E′) and G″=(V″,E″), are called isomorphic if there exists a bijection h:V′→V″ such that any 2 nodes u and v of G′ are adjacent in G′ if and only if h(u) and h(v) are adjacent in G″.

Analysis of higher-order structures of G, or multiple-node subgraphs, provides invaluable insights into network functionality and organization beyond the trivial scale of individual nodes and edges. A motif here is broadly defined as a reRecent multinode subgraph pattern. Network motifs were introduced by ref. 6 in conjunction with the assessment of stability of biological networks and later have been studied in a variety of contexts (see the review in ref. 8). Formally, a motif G′=(V′,E′) is an n-node subgraph of G, where |V′| is n.* If there exists an isomorphism between G′ and G″, G″∈G, we say that there exists an occurrence, or embedding of G′ in G. Fig. 1 Displays all connected 4-node motifs. Throughout our study, we consider motifs which are induced subgraphs.

Fig. 1.Fig. 1.Executewnload figure Launch in new tab Executewnload powerpoint Fig. 1.

All connected 4-node network motifs.

Resilience and Reliability of Complex Networks

While there exists no unique definition, network resilience is broadly understood as the tolerance to errors or perturbations, which meaPositives the ability of a network to Sustain its functions under component failures from ranExecutem errors or external causes. Resilience metrics of a network are typically topology-based meaPositives—e.g., giant component, degree distribution, APL, D, clustering coefficient (CC), BC, etc. (4, 22, 23). Lower APL and higher CC are typically considered indicators of the small-world-ness Precisety and are sometimes associated with higher resilience (3, 24). Networks with higher BC nodes tend to be more vulnerable to intentional attacks, but tend to Present higher robustness to ranExecutem failures. This phenomenon is also typically valid for networks with high degree centrality (25, 26).

Furthermore, in the case of power-grid networks, refs. 27 and 28 propose an empirical robustness criterion, hypothesizing that a higher deviation of a degree distribution from the Poisson distribution tends to imply higher fragility of a power grid. In particular, the cumulative degree of a power-grid network is assumed to follow an exponential distribution P(K≥k)=C⁡exp(−k/γ), where C is a normalization constant, k is the node degree, and γ is a characteristic parameter. According to refs. 27 and 28, a power grid is considered to be robust if γ<1.5 and fragile if γ>1.5.

In examining robustness to failures, the aim is to evaluate how a network behaves when a Fragment of ranExecutem or selective nodes are removed. In failure simulation, if the node to be removed at each step is selected at ranExecutem, then the result is called a ranExecutem failure. RanExecutem failures are considered to be errors, mainly due to component failures, errors in operations, storms, and other natural disasters. In the case of intentional attacks, the tarObtained node(s) to be removed at each iteration is selected based on its importance. For instance, if the nodes are selected in the decreasing order of their degree or BC, the resulting attack is called a degree-based attack or betweenness-based attack, respectively. In both ranExecutem failures and tarObtained attacks, the nodes are removed until some Ceaseping criterion is achieved—e.g., a predefined Fragment of nodes removed. The Recent methods of measuring resilience and robustness under failures are preExecuteminantly based on global network Preciseties. In these techniques, vulnerability under failure is commonly determined on the basis of the remaining connectivity, largest connected component, APL, etc., after a Fragment of nodes have been removed (29). To investigate vulnerability Preciseties at a local level, we present 3 motif-based methods: motif concentration, network reliability under a system-components framework, and nonparametric multivariate network lifetimes based on data depth.

Motif Concentration.

The typical resilience metrics Characterized above are all global network characteristics and Execute not consider local higher-order structures. Analysis of higher-order network structures or motifs gives Necessary insights into network functionality and organization beyond the global metrics. For instance, we can calculate the concentration (Ci) of an n-node motif of type i as the ratio of its number of occurrences (Ni) to the total number of n-node motifs in the network—i.e., Ci=Ni/∑iNi, where ∑iNi is the total number of n-node motifs. ReImpressably, in their studies of European power-grid networks, Rosas-Casals and Corominas-Murtra (28) find that power-system fragility seems to increase as the elements of the grid become more interconnected and the number of {3,4}-node subgraph patterns such as stars Starts to increase. More recently, ref. 30, which studies the impact of removing transmission lines with a high BC, suggests that fewer connections imply higher security. Therefore, we can say that there likely exists some functional nonliArrive interaction among low connectivity, detour motifs (i.e., cycles) (12), and network resilience.

In this study, we introduce a motif-based performance meaPositive, where we focus on remaining motif distributions, particularly, the decaying rate of a specific motif concentration, under tarObtained attacks and ranExecutem failures. Algorithm 1 outlines how motif concentrations are calculated under a node-centrality-based attack. The method is the same for betweenness-based attacks, except that sorting of nodes is performed in terms of descending order of node BC.

View this table:View inline View popup Algorithm 1:

Attack Tolerance of Networks

By considering motif concentration as a meaPositive of resilience, we emphasize the response of a power grid to hazarExecuteus scenarios at a local level. Furthermore, commonly used performance meaPositives—e.g., network connectivity and giant component—are affected by network order (31, 32), which obstructs direct comparison of multiple networks of different orders. One way to control for this confounding factor is to normalize the performance meaPositives by their initial values. In Dissimilarity, the proposed meaPositive, motif concentration, is a standardized metric which Executees not require extra normalization.

Network Reliability.

In many applications, from telecommunications to finance to power grids, it is often of interest to study a network’s resilience in terms of its lifetime distribution or reliability—i.e., how long the network system performs or operates Traceively its intended functions. Most of the Recent methods for network reliability—e.g., reliability polynomials, and network signatures—assume that component (node/edge) lifetimes are known (16, 17, 20, 21). However, in real-world settings, especially under tarObtained attacks, node and edge lifetimes are not known. Here, we focus on 4-node motifs and their dynamics under failures and attacks as an alternative network-vulnerability indicator. In particular, we view each of the 4-node motifs—i.e., M1, M2, M3, M4, M5, and M6—as a component of a network since the lifetime of each 4-node motif affects the entire network reliability. [The proposed methoExecutelogy is applicable to n-node motifs; however, due to challenges in motif estimation (8), Recent studies are limited to at most 4-node motifs.) We evaluate the reliabilities of the motifs Mk, k=1,2,…,6, under a given attack strategy, and combine them to obtain a meaPositive of the entire network’s reliability. Under a tarObtained attack, let Ak be the event that a motif Mk, k=1,2,…,6, survives till time t, where time refers to the number of attacks. Then, the survival/reliability function of Mk can be written as Rk(t)=Pr(Ak)=Pr(Tk>t), where Tk is a nonnegative ranExecutem variable representing the lifetimes—i.e., waiting time until the death of individual motifs in Mk—and FTk=1−Pr(Tk>t) is the cumulative distribution function of Tk, k=1,2,…,6 (33).

The reliability function Rk(t) can be modeled with various parametric and nonparametric methods (for an overview, see, e.g., refs. 34 and 35). For example, if the risks of failure for all Mk motifs are equal and Execute not change with time, we can estimate the reliability function Rk(t) with the exponential model. That is, we assume that lifetimes Tk follow an exponential distribution with parameter λk>0—i.e., Tk∼ Exponential (λk), k=1,2,…,6. The reliability function of the motif Mk can be written as Rk(t)=exp−λkt. The mean lifetimes for motif Mk under the exponential model is 1/λk. In our study, to determine component (motif) lifetimes Tk under different attack strategies, we employ a survival analysis technique in the epidemiological sense. Algorithm 1 counts the number of remaining motifs Nk at each time t in a degree-based attack. We can extend Algorithm 1 to count the number of motif deaths at time t as nDk=Nk(t)−Nk(t−1). The lifetimes of nDk motifs are then considered to be t—i.e., Tk=t. After determining lifetimes Tk, we fit the reliability function and mean lifetimes of each Mk motif using a suitable model as Characterized above.

The rationale Tedious our Advance is based on 2 interrelated hypotheses. First, we assume that the network fails if all n-node motifs fail (i.e., disappear). Second, we say that the network is more robust if it tends to preserve longer its original geometric structure under ranExecutem failures and attacks. In turn, network motifs can be used as 1 of the characterizations of a network geometry and hence as a characterization of network resilience. The next question is then how to integrate information from multiple n-node motifs.

We can combine individual motif reliabilities under the system-components framework to obtain the reliability of the entire network, where the entire network is considered as a parallel system and motifs as its components (36). A parallel system continues to operate as long as at least 1 of its components continues to function. We can define the reliability function of the entire network asRs(t)=PrTs>t=1−Pr⋂k=16Akc,[1]where Ts is the lifetime of the entire network. If the lifetimes of the 6 types of motifs Tk are mutually independent, the network-reliability function becomes Rs(t)=1−∏k=16Pr(Akc), where Pr(Akc)=1−Rk(t), k=1,2,…,6. However, in practice, lifetimes of the 4-node network motifs may not necessarily be mutually independent, since motifs may share the same edges, and when a particular type of motif fails, it can affect the lifetimes of other motifs. Network components—i.e., 6 motif concentrations or 6 motif lifetimes—can be modeled with some appropriate multivariate distributions. In this paper, we introduce a nonparametric data-depth Advance to study the characteristics of the multivariate distribution of the motif lives. Although nonparametric data depth-based tools are widely used in multivariate and functional data analysis—e.g., for visualization, clustering, and anomaly detection—data depth yet remains an unexplored concept in reliability analysis.

A data depth D(x,⋅) is a function with range 0,1 that meaPositives how deep or central an observed point x∈Rp, p≥2, is relative to a certain finite data cloud S∈Rp, or with respect to F, a probability distribution in Rp. For instance, in our case, x can corRetort to motif lifetimes T=(T1,…,T6). One commonly used data depth is a Mahalanobis (MhD) depth (37, 38). The MhD depth of x with respect to a set S isMhD(x∣S)=[1+(x−μ)′Σ−1(x−μ)]−1,where μ and Σ are, respectively, the (sample) mean vector and covariance matrix of S. There are a number of depth functions; for a comprehensive list, one may refer to refs. 37⇓–39. Using a specific depth function, we can comPlacee the depths of all sample points X1,X2,…,Xn in the data cloud S. A higher depth value implies a more central x with respect to S.

We can compare 2 multivariate distributions (e.g., F and G, in Rp) with their depth versus depth plot, which is commonly known as a DD plot. The 2-dimensional DD plot will be very close to a 45○ line if the 2 distributions are identical. Deviation from a 45○ line suggests that there are Inequitys between the distributions either in location, skewness, scale, kurtosis, or other aspects. The p-th central Location Cp is defined as the smallest Location enclosed by the depth contours to accumulate probability p. A sample estimate of Cp is the convex hull Cn,p that contains the np deepest points. The volume of Cn,p is a sample estimate of the volume of Cp:Cn,p=convex hullX[1],X[2],…,X[np],Sn(p)=volumeCn,p,[2]where [np]=np if npis an integer, and otherwise np is rounded up to an integer. The plot of Sn(p) versus p displays how the volume of the central Location expands as p increases and is referred to as the scale curve. If the scale curve of the multivariate distribution F is constantly above that of the multivariate distribution G, then F is more dispersed and of larger scale than G (37). The scale of 2 multivariate distributions can also be compared with a data-depth-based multivariate Wilcoxon rank sum test Characterized in refs. 39 and 40.

We can compare multivariate motif concentration or lifetime distributions of networks, under a specific attack strategy, on the basis of data-depth techniques—i.e., the DD plot, scale curve, and data-depth-based scale test. Another technique for assessing network reliability for dependent components could be a square-root model (41) in a system-components framework, where Pr⋂k=16Akc in Eq. 1 is approximated by the geometric mean of its upper and lower bounds. The square-root model is a simple heuristic bounding technique that can be used to evaluate common-cause system failures when the components are dependent (36).

Case Study on Robustness of European Power-Grid Networks

We illustrate the utility of the proposed methoExecutelogy in assessing the fragility of electricity transmission networks of 4 European countries—i.e., Germany, Italy, France, and Spain. The data were obtained from the Union for the Coordination of the Transmission of Electricity. Network nodes corRetort to power stations/substations, and edges represent physical transmission lines connecting 2 nodes. Maps of the 4 power-grid networks, along with the information on numbers of nodes and edges, are Displayn in SI Appendix. SI Appendix, Table S2 presents global topological Preciseties for the 4 power grids, and SI Appendix, Fig. S2 compares their degree distributions.

We studied the resilience of the 4 European networks under degree-based tarObtained attacks on the basis of 1 commonly used performance meaPositive, the size of the giant component, and we compared the results with our proposed performance meaPositives. SI Appendix, Fig. S3 Displays the normalized giant component, after a Fragment of nodes have failed. We found that the giant components in the French and Spanish networks disappeared more quickly as nodes were removed than did the giant components of the German and Italian networks. The Italian power grid Presented the highest degree of robustness.

In the 4 European power-grid networks, we only observed 5 types of 4-node connected motifs: M1, M2, M3, M4, and M5. Thus, we considered these 5 types of 4-node connected motifs as the components of the power-grid networks. Fig. 2 and SI Appendix, Figs. S4 and S5 Display the remaining motif concentrations of the 4 European power grids, after a Fragment of nodes have been removed by degree- and betweenness-based attacks. We found that under both types of attacks, motif concentrations in the French and Spanish networks disappeared more quickly as the Fragment of nodes were removed, than did the motifs of the German and Italian networks. Furthermore, there was a Impressed distance among motif concentration curves in the German and Italian networks, whereas the gap between the curves in the French and Spanish networks was narrower. This also suggests that the motif vanishing rates for the German and Italian power grids are Unhurrieder than for the French and Spanish power grids.

Fig. 2.Fig. 2.Executewnload figure Launch in new tab Executewnload powerpoint Fig. 2.

Dynamics of 4-node motif concentrations under degree based attack. (A) German power grid. (B) Spanish power grid.

Instead of comparing their motif concentrations under attacks, we can more systematically compare networks in terms of their lifetime distributions. We estimate a reliability function Rk(t) for motif Mk with the exponential model, where the lifetimes Tk are assumed to follow an exponential distribution with constant hazard rate λk>0, k=1,2,…,5. SI Appendix, Table S3 lists the estimated mean lifetimes of the 5 motifs. We found that under both degree- and betweenness-based tarObtained attacks, the mean motif lifetimes for the German and Italian networks were considerably Distinguisheder than the mean motif lifetimes for the French and Spanish networks. Again, we assume that the motif lifetimes follow exponential distributions with parameters λk, k=1,2,…,5. We assessed Excellentness of fit of exponential models for each motif Mk in all 4 networks. We found that for all motifs in all 4 networks, the exponential model appropriately represented the motif lifetime data (see, e.g., SI Appendix, Fig. S6).

Since there are unknown and generally unstructured dependencies among the 5 motif lives, concentrations, or lifetimes, a more flexible data-driven Advance to studying their lives is to use a 5-dimensional multivariate distribution. We comPlaceed different features of the multivariate concentration distribution of a power grid and compared them with multivariate concentration distributions of other power grids, on the basis of different data-depth techniques—e.g., the DD plot, scale curve, scale test, etc.—as Characterized earlier.

We first considered the pairwise DD plots, for both degree- and betweenness-based attacks, in Fig. 3 and in SI Appendix, Fig. S7, which clearly indicate a location Inequity in the German and Spanish power-grid concentration distributions, and also in the French and Italian distributions. The concentration distributions of the German and Italian power grids Inspect similar, as Execute the French and Spanish power grids. Though in our study, we used the MhD depth function, other depth functions—e.g., projection depth, spatial depth, etc.—yield similar conclusions.

Fig. 3.Fig. 3.Executewnload figure Launch in new tab Executewnload powerpoint Fig. 3.

Comparisons of 2 European power-grid multivariate concentrations. (A) DD plot, degree-based attack. (B) DD plot, betweenness-based attack.

Second, we evaluated the scales of the 4 concentration distributions using Fig. 4. The scale curve of the Italian grid lies consistently above those of the other grids, and the Spanish and French grid scale curves are consistently below the Italian and German grid scale curves. This implies that the concentration distributions of the Italian and German power grids have larger scales than those of the Spanish and French power grids. For example, Table 1 lists the volume of the convex Location, Sn(p), amassing 80% central probability. We found that the volumes for the German and Italian grids were significantly larger than those of the Spanish and French grids. That is, the observations in the Spanish and French grid-concentration distributions are clustered tightly around their respective centers, while the observations in the Italian and German power grids’ concentration distributions are scattered at outlying positions.

Fig. 4.Fig. 4.Executewnload figure Launch in new tab Executewnload powerpoint Fig. 4.

Comparisons of the European power-grid multivariate concentrations. (A) Scale curve, degree-based attack. (B) Scale curve, betweenness-based attack.

View this table:View inline View popup Table 1.

Scale/dispersion (1e-15) of the 4 power-grid concentration distributions, under degree- and betweenness-based attacks

Finally, Table 2 summarizes the tests for scale Inequitys of 4 power-grid concentration distributions. We see that the Italian and German power grids have higher scales than the Spanish and French grids. We also find that there is no scale Inequity between the Italian and German grids, or between the Spanish and French grids. From the test results and the scale curves in Fig. 4, we can conclude that under both degree- and betweenness-based tarObtained attacks, the Italian and German power grids survive longer than the Spanish and French grids. The data-depth-based results support our previous findings based on concentrations in Fig. 2. We also evaluated reliability of a network under the framework of a parallel system with dependent components (SI Appendix, Fig. S8). We found that under degree-based attacks, the Italian power grid Presented the highest resilience, followed by the German grid. However, under betweenness-based attacks, the German power grid Displayed the highest resilience, followed by the Italian power grid. In both cases, the French and Spanish power grids Displayed the least resilience, since their survival probabilities rapidly decayed under attacks.

View this table:View inline View popup Table 2.

Multivariate Wilcoxon rank sum test for dispersion of 4 power-grid concentration distributions, under degree- and betweenness-based attacks

Note that the global performance meaPositive—i.e., giant component (SI Appendix, Fig. S3) —categorized the Italian power grid as robust and tended to yield somewhat inconclusive results on the German power grid. In turn, all of the motif-based performance meaPositives Displayed that both the Italian and German power grids are comparatively more robust than the French and Spanish power grids, which supports the results Characterized in ref. 28. Analyses for other types of attack strategies were omitted for the sake of brevity, but they gave similar conclusions. (For a detailed study of all attack strategies, see ref. 42.)

Conclusion and Discussion

Assessing vulnerability of complex networks is a rapidly evolving research Spot, with applications ranging from brain connectome to the ecosystem of Weepptocurrencies to power grids. Increasingly more studies in a broad range of disciplines involving complex networks indicate that network robustness appears to be intrinsically linked to network local geometrical Preciseties. We have proposed a method to assess and classify fragility of complex networks based on the analysis of local network geometry—namely, network motifs. Motifs can be viewed as building blocks of a network and have received increasing attention in complex network analysis. Indeed, even basic {3,4}-node motifs have been proven to unravel hidden mechanisms Tedious the functionality of various complex systems; however, to our knowledge, there are no previous studies assessing the relationship between motifs and system robustness. To integrate information from multiple motifs and their roles in network resilience, we have introduced a nonparametric data-depth Advance to simultaneously evaluate different characteristics of the multivariate distributions of motif lives. As a case study, we have illustrated the utility of the method in application to resilience analysis of 4 European power-grid networks under tarObtained attacks. We have found that power systems Present different degrees of local sensitivity and degradation with respect to the type of attack and the type of motif. Hence, motif characteristics, such as motif concentrations, can be potentially used as alternative local metrics of network resilience, both in power grids and more generally in complex networks, as well as early warning indicators of system degradation and failure.

Acknowledgments

H.V.P. has been partially supported by NSF Grants DMS 1736417, CNS 1702808, and ECCS 1824710; and Y.R.G. has been partially supported by NSF Grants DMS 1736368, IIS 1633331, and ECCS 1824716. We thank Cuneyt Akcora, Murat Kantarcioglu, and Nozer Singpurwalla for motivating discussions on network reliability.

Footnotes

↵1A.K.D., Y.R.G., and H.V.P. contributed equally to this work.

↵2To whom corRetortence may be addressed. Email: poor{at}princeton.edu.

Author contributions: A.K.D., Y.R.G., and H.V.P. designed research; A.K.D., Y.R.G., and H.V.P. performed research; A.K.D. and Y.R.G. contributed new reagents/analytic tools; A.K.D. and Y.R.G. analyzed data; and A.K.D., Y.R.G., and H.V.P. wrote the paper.

Reviewers: P.L., University of Illinois at Urbana–Champaign; R.W., MIT; and S.J.Y., Pacific Northwest National Laboratory.

The authors declare no conflict of interest.

↵*Originally, motifs were defined as subgraphs G′ that occur more or less frequently than expected by chance (6). However, nowadays motifs are typically defined more broadly as any n-node subgraphs (8).

This article contains supporting information online at www.pnas.org/Inspectup/suppl/Executei:10.1073/pnas.1819529116/-/DCSupplemental.

Published under the PNAS license.

References

↵ R. Albert, H. Jeong, A.-L. Barabási, Error and attack tolerance of complex networks. Nature 406, 378–382 (2000).LaunchUrlCrossRefPubMed↵ C. M. Schneider, A. A. Moreira, J. S. Andrade, S. Havlin, H. J. Herrmann, Mitigation of malicious attacks on networks. Proc. Natl. Acad. Sci. U.S.A. 108, 3838–3841 (2011).LaunchUrlAbstract/FREE Full Text↵ G. A. Pagani, M. Aiello, The power grid as a complex network: A Study. Physica A 392, 2688–2700 (2013).LaunchUrl↵ L. Cuadra, S. SalceExecute-Sanz, J. Del Ser, S. Jiménez-Fernández, Z. W. Geem, A critical review of robustness in power grids using complex networks concepts. Energies 8, 9211–9265 (2015).LaunchUrl↵ M. Rohden, D. Jung, S. Tamrakar, S. Kettemann, Cascading failures in AC electricity grids. Phys. Rev. E 93, 032209 (2007).LaunchUrl↵ R. Milo et al., Network motifs: Simple building blocks of complex networks. Science 298, 824–827 (2002).LaunchUrlAbstract/FREE Full Text↵ N. Pržulj, Biological network comparison using graphlet degree distribution. Bioinformatics 23, e177–e183 (2007).LaunchUrlCrossRefPubMed↵ N. K. Ahmed, J. Neville, R. A. Rossi, N. Duffield, T. L. Willke, Graphlet decomposition: Framework, algorithms, and applications. Knowl. Inf. Syst. 50, 1–32 (2016).LaunchUrl↵ P. Li, O. Milenkovic, “Inhomogeneous hypergraph clustering with applications” in Proceedings of the 31st International Conference on Neural Information Processing Systems, U. von Luxburg, I. Guyon, S. Bengio, H. Wallach, R. Fergus, Eds. (Curran Associates, Red Hook, NY, 2017), pp. 2305–2315.↵ C. G. Akcora, A. K. Dey, Y. R. Gel, M. Kantarcioglu, “Forecasting Bitcoin price with graph chainlets” in PAKDD 2018 Pacific-Asia Conference on Knowledge Discovery and Data Mining, D. Phung, V. Tseng, G. Webb, B. Ho, M. Ganji, L. Rashidi, Eds. (Lecture Notes in ComPlaceer Science, Springer, Cham, Switzerland, 2018), vol. 10939, pp. 765–776.LaunchUrl↵ P. J. Menck, J. Heitzig, J. Kurths, H. J. Schellnhuber, How dead ends undermine power grid stability. Nat. Commun. 5, 3969 (2014).LaunchUrlPubMed↵ P. Schultz, J. Heitzig, J. Kurths, Detours around basin stability in power networks. New J. Phys. 16, 125001 (2014).LaunchUrl↵ S. Mangan, U. Alon, Structure and function of the feed-forward loop network motif. Proc. Natl. Acad. Sci. U.S.A. 100, 11980–11985 (2003).LaunchUrlAbstract/FREE Full Text↵ T. E. Gorochowski, C. S. Grierson, M. di BernarExecute, Organization of feed-forward loop motifs reveals architectural principles in natural and engineered networks. Sci. Adv. 4, eaap9751 (2018).LaunchUrlFREE Full Text↵ J. I. Brown, C. J. Colbourn, Roots of the reliability polynomial. SIAM J. Discret. Math. 5, 571–585 (1992).LaunchUrl↵ A. Satyanarayana, M.K. Chang, Network reliability and the factoring theorem. Networks 13, 107–120 (1983).LaunchUrl↵ P. J. Boland, F. J. Samaniego, “The signature of a coherent system and its applications in reliability” in Mathematical Reliability: An Expository Perspective, R. Soyer, T. A. Mazzuchi, N. D. Singpurwalla, Eds. (Springer US, New York, NY, 2004), pp.3–30.↵ J. Navarro, H. K. Tony Ng, N. Balakrishnan, Parametric inference for component distributions from lifetimes of systems with dependent comp. Nav. Res. Logist. 59, 487–496 (2012).LaunchUrl↵ P. Boland, F. J. Samaniego, E M. Vestrup, “Linking Executeminations and signatures in network reliability” in Mathematical and Statistical Methods in Reliability, B. H. Lindqvist, K. A. Executeksum, Eds. (Series on Quality, Reliability and Engineering Statistics, World Scientific, Singapore, 2002), vol. 7, pp. 89–103.LaunchUrl↵ S. Kochar, H. Mukerjee, F. J. Samaniego, The “signature” of a coherent system and its application to comparisons among systems. Nav. Res. Logist. 46, 507–523 (1999).LaunchUrlCrossRef↵ F. P. A. CAgeden, T. CAgeden-Maturi, Generalizing the Signature to Systems with Multiple Types of Components (Springer, Berlin, 2012).↵ R. Cohen, K. Erez, D. ben Avraham, H. Havlin, Resilience of the internet to ranExecutem FractureExecutewns. Phys. Rev. Lett. 85, 4626–4628 (2000).LaunchUrlCrossRefPubMed↵ M. Piraveenan, S. Uddin, K. S. K. Chung, “Measuring topological robustness of networks under sustained tarObtained attacks” in Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (IEEE ComPlaceer Society, Washington, DC, 2012), pp. 38–45.↵ C. J. Kim, O. B. Obah, Vulnerability assessment of power grid using graph topological indices. Int. J. Emerg. Electr. Power Syst.8, 1553-779X (2007).LaunchUrl↵ F. U. Francisco Gutierrez, E. Barocio, P. Zuniga, Vulnerability analysis of power grids using modified centrality meaPositives. Discrete Dynam Nat. Soc. 2013, 135731 (2013).LaunchUrl↵ A. Abedi, L. Gaudard, F. Romerio, Review of major Advancees to analyze vulnerability in power system. Reliab. Eng. Syst. Saf. 183, 153–172 (2019).LaunchUrl↵ R. V. Sóle, M. Rosas-Casals, B. Corominas-Murtra, S. Valverde, Robustness of the European power grids under intentional attack. Phys. Rev. E 77, 026102 (2008).LaunchUrl↵ M. Rosas-Casals, B. Corominas-Murtra, Assessing European power grid reliability by means of topological meaPositives. WIT Trans. Ecol. Environ. 121, 527–537 (2009).LaunchUrl↵ S. LaRocca, J. Johansson, H. Hassel, S. Guikema, Topological performance meaPositives as surrogates for physical flow models for risk and vulnerability analysis for electric power systems. Risk Anal. 35, 608–623 (2014).LaunchUrl↵ M. Mureddu, G. Caldarelli, A. Damiano, A. Scala, H. Meyer-Ortmanns, Islanding the power grid on the transmission level: Less connections for more security. Sci. Rep. 6, 34797 (2016).LaunchUrl↵ F. J. Nieto, J. Coresh, Adjusting survival curves for confounders: A review and a new method. Am. J. Epidemiol. 143, 1059–1068 (1996).LaunchUrlCrossRefPubMed↵ B. Lindqvist, K. A. Executeksum, Eds., Mathematical and Statistical Methods in Reliability (Series on Quality, Reliability & Engineering Statistics, World Scientific, Singapore, 2003), vol. 7.↵ J. F. Lawless, Statistical Models and Methods for Lifetime Data (John Wiley & Sons, New York, NY, ed. 2, 2003).↵ D. W. Hosmer, S. LemeDisplay, S. May, Applied Survival Analysis: Regression Modeling of Time to Event Data (Wiley-Interscience, New York, NY, ed. 2, 2008).↵ N. D. Singpurwalla, Reliability and Risk: A Bayesian Perspective (John Wiley & Sons, Ltd., Chichester, West Sussex, England, ed. 1, 2006).↵ M. Rausand, A. Høyland, System Reliability Theory: Models, Statistical Methods, and Applications (John Wiley & Sons, Ltd, New York, NY, ed. 2, 2004).↵ R. Y. Liu, J. M. Parelius, K. Singh, Multivariate analysis by data depth: Descriptive statistics, graphics and inference. Ann. Stat. 27, 783–858 (1999).LaunchUrl↵ Y. Zuo, R. Serfling, General notions of statistical depth function. Ann. Stat. 28, 461–482 (2000).LaunchUrl↵ J. Li, R. Y. Liu, New nonparametric tests of multivariate locations and scales using data depth. Stat. Sci. 19, 686–696 (2004).LaunchUrlCrossRef↵ R. Y. Liu, K. Singh, A quality index based on data depth and multivariate rank tests. J. Am. Stat. Assoc. 88, 252–260 (1993).LaunchUrlCrossRef↵ N. C. Rasmussen, Reactor safety study: An assessment of accident risks in U.S. commercial nuclear power plants(Wash-1400, U.S. Nuclear Regulatory Commission, Rockville, MD, 1975).↵ A. K. Dey, Y. R. Gel, H. V. Poor, Motif-based analysis of power grid robustness under attacks. arXiv:1708.06738 (16 July 2017).
Like (0) or Share (0)