Universal robustness characteristic of weighted networks against cascading failure

Improved Link Entropy with Dynamic Community Number Detection for Quantifying Significance of Edges in Complex Social Networks

Discovering communities in complex networks is essential in performing analyses, such as dynamics of political fragmentation and echo chambers in social networks. In this work, we study the problem of quantifying the significance of edges in a complex network, and propose a significantly improved version of the Link Entropy method. Using Louvain, Leiden and Walktrap methods, our proposal detects the number of communities in each iteration on discovering the communities. Running experiments on various benchmark networks, we show that our proposed method outperforms the Link Entropy method in quantifying edge significance. Considering also the computational complexities and possible defects, we conclude that Leiden or Louvain algorithms are the best choice for community number detection in quantifying edge significance. We also discuss designing a new algorithm for not only discovering the number of communities, but also computing the community membership uncertainties.

Predicting the cascading dynamics in complex networks via the bimodal failure size distribution

Cascading failure as a systematic risk occurs in a wide range of real-world networks. Cascade size distribution is a basic and crucial characteristic of systemic cascade behaviors. Recent research works have revealed that the distribution of cascade sizes is a bimodal form indicating the existence of either very small cascades or large ones. In this paper, we aim to understand the properties and formation characteristics of such bimodal distribution in complex networks and further predict the final cascade size. We first find that the bimodal distribution is ubiquitous under certain conditions in both synthetic and real networks. Moreover, the large cascades distributed in the right peak of bimodal distribution are resulted from either the failure of nodes with high load at the first step of the cascade or multiple rounds of cascades triggered by the initial failure. Accordingly, we propose a hybrid load metric (HLM), which combines the load of the initial broken node and the load of failed nodes triggered by the initial failure, to predict the final size of cascading failures. We validate the effectiveness of HLM by computing the accuracy of identifying the cascades belonging to the right and left peaks of the bimodal distribution. The results show that HLM is a better predictor than commonly used network centrality metrics in both synthetic and real-world networks. Finally, the influence of network structure on the optimal HLM is discussed.

Dynamic Load Redistribution of Power CPS Based on Comprehensive Index of Coupling Node Pairs

The adoption of power cyber physical systems (Power CPS) is becoming more and more widespread, and as risk spreads, cascading failures of overload behavior can lead to the collapse of individual or entire networks, becoming a major threat to the network security. Taking the power CPS coupling node pair as the starting point, this paper establishes the comprehensive indicators characterizing the importance and vulnerability of the coupled node pair, based on the idea of intrusion tolerance, when the cyber side is faulted by the network attack, the system actively carries out reasonable and effective dynamic load redistribution based on the indicators updated after each round of cascading, thereby inhibiting the spread of risk, reducing system losses, and improving survivability. The above theory is simulated on the IEEE 30-bus system and concludes that the proposed load redistribution strategy can effectively reduce the loss of the system after attacks.

A model for cascading failures with the probability of failure described as a logistic function

In most cascading failure models in networks, overloaded nodes are assumed to fail and are removed from the network. However, this is not always the case due to network mitigation measures. Considering the effects of these mitigating measures, we propose a new cascading failure model that describes the probability that an overloaded node fails as a logistic function. By performing numerical simulations of cascading failures on Barabási and Albert (BA) scale-free networks and a real airport network, we compare the results of our model and the established model describing the probability of failure as a linear function. The simulation results show that the difference in the robustness of the two models depends on the initial load distribution and the redistribution of load. We further investigate the conditions of our new model under which the network exhibits the strongest robustness in terms of the load distribution and the network topology. We find the optimal value for the parameter of the load distribution and demonstrate that the robustness of the network improves as the average degree increases. The results regarding the optimal load distribution are verified by theoretical analysis. This work can be used to develop effective mitigation measures and design networks that are robust to cascading failure phenomena.

MLCOR Model for Suppressing the Cascade of Edge Failures in Complex Network

As a decisive parameter of network robustness and network economy, the capacity of network edges can directly affect the operation stability and the construction cost of the network. This paper proposes a multilevel load–capacity optimal relationship (MLCOR) model that can substantially improve the network economy on the premise of network safety. The model is verified in artificially created networks including free-scale networks, small-world networks, and in the real network structure of the Shanghai Metro network as well. By numerical simulation, it is revealed that under the premise of ensuring the stability of the network from the destruction caused by initial internal or external damage on edge, the MLCOR model can effectively reduce the cost of the entire network compared to the other two linear load–capacity models regardless of what extent of the destruction that the network edges suffer initially. It is also proved that there exists an optimal tunable parameter and the corresponding optimal network cost for any BA and NW network topology, which can provide the reference for setting reasonable capacities for network edges in a real network at the stage of network planning and construction, promoting security and stability of network operation.

