Percolation of interdependent network of networks

Complex networks appear in almost every aspect of science and technology. Previous work in network theory has focused primarily on analyzing single networks that do not interact with other networks, despite the fact that many real-world networks interact with and depend on each other. Very recently an analytical framework for studying the percolation properties of interacting networks has been introduced. Here we review the analytical framework and the results for percolation laws for a Network Of Networks (NONs) formed by n interdependent random networks. The percolation properties of a network of networks differ greatly from those of single isolated networks. In particular, because the constituent networks of a NON are connected by node dependencies, a NON is subject to cascading failure. When there is strong interdependent coupling between networks, the percolation transition is discontinuous (first-order) phase transition, unlike the well-known continuous second-order transition in single isolated networks. Moreover, although networks with broader degree distributions, e.g., scale-free networks, are more robust when analyzed as single networks, they become more vulnerable in a NON. We also review the effect of space embedding on network vulnerability. It is shown that for spatially embedded networks any finite fraction of dependency nodes will lead to abrupt transition.     

Minimum vertex cover problem for coupled interdependent networks with cascading failures

This paper defines and analyzes a generalization of the classical minimum vertex cover problem to the case of two-layer interdependent networks with cascading node failures that can be caused by two common types of interdependence. Previous studies on interdependent networks mainly addressed the issues of cascading failures from a numerical simulations perspective, whereas this paper proposes an exact optimization-based approach for identifying a minimum-cardinality set of nodes, whose deletion would effectively disable both network layers through cascading failure mechanisms. We analyze the computational complexity and linear 0–1 formulations of the defined problems, as well as prove an LP approximation ratio result that generalizes the well-known 2-approximation for the classical minimum vertex cover problem. In addition, we introduce the concept of a “depth of cascade” (i.e., the maximum possible length of a sequence of cascading failures for a given interdependent network) and show that for any problem instance this parameter can be explicitly derived via a polynomial-time procedure.     

Vulnerability of complex networks

We consider normalized average edge betweenness of a network as a metric of network vulnerability. We suggest that normalized average edge betweenness together with is relative difference when certain number of nodes and/or edges are removed from the network is a measure of network vulnerability, called vulnerability index. Vulnerability index is calculated for four synthetic networks: Erdős–Rényi (ER) random networks, Barabási–Albert (BA) model of scale-free networks, Watts–Strogatz (WS) model of small-world networks, and geometric random networks. Real-world networks for which vulnerability index is calculated include: two human brain networks, three urban networks, one collaboration network, and two power grid networks. We find that WS model of small-world networks and biological networks (human brain networks) are the most robust networks among all networks studied in the paper.     

Effect of clustering on attack vulnerability of interdependent scale-free networks

In order to deeply understand the complex interdependent systems, it is of great concern to take clustering coefficient, which is an important feature of many real-world systems, into account. Previous study mainly focused on the impact of clustering on interdependent networks under random attacks, while we extend the study to the case of the more realistic attacking strategy, targeted attack. A system composed of two interdependent scale-free networks with tunable clustering is provided. The effects of coupling strength and coupling preference on attack vulnerability are explored. Numerical simulation results demonstrate that interdependent links between two networks make the entire system much more fragile to attacks. Also, it is found that clustering significantly increases the vulnerability of interdependent scale-free networks. Moreover, for fully coupled network, disassortative coupling is found to be most vulnerable to random attacks, while the random and assortative coupling have little difference. Additionally, enhancing coupling strength can greatly enhance the fragility of interdependent networks against targeted attacks. These results can not only improve the deep understanding of structural complexity of complex systems, but also provide insights into the guidance of designing resilient infrastructures.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

Application of modal analysis in assessing attack vulnerability of complex networks

In this paper we propose an alternative way to study robustness and vulnerability of complex networks, applying a modal analysis. The modal weights of the network nodes are considered as a measure for their busyness, which is further used for preferential removal of nodes and attack simulation. Analyses of the attack vulnerability are carried out for several generic graphs, generated according to ER and BA algorithms, as well as for some examples of manmade networks. It was found that a modal weight based attack causes significant disintegration of manmade networks by removing a small fraction of the busiest nodes, comparable to the one based on the node degree and betweenness centrality.     

A unified network performance measure with importance identification and the ranking of network components

In this paper, we propose the first network performance measure that can be used to assess the efficiency of a network in the case of either fixed or elastic demands. Such a measure is needed for many different applications since only when the performance of a network can be quantifiably measured can the network be appropriately managed. Moreover, as we demonstrate, the proposed performance measure, which captures flow information and behavior, allows one to determine the criticality of various nodes (as well as links) through the identification of their importance and ranking. We present specific networks for which the performance/efficiency is computed along with the importance rankings of the nodes and links. The new measure can be applied to transportation networks, supply chains, financial networks, electric power generation and distribution networks as well as to the Internet and can be used to assess the vulnerability of a network to disruptions.     

