Robustness of onionlike correlated networks against targeted attacks

Investigating stronger tolerant network against cascading failures in focusing on changing degree distributions

Many real-world networks with Scale-Free structure are significantly vulnerable against both intentional attacks and catastrophic cascading failures. On the other hand, it has been shown that networks with narrower degree distributions have strong robustness of connectivity by enhancing loops. This paper numerically reveals that such networks are also tolerant against cascading failures. Our findings will be useful in designing stronger tolerant network infrastructures.

A Learning Convolutional Neural Network Approach for Network Robustness Prediction

Network robustness is critical for various societal and industrial networks against malicious attacks. In particular, connectivity robustness and controllability robustness reflect how well a networked system can maintain its connectedness and controllability against destructive attacks, which can be quantified by a sequence of values that record the remaining connectivity and controllability of the network after a sequence of node- or edge-removal attacks. Traditionally, robustness is determined by attack simulations, which are computationally very time-consuming or even practically infeasible for large-scale networks. In this article, an improved method for network robustness prediction is developed based on learning feature representation using the convolutional neural network (LFR-CNN). In this scheme, the higher-dimensional network data are compressed into lower-dimensional representations, which are then passed to a convolutional neural network to perform robustness prediction. Extensive experimental studies on both synthetic and real-world networks, both directed and undirected, demonstrate that: 1) the proposed LFR-CNN performs better than other two state-of-the-art prediction methods, with significantly smaller prediction errors; 2) LFR-CNN is insensitive to the variation of the input network size, which significantly extends its applicability; 3) although LFR-CNN needs more time to perform feature learning, it can achieve accurate prediction faster than attack simulations; and 4) LFR-CNN not only accurately predicts the network robustness, but also provides a good indicator for connectivity robustness, better than the classical spectral measures.

Graph convolutional networks-based robustness optimization for scale-free Internet of Things

The Internet of Things (IoT) devices have limited resources and are vulnerable to attacks, so optimizing their network topology to resist random failures and malicious attacks has become a key issue. The scale-free network model has strong resistance to random attacks, but it is very vulnerable to malicious attacks. The existing studies mostly adopt heuristic algorithms to optimize the ability of scale-free networks to resist malicious attacks, but their high computational cost cannot meet the timeliness requirements of the real IoT. Therefore, this paper proposes an intelligent topology robustness optimization model based on a graph convolutional network (ROGCN). The model extracts the onion-like structural features of the highly robust network topology from the data set through supervised learning, and on this basis, different search strategies are designed to meet the needs of different IoT scenarios. The extensive experimental results demonstrate that ROGCN can more effectively improve the robustness of scale-free IoT networks against malicious attacks compared to two existing heuristic algorithms, with a lower computational cost.

Adding links on minimum degree and longest distance strategies for improving network robustness and efficiency

Many real-world networks characterized by power-law degree distributions are extremely vulnerable against malicious attacks. Therefore, it is important to obtain effective methods for strengthening the robustness of the existing networks. Previous studies have been discussed some link addition methods for improving the robustness. In particular, two effective strategies for selecting nodes to add links have been proposed: the minimum degree and longest distance strategies. However, it is unclear whether the effects of these strategies on the robustness are independent or not. In this paper, we investigate the contributions of these strategies to improving the robustness by adding links in distinguishing the effects of degrees and distances as much as possible. Through numerical simulation, we find that the robustness is effectively improved by adding links on the minimum degree strategy for both synthetic trees and real networks. As an exception, only when the number of added links is small, the longest distance strategy is the best. Conversely, the robustness is only slightly improved by adding links on the shortest distance strategy in many cases, even combined with the minimum degree strategy. Therefore, enhancing global loops is essential for improving the robustness rather than local loops.

Knowledge-Based Prediction of Network Controllability Robustness

Network controllability robustness (CR) reflects how well a networked system can maintain its controllability against destructive attacks. Its measure is quantified by a sequence of values that record the remaining controllability of the network after a sequence of node-removal or edge-removal attacks. Traditionally, the CR is determined by attack simulations, which is computationally time-consuming or even infeasible. In this article, an improved method for predicting the network CR is developed based on machine learning using a group of convolutional neural networks (CNNs). In this scheme, a number of training data generated by simulations are used to train the group of CNNs for classification and prediction, respectively. Extensive experimental studies are carried out, which demonstrate that 1) the proposed method predicts more precisely than the classical single-CNN predictor; 2) the proposed CNN-based predictor provides a better predictive measure than the traditional spectral measures and network heterogeneity.