Effect of load-capacity heterogeneity on cascading overloads in networks

Heterogeneity in the load capacity of nodes is a common characteristic of many real-world networks that can dramatically affect their robustness to cascading overloads. However, most studies seeking to model cascading failures have ignored variations in nodal load capacity and functionality. The present study addresses this issue by extending the local load redistribution model to include heterogeneity in nodal load capacity and heterogeneity in the types of nodes employed in the network configuration and exploring how these variations affect network robustness. Theoretical and numerical analyses demonstrate that the extent of cascading failure is influenced by heterogeneity in nodal load capacity, while it is relatively insensitive to heterogeneity in nodal configuration. Moreover, the probability of cascading failure initiation at the critical state increases as the range of nodal load capacities increases. However, for large-scale networks with degree heterogeneity, a wide range of nodal load capacities can also suppress the spread of failure after its initiation. In addition, the analysis demonstrates that heterogeneity in nodal load capacity increases and decreases the extent of cascading failures in networks with sublinear and superlinear load distributions, respectively. These findings may provide some practical implications for controlling the spread of cascading failure.

Improving robustness in interdependent networks under intentional attacks by optimizing intra-link allocation

The interdependent network is particularly vulnerable to attacks on high degree nodes; therefore, the improvement of its robustness under intentional attacks has become an important topic. In this paper, we put forward a new metric to quantify the robustness of interdependent networks against intentional attacks and develop an improved simulated annealing algorithm (ISAA) to maximize this metric by optimizing the allocation of intra-links in subnetworks. Based on the comparison between the ISAA and existing algorithms, it is found that the algorithm presented in this paper is more effective to enhance the robustness of an interdependent scale-free network (ISFN). By applying the ISAA to ISFNs with different coupling preferences, there is a key finding that the robustness of the optimized ISFN is significantly stronger than that of the original ISFN. In particular, for cases of disassortative and random couplings, no sudden collapse occurs in optimized ISFNs. According to the analysis of the degree and the clustering coefficient, we find that the subnetwork of the optimized ISFN exhibits an onion-like structure. In addition, the ISFN whose robustness is enhanced to resist the attacks on high degree nodes is still robust to the intentional attacks concerning the betweenness and PageRank.

Numerical analysis of first-passage processes in finite Markov chains exhibiting metastability

We describe state-reduction algorithms for the analysis of first-passage processes in discrete- and continuous-time finite Markov chains. We present a formulation of the graph transformation algorithm that allows for the evaluation of exact mean first-passage times, stationary probabilities, and committor probabilities for all nonabsorbing nodes of a Markov chain in a single computation. Calculation of the committor probabilities within the state-reduction formalism is readily generalizable to the first hitting problem for any number of alternative target states. We then show that a state-reduction algorithm can be formulated to compute the expected number of times that each node is visited along a first-passage path. Hence, all properties required to analyze the first-passage path ensemble (FPPE) at both a microscopic and macroscopic level of detail, including the mean and variance of the first-passage time distribution, can be computed using state-reduction methods. In particular, we derive expressions for the probability that a node is visited along a direct transition path, which proceeds without returning to the initial state, considering both the nonequilibrium and equilibrium (steady-state) FPPEs. The reactive visitation probability provides a rigorous metric to quantify the dynamical importance of a node for the productive transition between two endpoint states and thus allows the local states that facilitate the dominant transition mechanisms to be readily identified. The state-reduction procedures remain numerically stable even for Markov chains exhibiting metastability, which can be severely ill-conditioned. The rare event regime is frequently encountered in realistic models of dynamical processes, and our methodology therefore provides valuable tools for the analysis of Markov chains in practical applications. We illustrate our approach with numerical results for a kinetic network representing a structural transition in an atomic cluster.

Modelling cascading failures in networks with the harmonic closeness

Many studies on cascading failures adopt the degree or the betweenness of a node to define its load. From a novel perspective, we propose an approach to obtain initial loads considering the harmonic closeness and the impact of neighboring nodes. Based on simulation results for different adjustable parameter θ, local parameter δ and proportion of attacked nodes f, it is found that in scale-free networks (SF networks), small-world networks (SW networks) and Erdos-Renyi networks (ER networks), there exists a negative correlation between optimal θ and δ. By the removal of the low load node, cascading failures are more likely to occur in some cases. In addition, we find a valuable result that our method yields better performance compared with other methods in SF networks with an arbitrary f, SW and ER networks with large f. Moreover, the method concerning the harmonic closeness makes these three model networks more robust for different average degrees. Finally, we perform the simulations on twenty real networks, whose results verify that our method is also effective to distribute the initial load in different real networks.

