Session A54: Focus Session: Complex and Co-evolving Networks - Cascades in Networks

Percolation of Double-Layer Networks with Different Topologies Under Random Attacks

We report on the effects of topology on failure propagation models for systems consisting of two interdependent networks, which are either SF networks with different parameters, or different types of networks. Pairs of interdependent networks are known to exhibit a percolation transition upon failure accumulation. The topology of the nets significantly change the critical density of failure for the total disruption of the two net composite system. When the system is not fully coupled, the existence of a very small fraction of SF network will hold the system from fragment. When the critical threshold $p_c$ doesn't change, robustness measure R is introduced. The consequences of the study may provide insights for future network architectures and their evolution to improve their robustness and enhancing the protection of critical infrastructure.   

Statistics of interacting networks with extreme preferred degrees: Simulation results and theoretical approaches

Network studies have played a central role for understanding many systems in nature - e.g., physical, biological, and social. So far, much of the focus has been the statistics of networks in isolation. Yet, many networks in the world are coupled to each other. Recently, we considered this issue, in the context of two interacting social networks. In particular, We studied networks with two different preferred degrees, modeling, say, introverts vs. extroverts, with a variety of ``rules for engagement.'' As a first step towards an analytically accessible theory, we restrict our attention to an ``extreme scenario'': The introverts prefer zero contacts while the extroverts like to befriend everyone in the society. In this ``maximally frustrated'' system, the degree distributions, as well as the statistics of cross-links (between the two groups), can depend sensitively on how a node (individual) creates/breaks its connections. The simulation results can be reasonably well understood in terms of an approximate theory.   

Correlated multiplexity in random and co-evolving multiplex networks

Nodes in a complex networked system often engage in multiple types f interactions among them; they form a {\it multiplex} network with multiple layers that can be interdependent and co-evolve. In many real-world complex systems, such multiple network layers are not randomly coupled but correlated. Such a correlated multiplexity can imprint nontrivial structural correlations in the multiplex network, which in turn can impact the dynamical processes on it. Here we present some recent results on the correlated multiplexity in multiplex networks. First we show how the correlated multiplexity can dramatically alter the giant component properties of multiplex random networks. Secondly we introduce an evolution model of co-evolving multiplex networks by generalizing the well-known Barab\'asi-Albert-type model, to show how the co-evolution of network layers can induce and modulate the degree of correlated multiplexity.   

Cascades of overload failures in spatial networks

Our daily life imposes increasing demands on infrastructural networks such as the power grid, transportation network, water supply, etc. Understanding the vulnerabilities of these systems is crucial to securing them. To this end, we study the effect of spatial constraints on network resilience against cascading overloads. Specifically, we consider distributed and shortest path flows on spatially embedded networks and study the model of cascading failures (Motter and Lai (2002)) triggered by the removal of a single or multiple nodes. We present results of intentional attacks on highly loaded and high degree nodes as well as a comparison between spatially concentrated and randomly distributed, multiple attacks.   

Multiplexity-facilitated cascade dynamics in networks

Most complex network studies thus far have been focused on single-layer framework. It becomes increasingly clearly, however, that many real-world complex systems are {\it multiplex} ---nodes interact with multiple types of interactions (links) which coexist, co-depend, and co-evolve. The interplay of such multiplex interactions may confer nontrivial consequences on network dynamics. Here we present recent results on how such multiplexity affects cascade dynamics on networks. We found the cascasde progression is greatly facilitated by multiplexity. Layers that are unable to achieve global cascades in isolation can cooperatively achieve them by multiplex coupling. Therefore, the multiplex network can be dramatically more vulnerable to global cascades than single-layer or simplex networks. Implication of these results on cascade prediction and control in social and economic dynamics is also discussed.   

Cascades of failures in various models of interdependent networks

Complex networks appear in almost every aspect of science and technology. Recently an analytical framework for studying the percolation properties of interacting networks has been developed [1]. These studies however have several limitations. The real networks do are not randomly connected. They are often embedded into two dimensional space. The dependency links are not connecting nodes at random but have tendency to connect nodes with similar degrees, or nodes which are close to each other in Euclidian space. Moreover, the network failures may occur not only to the loss of connectivity but also due to overload of nodes with high betweennes. We have study these situations analytically and by computer simulations and found the conditions at which networks collapse in an abrupt first order like transition when the entire network becomes non-functional or fail gradually like in a second order transition as a greater fraction of nodes is removed in the initial attack or failure. \\[4pt] [1] \textbf{S. V. Buldyrev}, R. Parshani, G. Paul, H. E. Stanley, and S. Havlin, ``Catastrophic cascade of failures in interdependent networks,'' \textit{Nature} \textbf{464}, 1025-1028 (2010)   

Robustness of a Network of Networks