Random walks on finitely structured transfinite networks

A general theory for random walks on transfinite networks whose ranks are arbitrary natural numbers is established herein. In such networks, nodes of higher ranks connect together transfinite networks of lower ranks. The probabilities for transitions through such nodes are obtained as extensions of the Nash-Williams rule for random walks on ordinary infinite networks. The analysis is based on the theory of transfinite electrical networks, but it requires that the transfinite network have a structure that generalizes local-finiteness for ordinary infinite networks. The shorting together of nodes of different ranks are allowed; this complicates transitions through such nodes but provides a considerably more general theory. It is shown that, with respect to any finite set of nodes of any ranks, a transfinite random walk can be represented by an irreducible reversible Makov chain, whose state space is that set of nodes.This work was supported by the National Science Foundation under the grants DMS-9200738 and MIP-9200748.     

Pancake网络的t/k-诊断度及其算法

由于大型多处理机系统规模的不断扩大, 其组件脆弱性也随之增加, 因此故障容错性能对于多处理机系统尤为重要. t/k-诊断分析是一种能极大提高多处理机系统自我诊断性能的系统级故障诊断策略,该诊断策略能识别至多t个故障处理机节点, 其中可能包含至多$k$个被误诊的处理机. 首先给出了Pancake网络P_n(n\geq 5) 的容错性分析, 其后证明了P_n在PMC模型下是((k+1)n-3k-1)/k-可诊断的, 其中1\leq k\leq 3, 最后还给出复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点.     

Queue length and occupancy in discrete-time cyclic networks with several types of nodes

For a discrete-time, closed, cyclic queueing network, where the nodes have independent, geometric service times, the equilibrium rate of local progress is determined. Faster nodes are shown to have a capacity depending only on the service probabilities. A family of such networks, each with the same number of types of nodes, is analyzed. If the number of nodes approaches infinity, and if the ratio of jobs to nodes has a positive limit and each node type has an asymptotic density, then for a given node type, the limits of the proportion of occupied nodes and the expected queue length are calculated. These values depend on the service parameter and on the asymptotic rate of local progress. The faster nodes can attain their capacity only when the limiting density of nodes of slowest type is zero. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the topologic structure of economic complex networks: Empirical evidence from large scale payment network of Estonia

This paper presents the first topological analysis of the economic structure of an entire country based on payments data obtained from Swedbank. This data set is exclusive in its kind because around 80% of Estonia's bank transactions are done through Swedbank; hence, the economic structure of the country can be reconstructed. Scale-free networks are commonly observed in a wide array of different contexts such as nature and society. In this paper, the nodes are comprised by customers of the bank (legal entities) and the links are established by payments between these nodes. We study the scaling-free and structural properties of this network. We also describe its topology, components and behaviors. We show that this network shares typical structural characteristics known in other complex networks: degree distributions follow a power law, low clustering coefficient and low average shortest path length. We identify the key nodes of the network and perform simulations of resiliency against random and targeted attacks of the nodes with two different approaches. With this, we find that by identifying and studying the links between the nodes is possible to perform vulnerability analysis of the Estonian economy with respect to economic shocks.     

Robust synchronization of singular complex switched networks with parametric uncertainties and unknown coupling topologies via impulsive control

This paper presents a general model of singular complex switched networks, in which the nodes can be singular dynamic systems and switching behaviors act on both nodes and edges. The parametric uncertainties and unknown coupling topologies are also considered in this model. Two robust synchronization schemes are discussed respectively. In one scheme, the network is synchronized to a homogeneous orbit and in the other one the network is synchronized to a weighted average of all the nodes. Based on the Lyapunov stability theory, different robust synchronization conditions for the two schemes are obtained for this singular complex switched network model via impulsive control. The similarities and differences between these synchronization conditions for the two schemes are discussed. In addition, three useful robust results for the special cases of the singular complex switched networks are presented. Two systematic-design procedures are presented for the two schemes, and three numerical examples are provided for illustrations.     

Cluster mixed synchronization via pinning control and adaptive coupling strength in community networks with nonidentical nodes

In this paper, complex networks with community structure and nonidentical nodes are investigated. The cluster mixed synchronization of these networks is studied by using some linear pinning control schemes. Only the nodes in one community which have direct connections to the nodes in other communities are controlled. Adaptive coupling strength method is adopted to achieve the synchronization as well. According to Lyapunov stability theory, several sufficient conditions for the network to achieve cluster mixed synchronization are derived. Numerical simulations are provided to verify the correctness and the effectiveness of the theoretical results.     

Spreading of epidemics on scale-free networks with nonlinear infectivity