Optimal control of aging in complex networks

Many complex systems experience damage accumulation, which leads to aging, manifest as an increasing probability of system collapse with time. This naturally raises the question of how to maximize health and longevity in an aging system at minimal cost of maintenance and intervention. Here, we pose this question in the context of a simple interdependent network model of aging in complex systems and show that it exhibits cascading failures. We then use both optimal control theory and reinforcement learning alongside a combination of analysis and simulation to determine optimal maintenance protocols. These protocols may motivate the rational design of strategies for promoting longevity in aging complex systems with potential applications in therapeutic schedules and engineered system maintenance.

Nonlinear model of cascade failure in weighted complex networks considering overloaded edges

Considering the elasticity of the real networks, the components in the network have a redundant capacity against the load, such as power grids, traffic networks and so on. Moreover, the interaction strength between nodes is often different. This paper proposes a novel nonlinear model of cascade failure in weighted complex networks considering overloaded edges to describe the redundant capacity for edges and capture the interaction strength of nodes. We fill this gap by studying a nonlinear weighted model of cascade failure with overloaded edges over synthetic and real weighted networks. The cascading failure model is constructed for the first time according to the overload coefficient, capacity parameter, weight coefficient, and distribution coefficient. Then through theoretical analysis, the conditions for stopping failure cascades are obtained, and the analysis shows the superiority of the constructed model. Finally, the cascading invulnerability is simulated in several typical network models and the US power grid. The results show that the model is a feasible and reasonable change of weight parameters, capacity coefficient, distribution coefficient, and overload coefficient can significantly improve the destructiveness of complex networks against cascade failure. Our methodology provides an efficacious reference for the control and prevention of cascading failures in many real networks.

A biochemical network modeling of a whole-cell

All cellular processes can be ultimately understood in terms of respective fundamental biochemical interactions between molecules, which can be modeled as networks. Very often, these molecules are shared by more than one process, therefore interconnecting them. Despite this effect, cellular processes are usually described by separate networks with heterogeneous levels of detail, such as metabolic, protein-protein interaction, and transcription regulation networks. Aiming at obtaining a unified representation of cellular processes, we describe in this work an integrative framework that draws concepts from rule-based modeling. In order to probe the capabilities of the framework, we used an organism-specific database and genomic information to model the whole-cell biochemical network of the Mycoplasma genitalium organism. This modeling accounted for 15 cellular processes and resulted in a single component network, indicating that all processes are somehow interconnected. The topological analysis of the network showed structural consistency with biological networks in the literature. In order to validate the network, we estimated gene essentiality by simulating gene deletions and compared the results with experimental data available in the literature. We could classify 212 genes as essential, being 95% of them consistent with experimental results. Although we adopted a relatively simple organism as a case study, we suggest that the presented framework has the potential for paving the way to more integrated studies of whole organisms leading to a systemic analysis of cells on a broader scale. The modeling of other organisms using this framework could provide useful large-scale models for different fields of research such as bioengineering, network biology, and synthetic biology, and also provide novel tools for medical and industrial applications.

Network overload due to massive attacks

We study the cascading failure of networks due to overload, using the betweenness centrality of a node as the measure of its load following the Motter and Lai model. We study the fraction of survived nodes at the end of the cascade p_{f} as a function of the strength of the initial attack, measured by the fraction of nodes p that survive the initial attack for different values of tolerance α in random regular and Erdös-Renyi graphs. We find the existence of a first-order phase-transition line p_{t}(α) on a p-α plane, such that if p<p_{t}, the cascade of failures leads to a very small fraction of survived nodes p_{f} and the giant component of the network disappears, while for p>p_{t}, p_{f} is large and the giant component of the network is still present. Exactly at p_{t}, the function p_{f}(p) undergoes a first-order discontinuity. We find that the line p_{t}(α) ends at a critical point (p_{c},α_{c}), in which the cascading failures are replaced by a second-order percolation transition. We find analytically the average betweenness of nodes with different degrees before and after the initial attack, we investigate their roles in the cascading failures, and we find a lower bound for p_{t}(α). We also study the difference between localized and random attacks.

Cascading failures in interdependent systems under a flow redistribution model

