1
|
Di Gaetano L, Carugno G, Battiston F, Coghi F. Dynamical Fluctuations of Random Walks in Higher-Order Networks. PHYSICAL REVIEW LETTERS 2024; 133:107401. [PMID: 39303236 DOI: 10.1103/physrevlett.133.107401] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/07/2023] [Revised: 06/04/2024] [Accepted: 07/26/2024] [Indexed: 09/22/2024]
Abstract
Although higher-order interactions are known to affect the typical state of dynamical processes giving rise to new collective behavior, how they drive the emergence of rare events and fluctuations is still an open problem. We investigate how fluctuations of a dynamical quantity of a random walk exploring a higher-order network arise over time. In the quenched case, where the hypergraph structure is fixed, through large deviation theory we show that the appearance of rare events is hampered in nodes with many higher-order interactions, and promoted elsewhere. Dynamical fluctuations are further boosted in an annealed scenario, where both the diffusion process and higher-order interactions evolve in time. Here, extreme fluctuations generated by optimal higher-order configurations can be predicted in the limit of a saddle-point approximation. Our study lays the groundwork for a wide and general theory of fluctuations and rare events in higher-order networks.
Collapse
Affiliation(s)
| | | | | | - Francesco Coghi
- Nordita, KTH Royal Institute of Technology and Stockholm University, Hannes Alfvéns väg 12, SEa-106 91 Stockholm, Sweden
| |
Collapse
|
2
|
Gandhi G, Santhanam MS. Biased random walkers and extreme events on the edges of complex networks. Phys Rev E 2022; 105:014315. [PMID: 35193284 DOI: 10.1103/physreve.105.014315] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/01/2021] [Accepted: 01/18/2022] [Indexed: 06/14/2023]
Abstract
Extreme events have low occurrence probabilities and display pronounced deviation from their average behavior, such as earthquakes or power blackouts. Such extreme events occurring on the nodes of a complex network have been extensively studied earlier through the modeling framework of unbiased random walks. They reveal that the occurrence probability for extreme events on nodes of a network has a strong dependence on the nodal properties. Apart from these, a recent work has shown the independence of extreme events on edges from those occurring on nodes. Hence, in this work, we propose a more general formalism to study the properties of extreme events arising from biased random walkers on the edges of a network. This formalism is applied to biases based on a variety network centrality measures including PageRank. It is shown that with biased random walkers as the dynamics on the network, extreme event probabilities depend on the local properties of the edges. The probabilities are highly variable for some edges of the network, while they are approximately a constant for some other edges on the same network. This feature is robust with respect to different biases applied to the random walk algorithm. Further, using the results from this formalism, it is shown that a network is far more robust to extreme events occurring on edges when compared to those occurring on the nodes.
Collapse
Affiliation(s)
- Govind Gandhi
- Indian Institute of Science Education and Research, Dr. Homi Bhabha Road, Pune, India 411008
| | - M S Santhanam
- Indian Institute of Science Education and Research, Dr. Homi Bhabha Road, Pune, India 411008
| |
Collapse
|
3
|
Peng J, Xu G, Shao R, Chen L, Stanley HE. Analysis of fluctuations in the first return times of random walks on regular branched networks. J Chem Phys 2018; 149:024903. [PMID: 30007392 DOI: 10.1063/1.5028123] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/15/2022] Open
Abstract
The first return time (FRT) is the time it takes a random walker to first return to its original site, and the global first passage time (GFPT) is the first passage time for a random walker to move from a randomly selected site to a given site. We find that in finite networks, the variance of FRT, Var(FRT), can be expressed as Var(FRT) = 2⟨FRT⟩⟨GFPT⟩ - ⟨FRT⟩2 - ⟨FRT⟩, where ⟨·⟩ is the mean of the random variable. Therefore a method of calculating the variance of FRT on general finite networks is presented. We then calculate Var(FRT) and analyze the fluctuation of FRT on regular branched networks (i.e., Cayley tree) by using Var(FRT) and its variant as the metric. We find that the results differ from those in such other networks as Sierpinski gaskets, Vicsek fractals, T-graphs, pseudofractal scale-free webs, (u, v) flowers, and fractal and non-fractal scale-free trees.
Collapse
Affiliation(s)
- Junhao Peng
- School of Math and Information Science, Guangzhou University, Guangzhou 510006, China
| | - Guoai Xu
- School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing 100876, China
| | - Renxiang Shao
- School of Math and Information Science, Guangzhou University, Guangzhou 510006, China
| | - Lin Chen
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA
| | - H Eugene Stanley
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA
| |
Collapse
|
4
|
Chen YZ, Lai YC. Sparse dynamical Boltzmann machine for reconstructing complex networks with binary dynamics. Phys Rev E 2018; 97:032317. [PMID: 29776147 DOI: 10.1103/physreve.97.032317] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/07/2017] [Indexed: 06/08/2023]
Abstract
Revealing the structure and dynamics of complex networked systems from observed data is a problem of current interest. Is it possible to develop a completely data-driven framework to decipher the network structure and different types of dynamical processes on complex networks? We develop a model named sparse dynamical Boltzmann machine (SDBM) as a structural estimator for complex networks that host binary dynamical processes. The SDBM attains its topology according to that of the original system and is capable of simulating the original binary dynamical process. We develop a fully automated method based on compressive sensing and a clustering algorithm to construct the SDBM. We demonstrate, for a variety of representative dynamical processes on model and real world complex networks, that the equivalent SDBM can recover the network structure of the original system and simulates its dynamical behavior with high precision.
Collapse
Affiliation(s)
- Yu-Zhong Chen
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
| | - Ying-Cheng Lai
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
- Department of Physics, Arizona State University, Tempe, Arizona 85287, USA
| |
Collapse
|
5
|
Wang LZ, Su RQ, Huang ZG, Wang X, Wang WX, Grebogi C, Lai YC. A geometrical approach to control and controllability of nonlinear dynamical networks. Nat Commun 2016; 7:11323. [PMID: 27076273 PMCID: PMC4834635 DOI: 10.1038/ncomms11323] [Citation(s) in RCA: 77] [Impact Index Per Article: 9.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/16/2015] [Accepted: 03/08/2016] [Indexed: 12/22/2022] Open
Abstract
In spite of the recent interest and advances in linear controllability of complex networks, controlling nonlinear network dynamics remains an outstanding problem. Here we develop an experimentally feasible control framework for nonlinear dynamical networks that exhibit multistability. The control objective is to apply parameter perturbation to drive the system from one attractor to another, assuming that the former is undesired and the latter is desired. To make our framework practically meaningful, we consider restricted parameter perturbation by imposing two constraints: it must be experimentally realizable and applied only temporarily. We introduce the concept of attractor network, which allows us to formulate a quantifiable controllability framework for nonlinear dynamical networks: a network is more controllable if the attractor network is more strongly connected. We test our control framework using examples from various models of experimental gene regulatory networks and demonstrate the beneficial role of noise in facilitating control.
Collapse
Affiliation(s)
- Le-Zhi Wang
- School of Electrical, Computer and Energy Engineering, Arizona State University, 650 E. Tyler Mall, Tempe, Arizona 85287-5706, USA
| | - Ri-Qi Su
- School of Electrical, Computer and Energy Engineering, Arizona State University, 650 E. Tyler Mall, Tempe, Arizona 85287-5706, USA
| | - Zi-Gang Huang
- School of Electrical, Computer and Energy Engineering, Arizona State University, 650 E. Tyler Mall, Tempe, Arizona 85287-5706, USA.,Institute of Computational Physics and Complex Systems, Lanzhou University, 222 S. Tianshui Road, Lanzhou, Gansu 730000, China
| | - Xiao Wang
- School of Biological and Health Systems Engineering, Arizona State University, 621 E. Tyler Mall, Tempe, Arizona 85287-9709, USA
| | - Wen-Xu Wang
- School of Electrical, Computer and Energy Engineering, Arizona State University, 650 E. Tyler Mall, Tempe, Arizona 85287-5706, USA.,School of Systems Science, Beijing Normal University, 19 Xinjiekou Outer Street, Beijing, 100875, China
| | - Celso Grebogi
- Institute for Complex Systems and Mathematical Biology, King's College, Meston Walk, University of Aberdeen, Aberdeen AB24 3UE, UK
| | - Ying-Cheng Lai
- School of Electrical, Computer and Energy Engineering, Arizona State University, 650 E. Tyler Mall, Tempe, Arizona 85287-5706, USA.,Institute for Complex Systems and Mathematical Biology, King's College, University of Aberdeen, Meston Walk, Aberdeen AB24 3UE, UK.,Department of Physics, Arizona State University, 550 E Tyler Drive, Tempe, Arizona 85287-1504, USA
| |
Collapse
|
6
|
Hunt D, Molnár F, Szymanski BK, Korniss G. Extreme fluctuations in stochastic network coordination with time delays. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 92:062816. [PMID: 26764753 DOI: 10.1103/physreve.92.062816] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/08/2015] [Indexed: 06/05/2023]
Abstract
We study the effects of uniform time delays on the extreme fluctuations in stochastic synchronization and coordination problems with linear couplings in complex networks. We obtain the average size of the fluctuations at the nodes from the behavior of the underlying modes of the network. We then obtain the scaling behavior of the extreme fluctuations with system size, as well as the distribution of the extremes on complex networks, and compare them to those on regular one-dimensional lattices. For large complex networks, when the delay is not too close to the critical one, fluctuations at the nodes effectively decouple, and the limit distributions converge to the Fisher-Tippett-Gumbel density. In contrast, fluctuations in low-dimensional spatial graphs are strongly correlated, and the limit distribution of the extremes is the Airy density. Finally, we also explore the effects of nonlinear couplings on the stability and on the extremes of the synchronization landscapes.
Collapse
Affiliation(s)
- D Hunt
- Department of Physics, Applied Physics, and Astronomy
- Network Science and Technology Center
| | - F Molnár
- Department of Physics, Applied Physics, and Astronomy
- Network Science and Technology Center
| | - B K Szymanski
- Network Science and Technology Center
- Department of Computer Science Rensselaer Polytechnic Institute, 110 8th Street, Troy, New York 12180-3590, USA
| | - G Korniss
- Department of Physics, Applied Physics, and Astronomy
- Network Science and Technology Center
| |
Collapse
|
7
|
Extreme events in multilayer, interdependent complex networks and control. Sci Rep 2015; 5:17277. [PMID: 26612009 PMCID: PMC4661526 DOI: 10.1038/srep17277] [Citation(s) in RCA: 25] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/08/2015] [Accepted: 10/28/2015] [Indexed: 11/30/2022] Open
Abstract
We investigate the emergence of extreme events in interdependent networks. We introduce an inter-layer traffic resource competing mechanism to account for the limited capacity associated with distinct network layers. A striking finding is that, when the number of network layers and/or the overlap among the layers are increased, extreme events can emerge in a cascading manner on a global scale. Asymptotically, there are two stable absorption states: a state free of extreme events and a state of full of extreme events, and the transition between them is abrupt. Our results indicate that internal interactions in the multiplex system can yield qualitatively distinct phenomena associated with extreme events that do not occur for independent network layers. An implication is that, e.g., public resource competitions among different service providers can lead to a higher resource requirement than naively expected. We derive an analytical theory to understand the emergence of global-scale extreme events based on the concept of effective betweenness. We also articulate a cost-effective control scheme through increasing the capacity of very few hubs to suppress the cascading process of extreme events so as to protect the entire multi-layer infrastructure against global-scale breakdown.
Collapse
|
8
|
Hamaneh MB, Haber J, Yu YK. Analytical solution and scaling of fluctuations in complex networks traversed by damped, interacting random walkers. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 92:052803. [PMID: 26651740 PMCID: PMC5873644 DOI: 10.1103/physreve.92.052803] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/13/2015] [Indexed: 06/05/2023]
Abstract
A general model for random walks (RWs) on networks is proposed. It incorporates damping and time-dependent links, and it includes standard (undamped, noninteracting) RWs (SRWs), coalescing RWs, and coalescing-branching RWs as special cases. The exact, time-dependent solutions for the average numbers of visits (w) to nodes and their fluctuations (σ2) are given, and the long-term σ-w relation is studied. Although σ ∝ w(1/2) for SRWs, this power law can be fragile when coalescing-branching interaction is present. Damping, however, often strengthens it but with an exponent generally different from 1/2.
Collapse
|
9
|
Gao J, Zhou T, Hu Y. Bootstrap percolation on spatial networks. Sci Rep 2015; 5:14662. [PMID: 26423347 PMCID: PMC4589777 DOI: 10.1038/srep14662] [Citation(s) in RCA: 27] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/16/2015] [Accepted: 09/03/2015] [Indexed: 11/11/2022] Open
Abstract
Bootstrap percolation is a general representation of some networked activation process, which has found applications in explaining many important social phenomena, such as the propagation of information. Inspired by some recent findings on spatial structure of online social networks, here we study bootstrap percolation on undirected spatial networks, with the probability density function of long-range links' lengths being a power law with tunable exponent. Setting the size of the giant active component as the order parameter, we find a parameter-dependent critical value for the power-law exponent, above which there is a double phase transition, mixed of a second-order phase transition and a hybrid phase transition with two varying critical points, otherwise there is only a second-order phase transition. We further find a parameter-independent critical value around -1, about which the two critical points for the double phase transition are almost constant. To our surprise, this critical value -1 is just equal or very close to the values of many real online social networks, including LiveJournal, HP Labs email network, Belgian mobile phone network, etc. This work helps us in better understanding the self-organization of spatial structure of online social networks, in terms of the effective function for information spreading.
Collapse
Affiliation(s)
- Jian Gao
- CompleX Lab, Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 611731, China
| | - Tao Zhou
- CompleX Lab, Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 611731, China
- Big Data Research Center, University of Electronic Science and Technology of China, Chengdu 611731, China
| | - Yanqing Hu
- School of Mathematics, Southwest Jiaotong University, Chengdu 610031, China
- School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, China
| |
Collapse
|
10
|
Chen YZ, Huang ZG, Xu S, Lai YC. Spatiotemporal patterns and predictability of cyberattacks. PLoS One 2015; 10:e0124472. [PMID: 25992837 PMCID: PMC4439157 DOI: 10.1371/journal.pone.0124472] [Citation(s) in RCA: 27] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/23/2014] [Accepted: 03/02/2015] [Indexed: 11/18/2022] Open
Abstract
A relatively unexplored issue in cybersecurity science and engineering is whether there exist intrinsic patterns of cyberattacks. Conventional wisdom favors absence of such patterns due to the overwhelming complexity of the modern cyberspace. Surprisingly, through a detailed analysis of an extensive data set that records the time-dependent frequencies of attacks over a relatively wide range of consecutive IP addresses, we successfully uncover intrinsic spatiotemporal patterns underlying cyberattacks, where the term “spatio” refers to the IP address space. In particular, we focus on analyzing macroscopic properties of the attack traffic flows and identify two main patterns with distinct spatiotemporal characteristics: deterministic and stochastic. Strikingly, there are very few sets of major attackers committing almost all the attacks, since their attack “fingerprints” and target selection scheme can be unequivocally identified according to the very limited number of unique spatiotemporal characteristics, each of which only exists on a consecutive IP region and differs significantly from the others. We utilize a number of quantitative measures, including the flux-fluctuation law, the Markov state transition probability matrix, and predictability measures, to characterize the attack patterns in a comprehensive manner. A general finding is that the attack patterns possess high degrees of predictability, potentially paving the way to anticipating and, consequently, mitigating or even preventing large-scale cyberattacks using macroscopic approaches.
Collapse
Affiliation(s)
- Yu-Zhong Chen
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
| | - Zi-Gang Huang
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
- Institute of Computational Physics and Complex Systems, Lanzhou University, Lanzhou Gansu 730000, China
- * E-mail: (ZGH); (YCL)
| | - Shouhuai Xu
- Department of Computer Science, University of Texas at San Antonio, San Antonio, TX 78249, USA
| | - Ying-Cheng Lai
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
- Department of Physics, Arizona State University, Tempe, Arizona 85287, USA
- * E-mail: (ZGH); (YCL)
| |
Collapse
|
11
|
Huang ZG, Dong JQ, Huang L, Lai YC. Universal flux-fluctuation law in small systems. Sci Rep 2014; 4:6787. [PMID: 25345973 PMCID: PMC4209461 DOI: 10.1038/srep06787] [Citation(s) in RCA: 16] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/01/2014] [Accepted: 10/03/2014] [Indexed: 11/09/2022] Open
Abstract
The relation between flux and fluctuation is fundamental to complex physical systems that support and transport flows. A recently obtained law predicts monotonous enhancement of fluctuation as the average flux is increased, which in principle is valid but only for large systems. For realistic complex systems of small sizes, this law breaks down when both the average flux and fluctuation become large. Here we demonstrate the failure of this law in small systems using real data and model complex networked systems, derive analytically a modified flux-fluctuation law, and validate it through computations of a large number of complex networked systems. Our law is more general in that its predictions agree with numerics and it reduces naturally to the previous law in the limit of large system size, leading to new insights into the flow dynamics in small-size complex systems with significant implications for the statistical and scaling behaviors of small systems, a topic of great recent interest.
Collapse
Affiliation(s)
- Zi-Gang Huang
- 1] Institute of Computational Physics and Complex Systems and Key Laboratory for Magnetism and Magnetic Materials of MOE, Lanzhou University, Lanzhou 730000, China [2] School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ 85287, USA
| | - Jia-Qi Dong
- Institute of Computational Physics and Complex Systems and Key Laboratory for Magnetism and Magnetic Materials of MOE, Lanzhou University, Lanzhou 730000, China
| | - Liang Huang
- 1] Institute of Computational Physics and Complex Systems and Key Laboratory for Magnetism and Magnetic Materials of MOE, Lanzhou University, Lanzhou 730000, China [2] School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ 85287, USA
| | - Ying-Cheng Lai
- 1] School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ 85287, USA [2] Department of Physics, Arizona State University, Tempe, Arizona 85287, USA
| |
Collapse
|