Network research has been focused on studying the properties of a single isolated network, which rarely exists. We develop a general analytical framework for studying percolation of $n$ interdependent networks. We illustrate our analytical solutions for three examples: (i) For any tree of $n$ fully dependent Erd\H{o}s-R\'{e}nyi (ER) networks, each of average degree $\bar{k}$, we find that the giant component $P_{\infty}=p[1-\exp(-\bar{k}P_{\infty})]^n$ where $1 - p$ is the initial fraction of removed nodes. This general result coincides for $n = 1$ with the known second-order phase transition for a single network. For any $n>1$ cascading failures occur and the percolation becomes an abrupt first-order transition. (ii) For a starlike network of n partially interdependent ER networks, $P_{\infty}$ depends also on the topology--in contrast to case (i). (iii) For a looplike network formed by $n$ partially dependent ER networks, $P_{\infty}$ is independent of $n$.   

Robustness of interdependent networks under targeted attack

When an initial failure of nodes occurs in interdependent networks, a cascade of failure between the networks occurs. Earlier studies focused on random initial failures. Here we study the robustness of interdependent networks under targeted attack on high or low degree nodes. We introduce a general technique which maps the targeted-attack problem in interdependent networks to the random-attack problem in a transformed pair of interdependent networks. We find that when the highly connected nodes are protected and have lower probability to fail, in contrast to single scale-free (SF) networks where the percolation threshold $p_c=0$, coupled SF networks are significantly more vulnerable with $p_c$ significantly larger than zero. The result implies that interdependent networks are difficult to defend by strategies such as protecting the high degree nodes that have been found useful to significantly improve robustness of single networks.   

Information Spreading in Context

Information spreading processes are central to human interactions. Despite recent studies in online domains, little is known about factors that could affect the dissemination of a single piece of information. In this paper, we address this challenge by combining two related but distinct datasets, collected from a large scale privacy-preserving distributed social sensor system. We find that the social and organizational context significantly impacts to whom and how fast people forward information. Yet the structures within spreading processes can be well captured by a simple stochastic branching model, indicating surprising independence of context. Our results build the foundation of future predictive models of information flow and provide significant insights towards design of communication platforms.   

Power-grid Network Partitioning and Cluster Optimization with Applications to Florida and Texas

Cascading power-grid failures pose serious threats to lives and property, and it is desirable to contain them within a limited geographical area. One method to achieve this is Intelligent Intentional Islanding (I3): the purposeful partitioning of a grid into weakly connected ``islands'' of closely connected generators and loads. If such islands can be quickly isolated, the spread of faults can be limited. An additional constraint is that generating capacity and power demand within each island should be closely balanced to ensure self-sufficiency. I3 thus corresponds to constrained community detection in a network. After a matrix-based initial agglomeration of nearby loads and generators, we implement Monte Carlo simulated annealing to simultaneously optimize load-balance and internal connectivity of the resulting islands. The optimized network of islands is treated as a new network with the first-generation islands as the new nodes (``supergenerators'' and ``superloads''), and the same agglomeration and MC procedures are iteratively applied, reminiscent of real-space renormalization. Applications to the Floridian [1] and Texan high-voltage grids are demonstrated.\\[4pt] [1] I.\ Abou Hamad et al., Phys.\ Proc.\ {\bf 4}, 125-129 (2010); Phys.\ Proc.\ {\bf 15}, 2-6 (2011).   

Computational Analysis of Topological Survivability of Large-Scale Engineering Networks with Heterogeneous Nodes

The scale and complexity of modern networks, their integration, and the size of population and businesses they have impact on, make their massive damage catastrophic for the society and economy. Such damage is usually caused by adverse events and is not considered by traditional design practices. In the modern society, the likelihood of adverse events has substantially increased. Therefore, there is a need in evaluating the ability of a network to survive such damage. As the network topology is a key factor to consider, the goal of our research is to develop computational tools for quantifying its effect on the network survivability. ``Selfish'' algorithm will be presented that addresses exponential-time complexity associated with the problem of generation and analysis of all fault combinations possible in a given network. The reduction of computational complexity is achieved by mapping an initial network topology with multiple sources and sinks onto a set of simpler smaller topologies with multiple sources and a single sink. Application to the Texas power grid will be considered.   

Cascading failures in interdependent lattice networks: from first order to second order phase transition

We study a system composed of two interdependent lattice networks A and B, where nodes in network A depend on a node within a certain shuffling distance $r$ of its corresponding counterpart in network B and vice versa. We find, using numerical simulation that percolation in the two interdependent lattice networks system shows that for small $r$ the phase transition is second order while for larger $r$ it is a first order.   

Cascading behaviors in random directed dependency networks

Cascading behaviors have been studied only for some specific dependency network systems. In this paper, we present a more general and realistic network system with both random connectivity and directed dependency links. Using percolation approach, we obtained the universal boundaries among first order transition, second order transition and unstable regimes, which depend only on less than fourth moment of degree distribution and the fractions of zero and one directed dependency link nodes. Moreover, besides the connectivity degree distribution, we also find the final state of dynamical cascading process is determined by out degree distribution of directed dependency links, and the in degree distribution only influence cascading speed.   

Loops in hierarchical channel networks

Nature provides us with many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture. Although a number of methods have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated and natural graphs extracted from digitized images of dicotyledonous leaves and animal vasculature. We calculate various metrics on the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.