1
|
Ziganurova L, Shchur LN. Synchronization of conservative parallel discrete event simulations on a small-world network. Phys Rev E 2018; 98:022218. [PMID: 30253476 DOI: 10.1103/physreve.98.022218] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/12/2018] [Indexed: 11/07/2022]
Abstract
We examine the question of the influence of sparse long-range communications on the synchronization in parallel discrete event simulations. We build a model of the evolution of local virtual times in a conservative algorithm including several choices of local links. All network realizations belong to the small-world network class. We find that synchronization depends on the average shortest path of the network. The time profile dynamics are similar to the surface profile growth, which helps to analyze synchronization effects using a statistical physics approach. Without long-range links of the nodes, the model belongs to the universality class of the Kardar-Parisi-Zhang equation for surface growth. We find that the critical exponents depend logarithmically on the fraction of long-range links. We present the results of simulations and discuss our observations.
Collapse
Affiliation(s)
- Liliia Ziganurova
- Science Center in Chernogolovka, 142432 Chernogolovka, Russia and National Research University Higher School of Economics, 101000 Moscow, Russia
| | - Lev N Shchur
- Science Center in Chernogolovka, 142432 Chernogolovka, Russia and National Research University Higher School of Economics, 101000 Moscow, Russia
| |
Collapse
|
2
|
Melchert O, Katzgraber HG, Novotny MA. Site- and bond-percolation thresholds in K_{n,n}-based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies. Phys Rev E 2016; 93:042128. [PMID: 27176275 DOI: 10.1103/physreve.93.042128] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/22/2015] [Indexed: 06/05/2023]
Abstract
We estimate the critical thresholds of bond and site percolation on nonplanar, effectively two-dimensional graphs with chimeralike topology. The building blocks of these graphs are complete and symmetric bipartite subgraphs of size 2n, referred to as K_{n,n} graphs. For the numerical simulations we use an efficient union-find-based algorithm and employ a finite-size scaling analysis to obtain the critical properties for both bond and site percolation. We report the respective percolation thresholds for different sizes of the bipartite subgraph and verify that the associated universality class is that of standard two-dimensional percolation. For the canonical chimera graph used in the D-Wave Systems Inc. quantum annealer (n=4), we discuss device failure in terms of network vulnerability, i.e., we determine the critical fraction of qubits and couplers that can be absent due to random failures prior to losing large-scale connectivity throughout the device.
Collapse
Affiliation(s)
- O Melchert
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Helmut G Katzgraber
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
- Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
- Applied Mathematics Research Centre, Coventry University, Coventry, CV1 5FB, England
| | - M A Novotny
- Department of Physics and Astronomy, Mississippi State University, Mississippi State, Mississippi 39762-5167, USA
- HPC2 Center for Computational Sciences, Mississippi State University, Mississippi State, Mississippi 39762-5167, USA
| |
Collapse
|
3
|
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
|
4
|
Hunt D, Szymanski BK, Korniss G. Network coordination and synchronization in a noisy environment with time delays. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 86:056114. [PMID: 23214850 DOI: 10.1103/physreve.86.056114] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/18/2012] [Indexed: 06/01/2023]
Abstract
We study the effects of nonzero time delays in stochastic synchronization problems with linear couplings in complex networks. We consider two types of time delays: transmission delays between interacting nodes and local delays at each node (due to processing, cognitive, or execution delays). By investigating the underlying fluctuations for several delay schemes, we obtain the synchronizability threshold (phase boundary) and the scaling behavior of the width of the synchronization landscape, in some cases for arbitrary networks and in others for specific weighted networks. Numerical computations allow the behavior of these networks to be explored when direct analytical results are not available. We comment on the implications of these findings for simple locally or globally weighted network couplings and possible trade-offs present in such systems.
Collapse
Affiliation(s)
- D Hunt
- Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, New York 12180-3590, USA
| | | | | |
Collapse
|
5
|
Su X, Jin X, Min Y, Mo L, Yang J. A curve shaped description of large networks, with an application to the evaluation of network models. PLoS One 2011; 6:e19784. [PMID: 21611192 PMCID: PMC3096638 DOI: 10.1371/journal.pone.0019784] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/13/2010] [Accepted: 04/14/2011] [Indexed: 11/18/2022] Open
Abstract
Background Understanding the structure of complex networks is a continuing challenge, which calls for novel approaches and models to capture their structure and reveal the mechanisms that shape the networks. Although various topological measures, such as degree distributions or clustering coefficients, have been proposed to characterize network structure from many different angles, a comprehensive and intuitive representation of large networks that allows quantitative analysis is still difficult to achieve. Methodology/Principal Findings Here we propose a mesoscopic description of large networks which associates networks of different structures with a set of particular curves, using breadth-first search. After deriving the expressions of the curves of the random graphs and a small-world-like network, we found that the curves possess a number of network properties together, including the size of the giant component and the local clustering. Besides, the curve can also be used to evaluate the fit of network models to real-world networks. We describe a simple evaluation method based on the curve and apply it to the Drosophila melanogaster protein interaction network. The evaluation method effectively identifies which model better reproduces the topology of the real network among the given models and help infer the underlying growth mechanisms of the Drosophila network. Conclusions/Significance This curve-shaped description of large networks offers a wealth of possibilities to develop new approaches and applications including network characterization, comparison, classification, modeling and model evaluation, differing from using a large bag of topological measures.
Collapse
Affiliation(s)
- Xianchuang Su
- Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou, Zhejiang, China
- Ningbo Institute of Technology, Zhejiang University, Ningbo, Zhejiang, China
| | - Xiaogang Jin
- Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou, Zhejiang, China
- Ningbo Institute of Technology, Zhejiang University, Ningbo, Zhejiang, China
- * E-mail:
| | - Yong Min
- Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou, Zhejiang, China
- Ningbo Institute of Technology, Zhejiang University, Ningbo, Zhejiang, China
| | - Linjian Mo
- Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou, Zhejiang, China
| | - Jiangang Yang
- Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou, Zhejiang, China
- Ningbo Institute of Technology, Zhejiang University, Ningbo, Zhejiang, China
| |
Collapse
|
6
|
Network synchronization landscape reveals compensatory structures, quantization, and the positive effect of negative interactions. Proc Natl Acad Sci U S A 2010; 107:10342-7. [PMID: 20489183 DOI: 10.1073/pnas.0912444107] [Citation(s) in RCA: 69] [Impact Index Per Article: 4.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/18/2022] Open
Abstract
Synchronization, in which individual dynamical units keep in pace with each other in a decentralized fashion, depends both on the dynamical units and on the properties of the interaction network. Yet, the role played by the network has resisted comprehensive characterization within the prevailing paradigm that interactions facilitating pairwise synchronization also facilitate collective synchronization. Here we challenge this paradigm and show that networks with best complete synchronization, least coupling cost, and maximum dynamical robustness, have arbitrary complexity but quantized total interaction strength, which constrains the allowed number of connections. It stems from this characterization that negative interactions as well as link removals can be used to systematically improve and optimize synchronization properties in both directed and undirected networks. These results extend the recently discovered compensatory perturbations in metabolic networks to the realm of oscillator networks and demonstrate why "less can be more" in network synchronization.
Collapse
|
7
|
Almendral JA, Sendiña-Nadal I, Yu D, Leyva I, Boccaletti S. Regulating synchronous states of complex networks by pinning interaction with an external node. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2009; 80:066111. [PMID: 20365235 DOI: 10.1103/physreve.80.066111] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/11/2009] [Revised: 11/12/2009] [Indexed: 05/29/2023]
Abstract
To shed light on how biological and technological systems can establish or maintain a synchronous functioning, we address the problem of how to engineer an external pinning action on a network of dynamical units. In particular, we study the regulation of a network toward a synchronized behavior by means of a bidirectional interaction with an external node that leaves unchanged its inner parameters and architecture. We demonstrate that there are two classes of networks susceptible of being regulated into a synchronous motion and provide a simple method, for each one of them, to properly design a pinning sequence to achieve regulation. We also discuss how the obtained sequence can be compared with a topological ranking of the network nodes.
Collapse
Affiliation(s)
- J A Almendral
- Complex Systems Group, ETSIT, Universidad Rey Juan Carlos, Tulipán s/n, Móstoles, Madrid, Spain
| | | | | | | | | |
Collapse
|
8
|
Guclu H, Korniss G, Toroczkai Z. Extreme fluctuations in noisy task-completion landscapes on scale-free networks. CHAOS (WOODBURY, N.Y.) 2007; 17:026104. [PMID: 17614691 DOI: 10.1063/1.2735446] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/16/2023]
Abstract
We study the statistics and scaling of extreme fluctuations in noisy task-completion landscapes, such as those emerging in synchronized distributed-computing networks, or generic causally constrained queuing networks, with scale-free topology. In these networks the average size of the fluctuations becomes finite (synchronized state) and the extreme fluctuations typically diverge only logarithmically in the large system-size limit ensuring synchronization in a practical sense. Provided that local fluctuations in the network are short tailed, the statistics of the extremes are governed by the Gumbel distribution. We present large-scale simulation results using the exact algorithmic rules, supported by mean-field arguments based on a coarse-grained description.
Collapse
Affiliation(s)
- H Guclu
- Center for Nonlinear Studies, Theoretical Division, Los Alamos National Laboratory, MS-B258, Los Alamos, New Mexico 87545, USA
| | | | | |
Collapse
|
9
|
Teuscher C. Nature-inspired interconnects for self-assembled large-scale network-on-chip designs. CHAOS (WOODBURY, N.Y.) 2007; 17:026106. [PMID: 17614693 DOI: 10.1063/1.2740566] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/16/2023]
Abstract
Future nanoscale electronics built up from an Avogadro number of components need efficient, highly scalable, and robust means of communication in order to be competitive with traditional silicon approaches. In recent years, the networks-on-chip (NoC) paradigm emerged as a promising solution to interconnect challenges in silicon-based electronics. Current NoC architectures are either highly regular or fully customized, both of which represent implausible assumptions for emerging bottom-up self-assembled molecular electronics that are generally assumed to have a high degree of irregularity and imperfection. Here, we pragmatically and experimentally investigate important design tradeoffs and properties of an irregular, abstract, yet physically plausible three-dimensional (3D) small-world interconnect fabric that is inspired by modern network-on-chip paradigms. We vary the framework's key parameters, such as the connectivity, number of switch nodes, and distribution of long- versus short-range connections, and measure the network's relevant communication characteristics. We further explore the robustness against link failures and the ability and efficiency to solve a simple toy problem, the synchronization task. The results confirm that (1) computation in irregular assemblies is a promising and disruptive computing paradigm for self-assembled nanoscale electronics and (2) that 3D small-world interconnect fabrics with a power-law decaying distribution of shortcut lengths are physically plausible and have major advantages over local two-dimensional and 3D regular topologies.
Collapse
Affiliation(s)
- Christof Teuscher
- Los Alamos National Laboratory CCS-3, MS-B256, Los Alamos, New Mexico 87545, USA.
| |
Collapse
|
10
|
Yang H, Zhao F, Wang B. Synchronizabilities of networks: a new index. CHAOS (WOODBURY, N.Y.) 2006; 16:043112. [PMID: 17199390 DOI: 10.1063/1.2364178] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/13/2023]
Abstract
The random matrix theory is used to bridge the network structures and the dynamical processes defined on them. We propose a possible dynamical mechanism for the enhancement effect of network structures on synchronization processes, based upon which a dynamic-based index of the synchronizability is introduced in the present paper.
Collapse
Affiliation(s)
- Huijie Yang
- Department of Modern Physics, University of Science and Technology of China, Anhui Hefei 230026, China.
| | | | | |
Collapse
|