Robustness and cascading failures in interdependent systems has been an active research field in the past decade. However, most existing works use percolation-based models where only the largest component of each network remains functional throughout the cascade. Although suitable for communication networks, this assumption fails to capture the dependencies in systems carrying a flow (e.g., power systems, road transportation networks), where cascading failures are often triggered by redistribution of flows leading to overloading of lines. Here, we consider a model consisting of systems A and B with initial line loads and capacities given by {L_{A,i},C_{A,i}}_{i=1}^{n} and {L_{B,i},C_{B,i}}_{i=1}^{n}, respectively. When a line fails in system A, a fraction of its load is redistributed to alive lines in B, while remaining (1-a) fraction is redistributed equally among all functional lines in A; a line failure in B is treated similarly with b giving the fraction to be redistributed to A. We give a thorough analysis of cascading failures of this model initiated by a random attack targeting p_{1} fraction of lines in A and p_{2} fraction in B. We show that (i) the model captures the real-world phenomenon of unexpected large scale cascades and exhibits interesting transition behavior: the final collapse is always first order, but it can be preceded by a sequence of first- and second-order transitions; (ii) network robustness tightly depends on the coupling coefficients a and b, and robustness is maximized at non-trivial a,b values in general; (iii) unlike most existing models, interdependence has a multifaceted impact on system robustness in that interdependency can lead to an improved robustness for each individual network.

Quantifying edge significance on maintaining global connectivity

Global connectivity is a quite important issue for networks. The failures of some key edges may lead to breakdown of the whole system. How to find them will provide a better understanding on system robustness. Based on topological information, we propose an approach named LE (link entropy) to quantify the edge significance on maintaining global connectivity. Then we compare the LE with the other six acknowledged indices on the edge significance: the edge betweenness centrality, degree product, bridgeness, diffusion importance, topological overlap and k-path edge centrality. Experimental results show that the LE approach outperforms in quantifying edge significance on maintaining global connectivity.

Traffic congestion and the lifetime of networks with moving nodes

For many power-limited networks, such as wireless sensor networks and mobile ad hoc networks, maximizing the network lifetime is the first concern in the related designing and maintaining activities. We study the network lifetime from the perspective of network science. In our model, nodes are initially assigned a fixed amount of energy moving in a square area and consume the energy when delivering packets. We obtain four different traffic regimes: no, slow, fast, and absolute congestion regimes, which are basically dependent on the packet generation rate. We derive the network lifetime by considering the specific regime of the traffic flow. We find that traffic congestion inversely affects network lifetime in the sense that high traffic congestion results in short network lifetime. We also discuss the impacts of factors such as communication radius, node moving speed, routing strategy, etc., on network lifetime and traffic congestion.

Robustness and Vulnerability of Networks with Dynamical Dependency Groups

The dependency property and self-recovery of failure nodes both have great effects on the robustness of networks during the cascading process. Existing investigations focused mainly on the failure mechanism of static dependency groups without considering the time-dependency of interdependent nodes and the recovery mechanism in reality. In this study, we present an evolving network model consisting of failure mechanisms and a recovery mechanism to explore network robustness, where the dependency relations among nodes vary over time. Based on generating function techniques, we provide an analytical framework for random networks with arbitrary degree distribution. In particular, we theoretically find that an abrupt percolation transition exists corresponding to the dynamical dependency groups for a wide range of topologies after initial random removal. Moreover, when the abrupt transition point is above the failure threshold of dependency groups, the evolving network with the larger dependency groups is more vulnerable; when below it, the larger dependency groups make the network more robust. Numerical simulations employing the Erdős-Rényi network and Barabási-Albert scale free network are performed to validate our theoretical results.

Risk measures for power failures in transmission systems

We present a novel framework for evaluating the risk of failures in power transmission systems. We use the concept of systemic risk measures from the financial mathematics literature with models of power system failures in order to quantify the risk of the entire power system for design and comparative purposes. The proposed risk measures provide the collection of capacity vectors for the components in the system that lead to acceptable outcomes. Keys to the formulation of our measures of risk are two elements: a model of system behavior that provides the (distribution of) outcomes based on component capacities and an acceptability criterion that determines whether a (random) outcome is acceptable from an aggregated point of view. We examine the effects of altering the line capacities on energy not served under a variety of networks, flow manipulation methods, load shedding schemes, and load profiles using Monte Carlo simulations. Our results provide a quantitative comparison of the performance of these schemes, measured by the required line capacity. These results provide more complete descriptions of the risks of power failures than the previous, one-dimensional metrics.

Optimizing the robustness of electrical power systems against cascading failures

