1
|
Meng T, Duan G, Li A. Target control of complex networks: How to save control energy. Phys Rev E 2023; 108:014301. [PMID: 37583158 DOI: 10.1103/physreve.108.014301] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/21/2023] [Accepted: 06/06/2023] [Indexed: 08/17/2023]
Abstract
Controlling complex networks has received much attention in the past two decades. In order to control complex networks in practice, recent progress is mainly focused on the control energy required to drive the associated system from an initial state to any final state within finite time. However, one of the major challenges when controlling complex networks is that the amount of control energy is usually prohibitively expensive. Previous explorations on reducing the control energy often rely on adding more driver nodes to be controlled directly by external control inputs, or reducing the number of target nodes required to be controlled. Here we show that the required control energy can be reduced exponentially by appropriately setting the initial states of uncontrollable nodes for achieving the target control of complex networks. We further present the energy-optimal initial states and theoretically prove their existence for any structure of network. Moreover, we demonstrate that the control energy could be saved by reducing the distance between the energy-optimal states set and the initial states of uncontrollable nodes. Finally, we propose a strategy to determine the optimal time to inject the control inputs, which may reduce the control energy exponentially. Our conclusions are all verified numerically, and shed light on saving control energy in practical control.
Collapse
Affiliation(s)
- Tao Meng
- Center for Systems and Control, College of Engineering, Peking University, Beijing 100871, China
| | - Gaopeng Duan
- Center for Systems and Control, College of Engineering, Peking University, Beijing 100871, China
| | - Aming Li
- Center for Systems and Control, College of Engineering, Peking University, Beijing 100871, China
- Center for Multi-Agent Research, Institute for Artificial Intelligence, Peking University, Beijing 100871, China
| |
Collapse
|
2
|
Stefanou I, Tzortzopoulos G. Preventing Instabilities and Inducing Controlled, Slow-Slip in Frictionally Unstable Systems. JOURNAL OF GEOPHYSICAL RESEARCH. SOLID EARTH 2022; 127:e2021JB023410. [PMID: 35875412 PMCID: PMC9290888 DOI: 10.1029/2021jb023410] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 10/16/2021] [Revised: 05/19/2022] [Accepted: 05/20/2022] [Indexed: 06/15/2023]
Abstract
We propose a theory for preventing instabilities and inducing controlled, slow-slip in frictionally unstable systems, such as the Generalized-Burridge-Knopoff (GBK) model and seismic fault models. We exploit the dependence of friction on pressure and use it as a backdoor for altering the dynamics of the underlying dynamical system. We use the mathematical Theory of Control and, for the first time, we manage to (a) stabilize and restrict chaos in this kind of systems, (b) guarantee slow frictional dissipation and (c) tune the system toward desirable global asymptotic equilibria of lower energy. Our control approach is robust and does not require exact knowledge of the frictional or elastic behavior of the system. Numerical examples of control are given for a Burridge-Knopoff system and a strike-slip fault model obeying rate-and-state friction. GBK models are known to present Self-Organized Critical (SOC) behavior. Therefore, the presented methodology shows an additional example of SOC Control. Even though further developments are necessary before any practical application, we expect our methodology to inspire earthquake mitigation strategies regarding anthropogenic and/or natural seismicity.
Collapse
Affiliation(s)
- Ioannis Stefanou
- Ecole Centrale de NantesUniversité de NantesCNRS GeM (Institut de Recherche en Génie Civil et Mécanique)NantesFrance
| | - Georgios Tzortzopoulos
- Ecole Centrale de NantesUniversité de NantesCNRS GeM (Institut de Recherche en Génie Civil et Mécanique)NantesFrance
| |
Collapse
|
3
|
Mikaberidze G, D'Souza RM. Sandpile cascades on oscillator networks: The BTW model meets Kuramoto. CHAOS (WOODBURY, N.Y.) 2022; 32:053121. [PMID: 35649989 DOI: 10.1063/5.0095094] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/08/2022] [Accepted: 04/11/2022] [Indexed: 06/15/2023]
Abstract
Cascading failures abound in complex systems and the Bak-Tang-Weisenfeld (BTW) sandpile model provides a theoretical underpinning for their analysis. Yet, it does not account for the possibility of nodes having oscillatory dynamics, such as in power grids and brain networks. Here, we consider a network of Kuramoto oscillators upon which the BTW model is unfolding, enabling us to study how the feedback between the oscillatory and cascading dynamics can lead to new emergent behaviors. We assume that the more out-of-sync a node is with its neighbors, the more vulnerable it is and lower its load-carrying capacity accordingly. Also, when a node topples and sheds load, its oscillatory phase is reset at random. This leads to novel cyclic behavior at an emergent, long timescale. The system spends the bulk of its time in a synchronized state where load builds up with minimal cascades. Yet, eventually, the system reaches a tipping point where a large cascade triggers a "cascade of larger cascades," which can be classified as a dragon king event. The system then undergoes a short transient back to the synchronous, buildup phase. The coupling between capacity and synchronization gives rise to endogenous cascade seeds in addition to the standard exogenous ones, and we show their respective roles. We establish the phenomena from numerical studies and develop the accompanying mean-field theory to locate the tipping point, calculate the load in the system, determine the frequency of the long-time oscillations, and find the distribution of cascade sizes during the buildup phase.
Collapse
Affiliation(s)
- Guram Mikaberidze
- Department of Mathematics, University of California, Davis, Davis, California 95616, USA
| | - Raissa M D'Souza
- Department of Computer Science and Department of Mechanical and Aerospace Engineering, University of California, Davis, Davis, California 95616, USA
| |
Collapse
|
4
|
Turalska M, Swami A. Greedy control of cascading failures in interdependent networks. Sci Rep 2021; 11:3276. [PMID: 33558578 PMCID: PMC7870659 DOI: 10.1038/s41598-021-82843-8] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/13/2020] [Accepted: 01/21/2021] [Indexed: 11/09/2022] Open
Abstract
Complex systems are challenging to control because the system responds to the controller in a nonlinear fashion, often incorporating feedback mechanisms. Interdependence of systems poses additional difficulties, as cross-system connections enable malicious activity to spread between layers, increasing systemic risk. In this paper we explore the conditions for an optimal control of cascading failures in a system of interdependent networks. Specifically, we study the Bak-Tang-Wiesenfeld sandpile model incorporating a control mechanism, which affects the frequency of cascades occurring in individual layers. This modification allows us to explore sandpile-like dynamics near the critical state, with supercritical region corresponding to infrequent large cascades and subcritical zone being characterized by frequent small avalanches. Topological coupling between networks introduces dependence of control settings adopted in respective layers, causing the control strategy of a given layer to be influenced by choices made in other connected networks. We find that the optimal control strategy for a layer operating in a supercritical regime is to be coupled to a layer operating in a subcritical zone, since such condition corresponds to reduced probability of inflicted avalanches. However this condition describes a parasitic relation, in which only one layer benefits. Second optimal configuration is a mutualistic one, where both layers adopt the same control strategy. Our results provide valuable insights into dynamics of cascading failures and and its control in interdependent complex systems.
Collapse
Affiliation(s)
- Malgorzata Turalska
- CCDC Army Research Laboratory, Network Science Division, Adelphi, MD, 20783, USA.
| | - Ananthram Swami
- CCDC Army Research Laboratory, Network Science Division, Adelphi, MD, 20783, USA
| |
Collapse
|
5
|
Kuyyamudi C, Chakrabarti AS, Sinha S. Emergence of frustration signals systemic risk. Phys Rev E 2019; 99:052306. [PMID: 31212413 DOI: 10.1103/physreve.99.052306] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/18/2018] [Indexed: 11/07/2022]
Abstract
We show that the emergence of systemic risk in complex systems can be understood from the evolution of functional networks representing interactions inferred from fluctuation correlations between macroscopic observables. Specifically, we analyze the long-term collective dynamics in the New York Stock Exchange, the largest financial market in the world, for almost a century and show that periods marked by systemic crisis are associated with emergence of frustration. This is indicated by the loss of structural balance in the networks of interaction between stocks. Moreover, the mesoscopic organization of the networks during these periods exhibits prominent core-periphery organization. This suggests an increased degree of coherence in the collective dynamics of the system, which is reinforced by our observation of the transition to delocalization in the dominant eigenmodes when the systemic risk builds up. While frustration has been associated with phase transitions in physical systems such as spin glasses, its role as a signal for systemic risk buildup leading to severe crisis as shown here provides a novel perspective into the dynamical processes leading to catastrophic failures in complex systems.
Collapse
Affiliation(s)
- Chandrashekar Kuyyamudi
- The Institute of Mathematical Sciences, CIT Campus, Taramani, Chennai 600113, India.,Homi Bhabha National Institute, Anushaktinagar, Mumbai 400094, India
| | | | - Sitabhra Sinha
- The Institute of Mathematical Sciences, CIT Campus, Taramani, Chennai 600113, India.,Homi Bhabha National Institute, Anushaktinagar, Mumbai 400094, India
| |
Collapse
|
6
|
Hajihashemi M, Aghababaei Samani K. Fixation time in evolutionary graphs: A mean-field approach. Phys Rev E 2019; 99:042304. [PMID: 31108590 DOI: 10.1103/physreve.99.042304] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/13/2018] [Indexed: 06/09/2023]
Abstract
Using an analytical method we calculate average conditional fixation time of mutants in a general graph-structured population of two types of species. The method is based on Markov chains and uses a mean-field approximation to calculate the corresponding transition matrix. Analytical results are compared with the results of simulation of the Moran process on a number of network structures.
Collapse
Affiliation(s)
- Mahdi Hajihashemi
- Department of Physics, Isfahan University of Technology, Isfahan 84156-83111, Iran
| | - Keivan Aghababaei Samani
- Department of Physics, Isfahan University of Technology, Isfahan 84156-83111, Iran
- International Institute for Applied System Analysis (IIASA), Schlossolatz 1, A-2361 Laxenburg, Austria
| |
Collapse
|
7
|
Turalska M, Burghardt K, Rohden M, Swami A, D'Souza RM. Cascading failures in scale-free interdependent networks. Phys Rev E 2019; 99:032308. [PMID: 30999482 DOI: 10.1103/physreve.99.032308] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/03/2018] [Indexed: 06/09/2023]
Abstract
Large cascades are a common occurrence in many natural and engineered complex systems. In this paper we explore the propagation of cascades across networks using realistic network topologies, such as heterogeneous degree distributions, as well as intra- and interlayer degree correlations. We find that three properties, scale-free degree distribution, internal network assortativity, and cross-network hub-to-hub connections, are all necessary components to significantly reduce the size of large cascades in the Bak-Tang-Wiesenfeld sandpile model. We demonstrate that correlations present in the structure of the multilayer network influence the dynamical cascading process and can prevent failures from spreading across connected layers. These findings highlight the importance of internal and cross-network topology in optimizing robustness of interconnected systems.
Collapse
Affiliation(s)
- Malgorzata Turalska
- Network Science Division, Army Research Laboratory, Adelphi, Maryland 20783, USA
| | - Keith Burghardt
- Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA
| | - Martin Rohden
- Department of Computer Science, University of California, Davis, California 95616, USA
| | - Ananthram Swami
- Computational and Information Science Directorate, Army Research Laboratory, Adelphi, Maryland 20783, USA
| | - Raissa M D'Souza
- Department of Computer Science, University of California, Davis, California 95616, USA; Department of Mechanical and Aerospace Engineering, University of California, Davis, California 95616, USA; and Santa Fe Institute, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
8
|
Lin Y, Burghardt K, Rohden M, Noël PA, D'Souza RM. Self-organization of dragon king failures. Phys Rev E 2018; 98:022127. [PMID: 30253566 DOI: 10.1103/physreve.98.022127] [Citation(s) in RCA: 10] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/13/2017] [Indexed: 11/07/2022]
Abstract
The mechanisms underlying cascading failures are often modeled via the paradigm of self-organized criticality. Here we introduce a simple network model where nodes self-organize to be either weakly or strongly protected against failure in a manner that captures the trade-off between degradation and reinforcement of nodes inherent in many network systems. If strong nodes cannot fail, any failure is contained to a single, isolated cluster of weak nodes and the model produces power-law distributions of failure sizes. We classify the large, rare events that involve the failure of only a single cluster as "black swans." In contrast, if strong nodes fail once a sufficient fraction of their neighbors fail, then failure can cascade across multiple clusters of weak nodes. If over 99.9% of the nodes fail due to this cluster hopping mechanism, we classify this as a "dragon king," which are massive failures caused by mechanisms distinct from smaller failures. The dragon kings observed are self-organized, existing over a wide range of reinforcement rates and system sizes. We find that once an initial cluster of failing weak nodes is above a critical size, the dragon king mechanism kicks in, leading to piggybacking system-wide failures. We demonstrate that the size of the initial failed weak cluster predicts the likelihood of a dragon king event with high accuracy and we develop a simple control strategy that can dramatically reduce dragon kings and other large failures.
Collapse
Affiliation(s)
- Yuansheng Lin
- School of Reliability and Systems Engineering, Beihang University, Beijing 100191, China.,Beijing Jingdong Century Trade Co., Ltd., Beijing 101111, China.,Department of Computer Science, University of California, Davis, California 95616, USA
| | - Keith Burghardt
- Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA
| | - Martin Rohden
- Department of Computer Science, University of California, Davis, California 95616, USA
| | - Pierre-André Noël
- Department of Computer Science, University of California, Davis, California 95616, USA
| | - Raissa M D'Souza
- Department of Computer Science, University of California, Davis, California 95616, USA.,Department of Mechanical and Aerospace Engineering, University of California, Davis, California 95616, USA.,Santa Fe Institute, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
9
|
Dori N, Behar H, Brot H, Louzoun Y. Family-size variability grows with collapse rate in a birth-death-catastrophe model. Phys Rev E 2018; 98:012416. [PMID: 30110815 DOI: 10.1103/physreve.98.012416] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/13/2017] [Indexed: 06/08/2023]
Abstract
Forest-fire and avalanche models support the notion that frequent catastrophes prevent the growth of very large populations and as such, prevent rare large-scale catastrophes. We show that this notion is not universal. A new model class leads to a paradigm shift in the influence of catastrophes on the family-size distribution of subpopulations. We study a simple population dynamics model where individuals, as well as a whole family, may die with a constant probability, accompanied by a logistic population growth model. We compute the characteristics of the family-size distribution in steady state and the phase diagram of the steady-state distribution and show that the family and catastrophe size variances increase with the catastrophe frequency, which is the opposite of common intuition. Frequent catastrophes are balanced by a larger net-growth rate in surviving families, leading to the exponential growth of these families. When the catastrophe rate is further increased, a second phase transition to extinction occurs when the rate of new family creations is lower than their destruction rate by catastrophes.
Collapse
Affiliation(s)
- N Dori
- Gonda Brain Research Center, Bar-Ilan University, Ramat Gan, Israel
| | - H Behar
- Department of Biology, Stanford University, Stanford, California 94305-5020, USA
| | - H Brot
- Boston Children's Hospital, Harvard Medical School, 3 Blackfan Circle, Boston, Massachusetts 02115, USA and Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA
| | - Y Louzoun
- Gonda Brain Research Center, Bar-Ilan University, Ramat Gan, Israel
- Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel
| |
Collapse
|
10
|
Zhou D, Elmokashfi A. Network recovery based on system crash early warning in a cascading failure model. Sci Rep 2018; 8:7443. [PMID: 29748570 PMCID: PMC5945858 DOI: 10.1038/s41598-018-25591-6] [Citation(s) in RCA: 16] [Impact Index Per Article: 2.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/24/2018] [Accepted: 04/19/2018] [Indexed: 11/09/2022] Open
Abstract
This paper investigates the possibility of saving a network that is predicted to have a cascading failure that will eventually lead to a total collapse. We model cascading failures using the recently proposed KQ model. Then predict an impending total collapse by monitoring critical slowing down indicators and subsequently attempt to prevent the total collapse of the network by adding new nodes. To this end, we systematically evaluate five node addition rules, the effect of intervention delay and network degree heterogeneity. Surprisingly, unlike for random homogeneous networks, we find that a delayed intervention is preferred for saving scale free networks. We also find that for homogeneous networks, the best strategy is to wire newly added nodes to existing nodes in a uniformly random manner. For heterogeneous networks, however, a random selection of nodes based on their degree mostly outperforms a uniform random selection. These results provide new insights into restoring networks by adding nodes after observing early warnings of an impending complete breakdown.
Collapse
Affiliation(s)
- Dong Zhou
- Simula Metropolitan CDE, Fornebu, 1364, Norway
| | | |
Collapse
|
11
|
Po HF, Yeung CH, Zeng A, Wong KYM. Evolving power grids with self-organized intermittent strain releases: An analogy with sandpile models and earthquakes. Phys Rev E 2018; 96:052312. [PMID: 29347740 DOI: 10.1103/physreve.96.052312] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/20/2016] [Indexed: 11/07/2022]
Abstract
The stability of powergrid is crucial since its disruption affects systems ranging from street lightings to hospital life-support systems. While short-term dynamics of single-event cascading failures have been extensively studied, less is understood on the long-term evolution and self-organization of powergrids. In this paper, we introduce a simple model of evolving powergrid and establish its connection with the sandpile model and earthquakes, i.e., self-organized systems with intermittent strain releases. Various aspects during its self-organization are examined, including blackout magnitudes, their interevent waiting time, the predictability of large blackouts, as well as the spatiotemporal rescaling of blackout data. We examined the self-organized strain releases on simulated networks as well as the IEEE 118-bus system, and we show that both simulated and empirical blackout waiting times can be rescaled in space and time similarly to those observed between earthquakes. Finally, we suggested proactive maintenance strategies to drive the powergrids away from self-organization to suppress large blackouts.
Collapse
Affiliation(s)
- Ho Fai Po
- Department of Science and Environmental Studies, The Education University of Hong Kong, 10 Lo Ping Road, Taipo, Hong Kong
| | - Chi Ho Yeung
- Department of Science and Environmental Studies, The Education University of Hong Kong, 10 Lo Ping Road, Taipo, Hong Kong
| | - An Zeng
- School of Systems Science, Beijing Normal University, Beijing 100875, People's Republic of China
| | - K Y Michael Wong
- Department of Physics, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong
| |
Collapse
|
12
|
Podobnik B, Horvatic D, Lipic T, Perc M, Buldú JM, Stanley HE. The cost of attack in competing networks. J R Soc Interface 2016; 12:rsif.2015.0770. [PMID: 26490628 DOI: 10.1098/rsif.2015.0770] [Citation(s) in RCA: 37] [Impact Index Per Article: 4.6] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/12/2022] Open
Abstract
Real-world attacks can be interpreted as the result of competitive interactions between networks, ranging from predator-prey networks to networks of countries under economic sanctions. Although the purpose of an attack is to damage a target network, it also curtails the ability of the attacker, which must choose the duration and magnitude of an attack to avoid negative impacts on its own functioning. Nevertheless, despite the large number of studies on interconnected networks, the consequences of initiating an attack have never been studied. Here, we address this issue by introducing a model of network competition where a resilient network is willing to partially weaken its own resilience in order to more severely damage a less resilient competitor. The attacking network can take over the competitor's nodes after their long inactivity. However, owing to a feedback mechanism the takeovers weaken the resilience of the attacking network. We define a conservation law that relates the feedback mechanism to the resilience dynamics for two competing networks. Within this formalism, we determine the cost and optimal duration of an attack, allowing a network to evaluate the risk of initiating hostilities.
Collapse
Affiliation(s)
- B Podobnik
- Center for Polymer Studies and Department of Physics, Boston University, Boston, MA 02215, USA Faculty of Civil Engineering, University of Rijeka, 51000 Rijeka, Croatia Zagreb School of Economics and Management, 10000 Zagreb, Croatia
| | - D Horvatic
- Faculty of Natural Sciences, University of Zagreb, 10000 Zagreb, Croatia
| | - T Lipic
- Center for Polymer Studies and Department of Physics, Boston University, Boston, MA 02215, USA Rudjer Boskovic Institute, Centre for Informatics and Computing, 10000 Zagreb, Croatia
| | - M Perc
- Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, 2000 Maribor, Slovenia Department of Physics, Faculty of Sciences, King Abdulaziz University, Jeddah, Saudi Arabia
| | - J M Buldú
- Center for Biomedical Technology (UPM), 28223 Pozuelo de Alarcón, Madrid, Spain Complex Systems Group, Rey Juan Carlos University, 28933 Móstoles, Madrid, Spain
| | - H E Stanley
- Center for Polymer Studies and Department of Physics, Boston University, Boston, MA 02215, USA
| |
Collapse
|
13
|
Motter AE. Networkcontrology. CHAOS (WOODBURY, N.Y.) 2015; 25:097621. [PMID: 26428574 PMCID: PMC4592432 DOI: 10.1063/1.4931570] [Citation(s) in RCA: 27] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/07/2015] [Accepted: 09/10/2015] [Indexed: 05/20/2023]
Abstract
An increasing number of complex systems are now modeled as networks of coupled dynamical entities. Nonlinearity and high-dimensionality are hallmarks of the dynamics of such networks but have generally been regarded as obstacles to control. Here, I discuss recent advances on mathematical and computational approaches to control high-dimensional nonlinear network dynamics under general constraints on the admissible interventions. I also discuss the potential of network control to address pressing scientific problems in various disciplines.
Collapse
Affiliation(s)
- Adilson E Motter
- Department of Physics and Astronomy, Northwestern University, Evanston, Illinois 60208, USA and Northwestern Institute on Complex Systems (NICO), Northwestern University, Evanston, Illinois 60208, USA
| |
Collapse
|
14
|
Stäger DV, Araújo NAM, Herrmann HJ. Usage leading to an abrupt collapse of connectivity. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:042148. [PMID: 25375479 DOI: 10.1103/physreve.90.042148] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/10/2014] [Indexed: 06/04/2023]
Abstract
Network infrastructures are essential for the distribution of resources such as electricity and water. Typical strategies to assess their resilience focus on the impact of a sequence of random or targeted failures of network nodes or links. Here we consider a more realistic scenario, where elements fail based on their usage. We propose a dynamic model of transport based on the Bak-Tang-Wiesenfeld sandpile model where links fail after they have transported more than an amount μ (threshold) of the resource and we investigate it on the square lattice. As we deal with a new model, we provide insight on its fundamental behavior and dependence on parameters. We observe that, for low values of the threshold due to a positive feedback of link failure, an avalanche develops that leads to an abrupt collapse of the lattice. By contrast, for high thresholds the lattice breaks down in an uncorrelated fashion. We determine the critical threshold μ* separating these two regimes and show how it depends on the toppling threshold of the nodes and the mass increment added stepwise to the system. We find that the time of major disconnection is well described with a linear dependence on μ. Furthermore, we propose a lower bound for μ* by measuring the strength of the dynamics leading to abrupt collapses.
Collapse
Affiliation(s)
- D V Stäger
- Computational Physics for Engineering Materials, IfB, ETH Zurich, Wolfgang-Pauli-Strasse 27, CH-8093 Zurich, Switzerland
| | - N A M Araújo
- Departamento de Física, Faculdade de Ciências, Universidade de Lisboa, P-1749-016 Lisboa, Portugal and Centro de Física Teórica e Computacional, Universidade de Lisboa, P-1749-016 Lisboa, Portugal
| | - H J Herrmann
- Computational Physics for Engineering Materials, IfB, ETH Zurich, Wolfgang-Pauli-Strasse 27, CH-8093 Zurich, Switzerland and Departamento de Física, Universidade Federal do Ceará, 60451-970 Fortaleza, Ceará, Brazil
| |
Collapse
|
15
|
Abstract
Power grids, road maps, and river streams are examples of infrastructural networks which are highly vulnerable to external perturbations. An abrupt local change of load (voltage, traffic density, or water level) might propagate in a cascading way and affect a significant fraction of the network. Almost discontinuous perturbations can be modeled by shock waves which can eventually interfere constructively and endanger the normal functionality of the infrastructure. We study their dynamics by solving the Burgers equation under random perturbations on several real and artificial directed graphs. Even for graphs with a narrow distribution of node properties (e.g., degree or betweenness), a steady state is reached exhibiting a heterogeneous load distribution, having a difference of one order of magnitude between the highest and average loads. Unexpectedly we find for the European power grid and for finite Watts-Strogatz networks a broad pronounced bimodal distribution for the loads. To identify the most vulnerable nodes, we introduce the concept of node-basin size, a purely topological property which we show to be strongly correlated to the average load of a node.
Collapse
|
16
|
Gleeson JP, Ward JA, O'Sullivan KP, Lee WT. Competition-induced criticality in a model of meme popularity. PHYSICAL REVIEW LETTERS 2014; 112:048701. [PMID: 24580496 DOI: 10.1103/physrevlett.112.048701] [Citation(s) in RCA: 35] [Impact Index Per Article: 3.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/31/2013] [Indexed: 05/27/2023]
Abstract
Heavy-tailed distributions of meme popularity occur naturally in a model of meme diffusion on social networks. Competition between multiple memes for the limited resource of user attention is identified as the mechanism that poises the system at criticality. The popularity growth of each meme is described by a critical branching process, and asymptotic analysis predicts power-law distributions of popularity with very heavy tails (exponent α<2, unlike preferential-attachment models), similar to those seen in empirical data.
Collapse
Affiliation(s)
- James P Gleeson
- MACSI, Department of Mathematics and Statistics, University of Limerick, Limerick, Ireland
| | - Jonathan A Ward
- Centre for the Mathematics of Human Behaviour, Department of Mathematics and Statistics, University of Reading, Whiteknights RG6 6AH, United Kingdom
| | - Kevin P O'Sullivan
- MACSI, Department of Mathematics and Statistics, University of Limerick, Limerick, Ireland
| | - William T Lee
- MACSI, Department of Mathematics and Statistics, University of Limerick, Limerick, Ireland
| |
Collapse
|
17
|
Noël PA, Brummitt CD, D'Souza RM. Bottom-up model of self-organized criticality on networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:012807. [PMID: 24580281 DOI: 10.1103/physreve.89.012807] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/20/2013] [Indexed: 06/03/2023]
Abstract
The Bak-Tang-Wiesenfeld (BTW) sandpile process is an archetypal, stylized model of complex systems with a critical point as an attractor of their dynamics. This phenomenon, called self-organized criticality, appears to occur ubiquitously in both nature and technology. Initially introduced on the two-dimensional lattice, the BTW process has been studied on network structures with great analytical successes in the estimation of macroscopic quantities, such as the exponents of asymptotically power-law distributions. In this article, we take a microscopic perspective and study the inner workings of the process through both numerical and rigorous analysis. Our simulations reveal fundamental flaws in the assumptions of past phenomenological models, the same models that allowed accurate macroscopic predictions; we mathematically justify why universality may explain these past successes. Next, starting from scratch, we obtain microscopic understanding that enables mechanistic models; such models can, for example, distinguish a cascade's area from its size. In the special case of a 3-regular network, we use self-consistency arguments to obtain a zero-parameter mechanistic (bottom-up) approximation that reproduces nontrivial correlations observed in simulations and that allows the study of the BTW process on networks in regimes otherwise prohibitively costly to investigate. We then generalize some of these results to configuration model networks and explain how one could continue the generalization. The numerous tools and methods presented herein are known to enable studying the effects of controlling the BTW process and other self-organizing systems. More broadly, our use of multitype branching processes to capture information bouncing back and forth in a network could inspire analogous models of systems in which consequences spread in a bidirectional fashion.
Collapse
Affiliation(s)
- Pierre-André Noël
- Complexity Sciences Center, University of California, Davis, California 95616, USA and Department of Computer Science, University of California, Davis, California 95616, USA
| | - Charles D Brummitt
- Complexity Sciences Center, University of California, Davis, California 95616, USA and Department of Mathematics, University of California, Davis, California 95616, USA
| | - Raissa M D'Souza
- Complexity Sciences Center, University of California, Davis, California 95616, USA and Department of Computer Science, University of California, Davis, California 95616, USA and Department of Mechanical and Aerospace Engineering, University of California, Davis, California 95616, USA and Santa Fe Institute, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
18
|
|
19
|
|