In this paper, we study the spreading of epidemics on scale-free networks with infectivity which is nonlinear in the connectivity of nodes. We will show that the nonlinear infectivity is more appropriate than constant or linear ones, and give the epidemic threshold of the SIS model on a scale-free network with nonlinear infectivity. In addition, we compare the effects of nonlinear infectivity on the epidemic threshold with two other cases on infinite and finite scale-free networks, and find some new results, such as: with unit recovery rate and nonlinear irrational infectivity, the epidemic threshold is always positive; and the epidemic threshold can increase with network size on finite networks, contrary to the findings in all previous work.     

An introduction to dynamic generative networks: Minimum cost flow

What we are dealing with is a class of networks called dynamic generative network flows in which the flow commodity is dynamically generated at source nodes and dynamically consumed at sink nodes. As a basic assumption, the source nodes produce the flow according to time generative functions and the sink nodes absorb the flow according to time consumption functions. This paper tries to introduce these networks and formulate minimum cost dynamic flow problem for a pre-specified time horizon T. Finally, some simple, efficient approaches are developed to solve the dynamic problem, in the general form when the capacities and costs are time varying and some other special cases, as a minimum cost static flow problem.     

A network efficiency measure with application to critical infrastructure networks

In this paper, we demonstrate how a new network performance/efficiency measure, which captures demands, flows, costs, and behavior on networks, can be used to assess the importance of network components and their rankings. We provide new results regarding the measure, which we refer to as the Nagurney–Qiang measure, or, simply, the N–Q measure, and a previously proposed one, which did not explicitly consider demands and flows. We apply both measures to such critical infrastructure networks as transportation networks and the Internet and further explore the new measure through an application to an electric power generation and distribution network in the form of a supply chain. The Nagurney and Qiang network performance/efficiency measure that captures flows and behavior can identify which network components, that is, nodes and links, have the greatest impact in terms of their removal and, hence, are important from both vulnerability as well as security standpoints.     

Structural balance in fully signed networks

Node attributes play an important role in shaping network structures, but are generally ignored in transformations of structural balance. A fully signed network consisting of signs of edges and nodes expresses both properties of relationship and node attributes. In this article, we generalize the definition of structural balance in fully signed networks. We transform the unbalanced fully signed network by not only changing signs of edges but also changing the signs of nodes. We propose a memetic algorithm to transform unbalanced networks at the lowest cost. Experiments show that our algorithm can solve this problem efficiently, and different node attribute assignments may lead to different optimized structures. © 2016 Wiley Periodicals, Inc. Complexity 21: 497–511, 2016     

Quantifying the complexity of flow networks: How many roles are there?

Weighted flow networks are structures that arise naturally when analyzing complex systems. The countable properties of unweighted networks are not easily generalized to weighted networks. One candidate measure of complexity is the number of roles, or specialized functions in a network. It is easy to identify the number of roles in a linear or cyclic unweighted network. There is only one logically consistent way to generalize the measures of nodes, flows, connectivity, and roles into weighted networks, and these generalizations are equivalent to indices derived from information theory and used by ecologists since the late seventies. Data from ecosystem networks suggests that ecosystems inhabit a narrow window of the parameter space defined by these measures. © 2003 Wiley Periodicals, Inc.     

Partition inequalities for capacitated survivable network design based on directed p-cycles

We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the p-cycles.

We describe a model for designing capacitated survivable networks based on directed p-cycles. We motivate this model by comparing it with other means of ensuring survivability, and present a mixed-integer programming formulation for it. We derive valid inequalities for the model based on the minimum capacity requirement between partitions of the nodes and give facet conditions for them. We discuss the separation for these inequalities and present results of computational experiments for testing their effectiveness as cutting planes when incorporated in a branch-and-cut algorithm. Our experiments show that the proposed inequalities reduce the computational effort significantly.     

Location tracking in mobile ad hoc networks using particle filters

Mobile ad hoc networks (MANETs) are dynamic networks formed on-the-fly as mobile nodes move in and out of each others' transmission ranges. In general, the mobile ad hoc networking model makes no assumption that nodes know their own locations. However, recent research shows that location-awareness can be beneficial to fundamental tasks such as routing and energy-conservation. On the other hand, the cost and limited energy resources associated with common, low-cost mobile nodes prohibits them from carrying relatively expensive and power-hungry location-sensing devices such as GPS. This paper proposes a mechanism that allows non-GPS-equipped nodes in the network to derive their approximated locations from a limited number of GPS-equipped nodes. In our method, all nodes periodically broadcast their estimated location, in terms of a compressed particle filter distribution. Non-GPS nodes estimate the distance to their neighbors by measuring the received signal strength of incoming messages. A particle filter is then used to estimate the approximated location, along with a measure of confidence, from the sequence of distance estimates. Simulation studies show that our solution is capable of producing good estimates equal or better than the existing localization methods such as APS-Euclidean for the more difficult scenario when the network connectivity is low.