Electrical power systems are one of the most important infrastructures that support our society. However, their vulnerabilities have raised great concern recently due to several large-scale blackouts around the world. In this paper, we investigate the robustness of power systems against cascading failures initiated by a random attack. This is done under a simple yet useful model based on global and equal redistribution of load upon failures. We provide a comprehensive understanding of system robustness under this model by (i) deriving an expression for the final system size as a function of the size of initial attacks; (ii) deriving the critical attack size after which system breaks down completely; (iii) showing that complete system breakdown takes place through a first-order (i.e., discontinuous) transition in terms of the attack size; and (iv) establishing the optimal load-capacity distribution that maximizes robustness. In particular, we show that robustness is maximized when the difference between the capacity and initial load is the same for all lines; i.e., when all lines have the same redundant space regardless of their initial load. This is in contrast with the intuitive and commonly used setting where capacity of a line is a fixed factor of its initial load.

Abnormal Behavior in Cascading Dynamics with Node Weight

Considering a preferential selection mechanism of load destination, we introduce a new method to quantify initial load distribution and subsequently construct a simple cascading model. By attacking the node with the highest load, we investigate the cascading dynamics in some synthetic networks. Surprisingly, we observe that for several networks of different structural patterns, a counterintuitive phenomenon emerges if the highest load attack is applied to the system, i.e., investing more resources to protect every node in a network inversely makes the whole network more vulnerable. We explain this ability paradox by analyzing the micro-structural components of the underlying network and therefore reveals how specific structural patterns may influence the cascading dynamics. We discover that the robustness of the network oscillates as the capacity of each node increases. The conclusion of the paper may shed lights on future investigations to avoid the demonstrated ability paradox and subsequent cascading failures in real-world networks.

Ability paradox of cascading model based on betweenness

Must Investing more resources to protect every node in a network improve the robustness of the whole network subject to target attacks? To answer this question, we investigate the cascading dynamics in some typical networks. In real networks, the load on a node is generally correlated with the betweenness. Considering the weight of a node, we give a new method to define the initial load on a node by the revised betweenness. Then we present a simple cascading model. We investigate the cascading dynamics by disabling a single key node with the highest load. We find that in BA scale-free networks, the bigger the capacity of every node, the stronger the robustness of the whole network. However, in WS networks and some random networks, when we increase the capacity of every node, instead, the robustness of the whole network is weaker. In US power grid and the China power grid, we also observe this counterintuitive phenomenon. We give a reasonable explanation by a simple illusion. By the analysis, we think that resurrections of some nodes in a ring network structure after removing a node may be the reason of this phenomenon.

Improving the accuracy of the k-shell method by removing redundant links: From a perspective of spreading dynamics

Recent study shows that the accuracy of the k-shell method in determining node coreness in a spreading process is largely impacted due to the existence of core-like group, which has a large k-shell index but a low spreading efficiency. Based on the analysis of the structure of core-like groups in real-world networks, we discover that nodes in the core-like group are mutually densely connected with very few out-leaving links from the group. By defining a measure of diffusion importance for each edge based on the number of out-leaving links of its both ends, we are able to identify redundant links in the spreading process, which have a relatively low diffusion importance but lead to form the locally densely connected core-like group. After filtering out the redundant links and applying the k-shell method to the residual network, we obtain a renewed coreness k_s for each node which is a more accurate index to indicate its location importance and spreading influence in the original network. Moreover, we find that the performance of the ranking algorithms based on the renewed coreness are also greatly enhanced. Our findings help to more accurately decompose the network core structure and identify influential nodes in spreading processes.

Robustness of power systems under a democratic-fiber-bundle-like model