Fuzzy Clustering in Assortative and Disassortative Networks

Despite the significance of assortativity as a property of networks that paves for the emergence of new structural types, surprisingly, there has been little research done on assortativity. Assortative networks are perhaps among the most prominent examples of complex networks believed to be governed by common phenomena, thereby producing structures far from random. Further, certain vertices possess high centrality and can be regarded as significant and influential vertices that can become cluster centers that connect with high membership to many of the surrounding vertices. We propose a fuzzy clustering method to meaningfully characterize assortative, as well as disassortative, networks by adapting the Bonacichi’s power centrality to seek the high degree centrality vertices to become cluster centers. Moreover, we leverage our novel modularity function to determine the optimal number of clusters, as well as the optimal membership among clusters. However, due to the difficulty of finding real-world assortative network datasets that come with ground truths, we evaluated our method using synthetic data but possibly bearing resemblance to real-world network datasets as they were generated by the Lancichinetti–Fortunato–Radicchi benchmark. Our results show our non-hierarchical method outperforms a known hierarchical fuzzy clustering method, and also performs better than a well-known membership-based modularity function. Our method proved to perform beyond satisfactory for both assortative and disassortative networks.

A growth model for water distribution networks with loops

Water distribution networks (WDNs) expand their service areas over time. These growth dynamics are poorly understood. One facet of WDNs is that they have loops in general, and closing loops may be a functionally important process for enhancing their robustness and efficiency. We propose a growth model for WDNs that generates networks with loops and is applicable to networks with multiple water sources. We apply the proposed model to four empirical WDNs to show that it produces networks whose structure is similar to that of the empirical WDNs. The comparison between the empirical and modelled WDNs suggests that the empirical WDNs may realize a reasonable balance between cost, efficiency and robustness in terms of the network structure. We also study the design of pipe diameters based on a biological positive feedback mechanism. Specifically, we apply a model inspired by Physarum polycephalum to find moderate positive correlations between the empirical and modelled pipe diameters. The difference between the empirical and modelled pipe diameters suggests that we may be able to improve the performance of WDNs by following organizing principles of biological flow networks.

More Tolerant Reconstructed Networks Using Self-Healing against Attacks in Saving Resource

Complex network infrastructure systems for power supply, communication, and transportation support our economic and social activities; however, they are extremely vulnerable to frequently increasing large disasters or attacks. Thus, the reconstruction of a damaged network is more advisable than an empirically performed recovery of the original vulnerable one. To reconstruct a sustainable network, we focus on enhancing loops so that they are not trees, which is made possible by node removal. Although this optimization corresponds with an intractable combinatorial problem, we propose self-healing methods based on enhancing loops when applying an approximate calculation inspired by statistical physics. We show that both higher robustness and efficiency are obtained in our proposed methods by saving the resources of links and ports when compared to ones in conventional healing methods. Moreover, the reconstructed network can become more tolerant than the original when some damaged links are reusable or compensated for as an investment of resource. These results present the potential of network reconstruction using self-healing with adaptive capacity in terms of resilience.

Maximizing Network Resilience against Malicious Attacks

The threat of a malicious attack is one of the major security problems in complex networks. Resilience is the system-level self-adjusting ability of a complex network to retain its basic functionality and recover rapidly from major disruptions. Despite numerous heuristic enhancement methods, there is a research gap in maximizing network resilience: current heuristic methods are designed to immunize vital nodes or modify a network to a specific onion-like structure and cannot maximize resilience theoretically via network structure. Here we map complex networks onto a physical elastic system to introduce indices of network resilience, and propose a unified theoretical framework and general approach, which can address the optimal problem of network resilience by slightly modifying network structures (i.e., by adding a set of structural edges). We demonstrate the high efficiency of this approach on three realistic networks as well as two artificial random networks. Case studies show that the proposed approach can maximize the resilience of complex networks while maintaining their topological functionality. This approach helps to unveil hitherto hidden functions of some inconspicuous components, which in turn, can be used to guide the design of resilient systems, offer an effective and efficient approach for mitigating malicious attacks, and furnish self-healing to reconstruct failed infrastructure systems.

Onion-like networks are both robust and resilient