We consider a power system with N transmission lines whose initial loads (i.e., power flows) L(1),...,L(N) are independent and identically distributed with P(L)(x)=P[L≤x]. The capacity C(i) defines the maximum flow allowed on line i and is assumed to be given by C(i)=(1+α)L(i), with α>0. We study the robustness of this power system against random attacks (or failures) that target a p fraction of the lines, under a democratic fiber-bundle-like model. Namely, when a line fails, the load it was carrying is redistributed equally among the remaining lines. Our contributions are as follows. (i) We show analytically that the final breakdown of the system always takes place through a first-order transition at the critical attack size p(☆)=1-(E[L]/max(x)(P[L>x](αx+E[L|L>x])), where E[·] is the expectation operator; (ii) we derive conditions on the distribution P(L)(x) for which the first-order breakdown of the system occurs abruptly without any preceding diverging rate of failure; (iii) we provide a detailed analysis of the robustness of the system under three specific load distributions-uniform, Pareto, and Weibull-showing that with the minimum load L(min) and mean load E[L] fixed, Pareto distribution is the worst (in terms of robustness) among the three, whereas Weibull distribution is the best with shape parameter selected relatively large; (iv) we provide numerical results that confirm our mean-field analysis; and (v) we show that p(☆) is maximized when the load distribution is a Dirac delta function centered at E[L], i.e., when all lines carry the same load. This last finding is particularly surprising given that heterogeneity is known to lead to high robustness against random failures in many other systems.

Improving the robustness of complex networks with preserving community structure

Complex networks are everywhere, such as the power grid network, the airline network, the protein-protein interaction network, and the road network. The networks are 'robust yet fragile', which means that the networks are robust against random failures but fragile under malicious attacks. The cascading failures, system-wide disasters and intentional attacks on these networks are deserving of in-depth study. Researchers have proposed many solutions to improve the robustness of these networks. However whilst many solutions preserve the degree distribution of the networks, little attention is paid to the community structure of these networks. We argue that the community structure of a network is a defining characteristic of a network which identifies its functionality and thus should be preserved. In this paper, we discuss the relationship between robustness and the community structure. Then we propose a 3-step strategy to improve the robustness of a network, while retaining its community structure, and also its degree distribution. With extensive experimentation on representative real-world networks, we demonstrate that our method is effective and can greatly improve the robustness of networks, while preserving community structure and degree distribution. Finally, we give a description of a robust network, which is useful not only for improving robustness, but also for designing robust networks and integrating networks.

Robustness of controllability for networks based on edge-attack

We study the controllability of networks in the process of cascading failures under two different attacking strategies, random and intentional attack, respectively. For the highest-load edge attack, it is found that the controllability of Erdős-Rényi network, that with moderate average degree, is less robust, whereas the Scale-free network with moderate power-law exponent shows strong robustness of controllability under the same attack strategy. The vulnerability of controllability under random and intentional attacks behave differently with the increasing of removal fraction, especially, we find that the robustness of control has important role in cascades for large removal fraction. The simulation results show that for Scale-free networks with various power-law exponents, the network has larger scale of cascades do not mean that there will be more increments of driver nodes. Meanwhile, the number of driver nodes in cascading failures is also related to the edges amount in strongly connected components.

Performance and reliability analysis of water distribution systems under cascading failures and the identification of crucial pipes

As a mean of supplying water, Water distribution system (WDS) is one of the most important complex infrastructures. The stability and reliability are critical for urban activities. WDSs can be characterized by networks of multiple nodes (e.g. reservoirs and junctions) and interconnected by physical links (e.g. pipes). Instead of analyzing highest failure rate or highest betweenness, reliability of WDS is evaluated by introducing hydraulic analysis and cascading failures (conductive failure pattern) from complex network. The crucial pipes are identified eventually. The proposed methodology is illustrated by an example. The results show that the demand multiplier has a great influence on the peak of reliability and the persistent time of the cascading failures in its propagation in WDS. The time period when the system has the highest reliability is when the demand multiplier is less than 1. There is a threshold of tolerance parameter exists. When the tolerance parameter is less than the threshold, the time period with the highest system reliability does not meet minimum value of demand multiplier. The results indicate that the system reliability should be evaluated with the properties of WDS and the characteristics of cascading failures, so as to improve its ability of resisting disasters.

Structural robustness of scale-free networks against overload failures

We study the structural robustness of scale-free networks against overload failures induced by loads exceeding the node capacity, based on analytical and numerical approaches to the percolation problem in which a fixed number of nodes are removed according to the overload probability. Modeling fluctuating loads by random walkers in a network, we find that the degree dependence of the overload probability drastically changes with respect to the total load. We also elucidate that there exist two types of structural robustness of networks against overload failures. One is measured by the critical total load W(c) and the other is by the critical node removal fraction f(c). Enhancing the scale-free property, networks become fragile in both senses of W(c) and f(c). By contrast, increasing the node tolerance, scale-free networks become robust in the sense of the critical total load, while they come to be fragile in the sense of the critical node removal fraction. Furthermore, we show that these trends are not affected by degree-degree correlations, although assortative mixing makes networks robust in both senses of W(c) and f(c).

Random walks in weighted networks with a perfect trap: an application of Laplacian spectra

Trapping processes constitute a primary problem of random walks, which characterize various other dynamical processes taking place on networks. Most previous works focused on the case of binary networks, while there is much less related research about weighted networks. In this paper, we propose a general framework for the trapping problem on a weighted network with a perfect trap fixed at an arbitrary node. By utilizing the spectral graph theory, we provide an exact formula for mean first-passage time (MFPT) from one node to another, based on which we deduce an explicit expression for average trapping time (ATT) in terms of the eigenvalues and eigenvectors of the Laplacian matrix associated with the weighted graph, where ATT is the average of MFPTs to the trap over all source nodes. We then further derive a sharp lower bound for the ATT in terms of only the local information of the trap node, which can be obtained in some graphs. Moreover, we deduce the ATT when the trap is distributed uniformly in the whole network. Our results show that network weights play a significant role in the trapping process. To apply our framework, we use the obtained formulas to study random walks on two specific networks: trapping in weighted uncorrelated networks with a deep trap, the weights of which are characterized by a parameter, and Lévy random walks in a connected binary network with a trap distributed uniformly, which can be looked on as random walks on a weighted network. For weighted uncorrelated networks we show that the ATT to any target node depends on the weight parameter, that is, the ATT to any node can change drastically by modifying the parameter, a phenomenon that is in contrast to that for trapping in binary networks. For Lévy random walks in any connected network, by using their equivalence to random walks on a weighted complete network, we obtain the optimal exponent characterizing Lévy random walks, which have the minimal average of ATTs taken over all target nodes.

Random walks on weighted networks

Random walks constitute a fundamental mechanism for a large set of dynamics taking place on networks. In this article, we study random walks on weighted networks with an arbitrary degree distribution, where the weight of an edge between two nodes has a tunable parameter. By using the spectral graph theory, we derive analytical expressions for the stationary distribution, mean first-passage time (MFPT), average trapping time (ATT), and lower bound of the ATT, which is defined as the average MFPT to a given node over every starting point chosen from the stationary distribution. All these results depend on the weight parameter, indicating a significant role of network weights on random walks. For the case of uncorrelated networks, we provide explicit formulas for the stationary distribution as well as ATT. Particularly, for uncorrelated scale-free networks, when the target is placed on a node with the highest degree, we show that ATT can display various scalings of network size, depending also on the same parameter. Our findings could pave a way to delicately controlling random-walk dynamics on complex networks.

Stability-to-instability transition in the structure of large-scale networks

We examine phase transitions between the "easy," "hard," and "unsolvable" phases when attempting to identify structure in large complex networks ("community detection") in the presence of disorder induced by network "noise" (spurious links that obscure structure), heat bath temperature T, and system size N. The partition of a graph into q optimally disjoint subgraphs or "communities" inherently requires Potts-type variables. In earlier work [Philos. Mag. 92, 406 (2012)], when examining power law and other networks (and general associated Potts models), we illustrated that transitions in the computational complexity of the community detection problem typically correspond to spin-glass-type transitions (and transitions to chaotic dynamics in mechanical analogs) at both high and low temperatures and/or noise. The computationally "hard" phase exhibits spin-glass type behavior including memory effects. The region over which the hard phase extends in the noise and temperature phase diagram decreases as N increases while holding the average number of nodes per community fixed. This suggests that in the thermodynamic limit a direct sharp transition may occur between the easy and unsolvable phases. When present, transitions at low temperature or low noise correspond to entropy driven (or "order by disorder") annealing effects, wherein stability may initially increase as temperature or noise is increased before becoming unsolvable at sufficiently high temperature or noise. Additional transitions between contending viable solutions (such as those at different natural scales) are also possible. Identifying community structure via a dynamical approach where "chaotic-type" transitions were found earlier. The correspondence between the spin-glass-type complexity transitions and transitions into chaos in dynamical analogs might extend to other hard computational problems. In this work, we examine large networks (with a power law distribution in cluster size) that have a large number of communities (q≫1). We infer that large systems at a constant ratio of q to the number of nodes N asymptotically tend towards insolvability in the limit of large N for any positive T. The asymptotic behavior of temperatures below which structure identification might be possible, T_{×}=O[1/lnq], decreases slowly, so for practical system sizes, there remains an accessible, and generally easy, global solvable phase at low temperature. We further employ multivariate Tutte polynomials to show that increasing q emulates increasing T for a general Potts model, leading to a similar stability region at low T. Given the relation between Tutte and Jones polynomials, our results further suggest a link between the above complexity transitions and transitions associated with random knots.

Epidemic spreading in weighted networks: an edge-based mean-field solution

Weight distribution greatly impacts the epidemic spreading taking place on top of networks. This paper presents a study of a susceptible-infected-susceptible model on regular random networks with different kinds of weight distributions. Simulation results show that the more homogeneous weight distribution leads to higher epidemic prevalence, which, unfortunately, could not be captured by the traditional mean-field approximation. This paper gives an edge-based mean-field solution for general weight distribution, which can quantitatively reproduce the simulation results. This method could be applied to characterize the nonequilibrium steady states of dynamical processes on weighted networks.

Cascading dynamics on random networks: crossover in phase transition

In a complex network, random initial attacks or failures can trigger subsequent failures in a cascading manner, which is effectively a phase transition. Recent works have demonstrated that in networks with interdependent links so that the failure of one node causes the immediate failures of all nodes connected to it by such links, both first- and second-order phase transitions can arise. Moreover, there is a crossover between the two types of transitions at a critical system-parameter value. We demonstrate that these phenomena can occur in the more general setting where no interdependent links are present. A heuristic theory is derived to estimate the crossover and phase-transition points, and a remarkable agreement with numerics is obtained.

Cascaded failures in weighted networks

Many technological networks can experience random and/or systematic failures in their components. More destructive situations can happen if the components have limited capacity, where the failure in one of them might lead to a cascade of failures in other components, and consequently break down the structure of the network. In this paper, the tolerance of cascaded failures was investigated in weighted networks. Three weighting strategies were considered including the betweenness centrality of the edges, the product of the degrees of the end nodes, and the product of their betweenness centralities. Then, the effect of the cascaded attack was investigated by considering the local weighted flow redistribution rule. The capacity of the edges was considered to be proportional to their initial weight distribution. The size of the survived part of the attacked network was determined in model networks as well as in a number of real-world networks including the power grid, the internet in the level of autonomous system, the railway network of Europe, and the United States airports network. We found that the networks in which the weight of each edge is the multiplication of the betweenness centrality of the end nodes had the best robustness against cascaded failures. In other words, the case where the load of the links is considered to be the product of the betweenness centrality of the end nodes is favored for the robustness of the network against cascaded failures.

Evolution of Chinese airport network

With the rapid development of the economy and the accelerated globalization process, the aviation industry plays a more and more critical role in today's world, in both developed and developing countries. As the infrastructure of aviation industry, the airport network is one of the most important indicators of economic growth. In this paper, we investigate the evolution of the Chinese airport network (CAN) via complex network theory. It is found that although the topology of CAN has remained steady during the past few years, there are many dynamic switchings inside the network, which have changed the relative importance of airports and airlines. Moreover, we investigate the evolution of traffic flow (passengers and cargoes) on CAN. It is found that the traffic continues to grow in an exponential form and has evident seasonal fluctuations. We also found that cargo traffic and passenger traffic are positively related but the correlations are quite different for different kinds of cities.

Abnormal cascading on complex networks

In the study of cascading failures on complex networks, a key issue is to define capacities of edges and nodes as realistically as possible. This leads to the consideration of intrinsic edge capacity associated with laws governing flows on networks, which goes beyond the existing definitions of capacity based on the initial load as quantified by the betweenness centrality. Limited edge capacity (or bandwidth) and high flux or attack can trigger cascading processes, which we find as characteristically different from those reported in the literature. In particular, there can be an abnormal parameter regime where incrementally augmenting the edge capacity can counterintuitively increase the severeness of the cascading process. Another striking finding is that heterogeneous flow distribution tends to suppress the cascading process, in contrast to the current understanding that heterogeneity can make the network more vulnerable to cascading. We provide numerical computations and analysis to substantiate these findings.

Emergence of loop structure in scale-free networks and dynamical consequences

Previous work has revealed that the synchronizability of a scale-free network tends to be suppressed when its clustering coefficient is increased. We present a theory to explain this phenomenon. Our proposition is that, as the network becomes more strongly clustered, topological loop structure can emerge, generating a set of eigenvalues that are close to zero. As a result, the dynamics of synchronization tends to be dominated by the loop structure. As the clustering coefficient is increased, the size of the dominant loop increases, leading to continuous degradation of the network synchronizability. We provide analysis and numerical evidence to support the proposition and we speculate that the loop structure can provide a platform for controlling dynamical processes on scale-free networks with high clustering coefficients.

Power grid vulnerability: a complex network approach

Power grids exhibit patterns of reaction to outages similar to complex networks. Blackout sequences follow power laws, as complex systems operating near a critical point. Here, the tolerance of electric power grids to both accidental and malicious outages is analyzed in the framework of complex network theory. In particular, the quantity known as efficiency is modified by introducing a new concept of distance between nodes. As a result, a new parameter called net-ability is proposed to evaluate the performance of power grids. A comparison between efficiency and net-ability is provided by estimating the vulnerability of sample networks, in terms of both the metrics.

Optimal weighting scheme for suppressing cascades and traffic congestion in complex networks

This paper is motivated by the following two related problems in complex networks: (i) control of cascading failures and (ii) mitigation of traffic congestion. Both problems are of significant recent interest as they address, respectively, the security of and efficient information transmission on complex networks. Taking into account typical features of load distribution and weights in real-world networks, we have discovered an optimal solution to both problems. In particular, we shall provide numerical evidence and theoretical analysis that, by choosing a proper weighting parameter, a maximum level of robustness against cascades and traffic congestion can be achieved, which practically rids the network of occurrences of the catastrophic dynamics.