Tolerant connectivity and flow transmission within capacity are crucial functions as network. However, the threats to malicious attacks based on intelligent node selections and rapid breakdown by cascading overload failures increase more and more with large blackout or congestion in our contemporary networking systems and societies. It has been recently suggested that interwoven loops protect the network functions from such damages, but it is a computationally intractable combinatorial problem to maximize a set of necessary nodes for loops in order to improve the robustness. We propose a new method by enhancing loops in the incremental growth for constructing onion-like networks with positive degree-degree correlations, whose topological structure has the optimal tolerance of connectivity against attacks in the state-of-the-art. Moreover, we find out that onion-like networks acquire adaptive capacity in resilience by a change of routing policy for flow control to absorb cascading overload failures triggered by a single attack and simultaneous multi-attacks. The inhibitory effect is stronger than that in scale-free networks found in many real systems.

General formulation of long-range degree correlations in complex networks

We provide a general framework for analyzing degree correlations between nodes separated by more than one step (i.e., beyond nearest neighbors) in complex networks. One joint and four conditional probability distributions are introduced to fully describe long-range degree correlations with respect to degrees k and k^{'} of two nodes and shortest path length l between them. We present general relations among these probability distributions and clarify the relevance to nearest-neighbor degree correlations. Unlike nearest-neighbor correlations, some of these probability distributions are meaningful only in finite-size networks. Furthermore, as a baseline to determine the existence of intrinsic long-range degree correlations in a network other than inevitable correlations caused by the finite-size effect, the functional forms of these probability distributions for random networks are analytically evaluated within a mean-field approximation. The utility of our argument is demonstrated by applying it to real-world networks.

Cascading Failures in Interdependent Networks with Multiple Supply-Demand Links and Functionality Thresholds

Various social, financial, biological and technological systems can be modeled by interdependent networks. It has been assumed that in order to remain functional, nodes in one network must receive the support from nodes belonging to different networks. So far these models have been limited to the case in which the failure propagates across networks only if the nodes lose all their supply nodes. In this paper we develop a more realistic model for two interdependent networks in which each node has its own supply threshold, i.e., they need the support of a minimum number of supply nodes to remain functional. In addition, we analyze different conditions of internal node failure due to disconnection from nodes within its own network. We show that several local internal failure conditions lead to similar nontrivial results. When there are no internal failures the model is equivalent to a bipartite system, which can be useful to model a financial market. We explore the rich behaviors of these models that include discontinuous and continuous phase transitions. Using the generating functions formalism, we analytically solve all the models in the limit of infinitely large networks and find an excellent agreement with the stochastic simulations.

Structural instability of large-scale functional networks

We study how large functional networks can grow stably under possible cascading overload failures and evaluated the maximum stable network size above which even a small-scale failure would cause a fatal breakdown of the network. Employing a model of cascading failures induced by temporally fluctuating loads, the maximum stable size n_max has been calculated as a function of the load reduction parameter r that characterizes how quickly the total load is reduced during the cascade. If we reduce the total load sufficiently fast (r ≥ r_c), the network can grow infinitely. Otherwise, n_max is finite and increases with r. For a fixed r(< r_c), n_max for a scale-free network is larger than that for an exponential network with the same average degree. We also discuss how one detects and avoids the crisis of a fatal breakdown of the network from the relation between the sizes of the initial network and the largest component after an ordinarily occurring cascading failure.

Fragmentation properties of two-dimensional proximity graphs considering random failures and targeted attacks

The pivotal quality of proximity graphs is connectivity, i.e., all nodes in the graph are connected to one another either directly or via intermediate nodes. These types of graphs are often robust, i.e., they are able to function well even if they are subject to limited removal of elementary building blocks, as may occur for random failures or targeted attacks. Here, we study how the structure of these graphs is affected when nodes get removed successively until an extensive fraction is removed such that the graphs fragment. We study different types of proximity graphs for various node-removal strategies. We use different types of observables to monitor the fragmentation process, simple ones like the number and sizes of connected components and more complex ones like the hop diameter and the backup capacity, which is needed to make a network N-1 resilient. The actual fragmentation turns out to be described by a second-order phase transition. Using finite-size scaling analyses we numerically assess the threshold fraction of removed nodes, which is characteristic for the particular graph type and node deletion scheme; this suffices to decompose the underlying graphs.

Mitigate Cascading Failures on Networks using a Memetic Algorithm

Research concerning cascading failures in complex networks has become a hot topic. However, most of the existing studies have focused on modelling the cascading phenomenon on networks and analysing network robustness from a theoretical point of view, which considers only the damage incurred by the failure of one or several nodes. However, such a theoretical approach may not be useful in practical situation. Thus, we first design a much more practical measure to evaluate the robustness of networks against cascading failures, termed Rcf. Then, adopting Rcf as the objective function, we propose a new memetic algorithm (MA) named MA-Rcf to enhance network the robustness against cascading failures. Moreover, we design a new local search operator that considers the characteristics of cascading failures and operates by connecting nodes with a high probability of having similar loads. In experiments, both synthetic scale-free networks and real-world networks are used to test the efficiency and effectiveness of the MA-Rcf. We systematically investigate the effects of parameters on the performance of the MA-Rcf and validate the performance of the newly designed local search operator. The results show that the local search operator is effective, that MA-Rcf can enhance network robustness against cascading failures efficiently, and that it outperforms existing algorithms.

Robustness analysis of bimodal networks in the whole range of degree correlation

We present an exact analysis of the physical properties of bimodal networks specified by the two peak degree distribution fully incorporating the degree-degree correlation between node connections. The structure of the correlated bimodal network is uniquely determined by the Pearson coefficient of the degree correlation, keeping its degree distribution fixed. The percolation threshold and the giant component fraction of the correlated bimodal network are analytically calculated in the whole range of the Pearson coefficient from -1 to 1 against two major types of node removal, which are the random failure and the degree-based targeted attack. The Pearson coefficient for next-nearest-neighbor pairs is also calculated, which always takes a positive value even when the correlation between nearest-neighbor pairs is negative. From the results, it is confirmed that the percolation threshold is a monotonically decreasing function of the Pearson coefficient for the degrees of nearest-neighbor pairs increasing from -1 and 1 regardless of the types of node removal. In contrast, the node fraction of the giant component for bimodal networks with positive degree correlation rapidly decreases in the early stage of random failure, while that for bimodal networks with negative degree correlation remains relatively large until the removed node fraction reaches the threshold. In this sense, bimodal networks with negative degree correlation are more robust against random failure than those with positive degree correlation.

Hardness Analysis and Empirical Studies of the Relations among Robustness, Topology and Flow in Dynamic Networks

Network robustness is the ability of a network to maintain performance after disruption, thus it is an important index for network designers to refer to. Every actual network has its own topology structure, flow magnitude (scale) and flow distribution. How the robustness relates to these factors still remains unresolved. To analyze the relations, we first established a robustness problem model, studied the hardness of a special case of the model, and generated a lot of representative network instances. We conducted experiments on these instances, deleting 5% to 50% edges on each instance and found that the robustness of a network has an approximate linearity to its structural entropy and flow entropy, when the correlation coefficient between the structure and flow is fixed. We also found that robustness is unlikely to have a relation to the flow scale and edge scale in our model. The empirical studies thus can provide a way of quickly estimating the robustness of real-world networks by using the regression coefficients we obtained during the experiments. We conducted computation on a real-world dataset and got favorable results, which exhibited the effectiveness of the estimation.

Precise calculation of a bond percolation transition and survival rates of nodes in a complex network

Through precise numerical analysis, we reveal a new type of universal loopless percolation transition in randomly removed complex networks. As an example of a real-world network, we apply our analysis to a business relation network consisting of approximately 3,000,000 links among 300,000 firms and observe the transition with critical exponents close to the mean-field values taking into account the finite size effect. We focus on the largest cluster at the critical point, and introduce survival probability as a new measure characterizing the robustness of each node. We also discuss the relation between survival probability and k-shell decomposition.

Mandala networks: ultra-small-world and highly sparse graphs

The increasing demands in security and reliability of infrastructures call for the optimal design of their embedded complex networks topologies. The following question then arises: what is the optimal layout to fulfill best all the demands? Here we present a general solution for this problem with scale-free networks, like the Internet and airline networks. Precisely, we disclose a way to systematically construct networks which are robust against random failures. Furthermore, as the size of the network increases, its shortest path becomes asymptotically invariant and the density of links goes to zero, making it ultra-small world and highly sparse, respectively. The first property is ideal for communication and navigation purposes, while the second is interesting economically. Finally, we show that some simple changes on the original network formulation can lead to an improved topology against malicious attacks.

Dynamics on modular networks with heterogeneous correlations

We develop a new ensemble of modular random graphs in which degree-degree correlations can be different in each module, and the inter-module connections are defined by the joint degree-degree distribution of nodes for each pair of modules. We present an analytical approach that allows one to analyze several types of binary dynamics operating on such networks, and we illustrate our approach using bond percolation, site percolation, and the Watts threshold model. The new network ensemble generalizes existing models (e.g., the well-known configuration model and Lancichinetti-Fortunato-Radicchi networks) by allowing a heterogeneous distribution of degree-degree correlations across modules, which is important for the consideration of nonidentical interacting networks.

Cavity-based robustness analysis of interdependent networks: influences of intranetwork and internetwork degree-degree correlations

We develop a methodology for analyzing the percolation phenomena of two mutually coupled (interdependent) networks based on the cavity method of statistical mechanics. In particular, we take into account the influence of degree-degree correlations inside and between the networks on the network robustness against targeted (random degree-dependent) attacks and random failures. We show that the developed methodology is reduced to the well-known generating function formalism in the absence of degree-degree correlations. The validity of the developed methodology is confirmed by a comparison with the results of numerical experiments. Our analytical results indicate that the robustness of the interdependent networks depends on both the intranetwork and internetwork degree-degree correlations in a nontrivial way for both cases of random failures and targeted attacks.

Hierarchical scale-free network is fragile against random failure

We investigate site percolation in a hierarchical scale-free network known as the Dorogovtsev-Goltsev-Mendes network. We use the generating function method to show that the percolation threshold is 1, i.e., the system is not in the percolating phase when the occupation probability is less than 1. The present result is contrasted to bond percolation in the same network of which the percolation threshold is zero. We also show that the percolation threshold of intentional attacks is 1. Our results suggest that this hierarchical scale-free network is very fragile against both random failure and intentional attacks. Such a structural defect is common in many hierarchical network models.

Robustness of cooperation on scale-free networks under continuous topological change

In this paper, we numerically investigate the robustness of cooperation clusters in prisoner's dilemma played on scale-free networks, where the network topologies change by continuous removal and addition of nodes. Each removal and addition can be either random or intentional. We therefore have four different strategies in changing network topology: random removal and random addition (RR), random removal and preferential addition (RP), targeted removal and random addition (TR), and targeted removal and preferential addition (TP). We find that cooperation clusters are most fragile against TR, while they are most robust against RP, even for large values of the temptation coefficient for defection. The effect of the degree mixing pattern of the network is not the primary factor for the robustness of cooperation under continuous change in network topology, which is quite different from the cases observed in static networks. Cooperation clusters become more robust as the number of links of hubs occupied by cooperators increase. Our results might infer the fact that a huge variety of individuals is needed for maintaining global cooperation in social networks in the real world where each node representing an individual is constantly removed and added.

Observability transitions in correlated networks

Yang, Wang, and Motter [Phys. Rev. Lett. 109, 258701 (2012)] analyzed a model for network observability transitions in which a sensor placed on a node makes the node and the adjacent nodes observable. The size of the connected components comprising the observable nodes is a major concern of the model. We analyze this model in random heterogeneous networks with degree correlation. With numerical simulations and analytical arguments based on generating functions, we find that negative degree correlation makes networks more observable. This result holds true both when the sensors are placed on nodes one by one in a random order and when hubs preferentially receive the sensors. Finally, we numerically optimize networks with a fixed degree sequence with respect to the size of the largest observable component. Optimized networks have negative degree correlation induced by the resulting hub-repulsive structure; the largest hubs are rarely connected to each other, in contrast to the rich-club phenomenon of networks.

Quantitative modeling of degree-degree correlation in complex networks

This paper presents an approach to the modeling of degree-degree correlation in complex networks. Thus, a simple function, Δ(k', k), describing specific degree-to-degree correlations is considered. The function is well suited to graphically depict assortative and disassortative variations within networks. To quantify degree correlation variations, the joint probability distribution between nodes with arbitrary degrees, P(k', k), is used. Introduction of the end-degree probability function as a basic variable allows using group theory to derive mathematical models for P(k', k). In this form, an expression, representing a family of seven models, is constructed with the needed normalization conditions. Applied to Δ(k', k), this expression predicts a nonuniform distribution of degree correlation in networks, organized in two assortative and two disassortative zones. This structure is actually observed in a set of four modeled, technological, social, and biological networks. A regression study performed on 15 actual networks shows that the model describes quantitatively degree-degree correlation variations.

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).