Synchronization in scale-free dynamical networks: robustness and fragility
IEEE Transactions on Circuits and Systems I Fundamental Theory and ApplicationsPublished 1 January 2002
Xiao Fan Wang, Guanrong Chen
Citations1,118
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that if the coupling strength of a scale-free dynamical network is greater than a positive threshold, then the network will synchronize no matter how large it is, which is robust against random removal of nodes, but is fragile to specific removal of the most highly connected nodes.
Abstract
Recently, it has been demonstrated that many large complex networks display a scale-free feature, that is, their connectivity distributions are in the power-law form. In this paper, we investigate the synchronization phenomenon in scale-free dynamical networks. We show that if the coupling strength of a scale-free dynamical network is greater than a positive threshold, then the network will synchronize no matter how large it is. We show that the synchronizability of a scale-free dynamical network is robust against random removal of nodes, but is fragile to specific removal of the most highly connected nodes.
Keywords
Computer SciencePhysics and Astronomy
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
Cambridge University Press eBooksSocial Network Analysis
17,041 Citations1994Stanley Wasserman, Katherine Faust
This paper presents mathematical representation of social networks in the social and behavioral sciences through the lens of dyadic and triadic interaction models, which provide insights into the structure and dynamics of relationships between actors and groups.
Physical Review LettersSynchronization in chaotic systems
10,564 Citations1990Louis M. Pecora, Thomas L. Carroll
This chapter describes the linking of two chaotic systems with a common signal or signals and highlights that when the signs of the Lyapunov exponents for the subsystems are all negative the systems are synchronized.
NatureExploring complex networks
8,339 Citations2001Steven H. Strogatz
This work aims to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture.
NatureError and attack tolerance of complex networks
7,218 Citations2000Réka Albert, Hawoong Jeong +1 more
It is found that scale-free networks, which include the World-Wide Web, the Internet, social networks and cells, display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates.
Physical Review LettersEpidemic Spreading in Scale-Free Networks
5,770 Citations2001Romualdo Pastor‐Satorras, Alessandro Vespignani
A dynamical model for the spreading of infections on scale-free networks is defined, finding the absence of an epidemic threshold and its associated critical behavior and this new epidemiological framework rationalizes data of computer viruses and could help in the understanding of other spreading phenomena on communication and social networks.
NatureDiameter of the World-Wide Web
4,285 Citations1999Réka Albert, Hawoong Jeong +1 more
The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.
On power-law relationships of the Internet topology
4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.
NatureThe large-scale organization of metabolic networks
4,031 Citations2000H. Jeong, B. Tombor +3 more
This analysis of metabolic networks of 43 organisms representing all three domains of life shows that, despite significant variation in their individual constituents and pathways, these metabolic networks have the same topological scaling properties and show striking similarities to the inherent organization of complex non-biological systems.
Computer NetworksGraph structure in the Web
2,760 Citations2000Andrei Broder, Ravi Kumar +6 more
The study of the web as a graph yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.
ACM SIGCOMM Computer Communication ReviewOn power-law relationships of the Internet topology
2,599 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
Physical Review LettersNetwork Robustness and Fragility: Percolation on Random Graphs
2,422 Citations2000Duncan S. Callaway, M. E. J. Newman +2 more
This paper studies percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolators, bond percolations, and models in which occupation probabilities depend on vertex degree.
Choice Reviews OnlineSmall worlds: the dynamics of networks between order and randomness
2,393 Citations2000
Physical Review LettersResilience of the Internet to Random Breakdowns
2,327 Citations2000Reuven Cohen, Keren Erez +2 more
This work shows analytically and numerically that for alpha0.99.
Physica A Statistical Mechanics and its ApplicationsMean-field theory for scale-free random networks
2,251 Citations1999Albert-Ĺaszló Barabási, Réka Albert +1 more
A mean-field method is developed to predict the growth dynamics of the individual vertices of the scale-free model, and this is used to calculate analytically the connectivity distribution and the scaling exponents.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsEpidemic dynamics and endemic states in complex networks
1,665 Citations2001Romualdo Pastor‐Satorras, Alessandro Vespignani
A dynamical model for the spreading of epidemics in complex networks that implies that scale-free networks are prone to the spreading and the persistence of infections whatever spreading rate the epidemic agents might possess.
The European Physical Journal BHow popular is your paper? An empirical study of the citation distribution
1,508 Citations1998S. Redner
Physica A Statistical Mechanics and its ApplicationsScale-free characteristics of random networks: the topology of the world-wide web
1,409 Citations2000Albert-Ĺaszló Barabási, Réka Albert +1 more
This work introduces a model that leads to a scale-free network, capturing in a minimal fashion the self-organization processes governing the world-wide web.
Physical Review LettersTopology of Evolving Networks: Local Events and Universality
1,322 Citations2000Réka Albert, Albert-Ĺaszló Barabási
A continuum theory is proposed that predicts the connectivity distribution of the network describing the professional links between movie actors as well as the scaling function and the exponents, in good agreement with numerical results.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSearch in power-law networks
1,207 Citations2001Lada A. Adamic, Rajan M. Lukose +2 more
A number of local search strategies that utilize high degree nodes in power-law graphs and that have costs scaling sublinearly with the size of the graph are introduced and demonstrated on the GNUTELLA peer-to-peer network.
SciencePower-Law Distribution of the World Wide Web
1,018 Citations2000Lada A. Adamic, Bernardo A. Huberman
An improved version of the Erdos-Renyi (ER) theory of random networks is proposed to account for the scaling properties of a number of systems, including the link structure of the World Wide Web.
IEEE Transactions on Circuits and Systems I Fundamental Theory and ApplicationsSynchronization in an array of linearly coupled dynamical systems
975 Citations1995Chai Wah Wu, Leon O. Chua
NatureGrowth dynamics of the World-Wide Web
865 Citations1999Bernardo A. Huberman, Lada A. Adamic
It is found that web pages are distributed among sites according to a universal power law: many sites have only a few pages, whereas very few sites have hundreds of thousands of pages.
International Journal of Bifurcation and ChaosSYNCHRONIZATION IN SMALL-WORLD DYNAMICAL NETWORKS
857 Citations2002Xiao Fan Wang, Guanrong Chen
It is shown that, for any given coupling strength and a suciently large number of cells, the small-world dynamical network will synchronize, even if the original nearest-neighbor coupled network cannot achieve synchronization under the same condition.
ASME Press eBooksSynchronization in science and technology
579 Citations1988Ilʹi︠a︡ Izrailevich Blekhman
This book describes examples and applications of synchronization, and gives the problem a working mathematical formulation, for a wide range of specialists who may encounter nonlinear vibrations problems.
Physical Review LettersFast Response and Temporal Coherent Oscillations in Small-World Networks
574 Citations2000Luis F. Lago-Fernández, Ramón Huerta +2 more
Small-world topologies, which fall between random and regular ones, take advantage of the best features of both, giving rise to fast system response with coherent oscillations.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsHighly optimized tolerance: A mechanism for power laws in designed systems
550 Citations1999Jean M. Carlson, John C. Doyle
This work introduces a mechanism for generating power law distributions, referred to as highly optimized tolerance (HOT), which is motivated by biological organisms and advanced engineering technologies, and investigates the mechanism in the context of percolation and sand pile models in order to emphasize the sharp contrasts between SOC and self-organized criticality.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSynchronous chaos in coupled oscillator systems
466 Citations1994James F. Heagy, Thomas L. Carroll +1 more
IEEE Transactions on Circuits and Systems I Fundamental Theory and ApplicationsA universal circuit for studying and generating chaos. I. Routes to chaos
439 Citations1993Leon O. Chua, Chai Wah Wu +2 more
Physical Review LettersHighly Optimized Tolerance: Robustness and Design in Complex Systems
328 Citations2000Jean M. Carlson, John C. Doyle
This work studies the impact of incorporating increasing levels of design and finds that even small amounts of design lead to HOT states in percolation.
Princeton University Press eBooksThe large-scale organization of metabolic networks
280 Citations2011Hawoong Jeong, B. Tombort +3 more
IEEE/ACM Transactions on NetworkingThe synchronization of periodic routing messages
245 Citations1994Sally Floyd, Van Jacobson
The authors study the synchronization of periodic routing messages, and offer guidelines on how to avoid inadvertent synchronization, and show that synchronization can be avoided by the addition of randomization to the traffic sources and quantify how much randomization is necessary.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSynchronous chaos in coupled map lattices with small-world interactions
234 Citations2000Prashant M. Gade, Chin‐Kun Hu
It is shown that, for a fixed fraction of nonlocal couplings, synchronous chaos is always a stable attractor in the thermodynamic limit and it is pointed out that randomness helps synchronization.
Cambridge University Press eBooksEvolution of random graphs
145 Citations1998V. F. Kolchin
It is proved that if M = n/2 + s, s = o(n) and s > (log nj'^n2/3 then the giant component has (4 + o(l))s vertices, and rather precise estimates are given for the order of the rth largest component for every fixed r.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsInstability and controllability of linearly coupled oscillators: Eigenvalue analysis
124 Citations1998Guang Hu, Junzhong Yang +1 more
International Journal of Bifurcation and ChaosSYNCHRONIZATION STABILITY IN COUPLED OSCILLATOR ARRAYS: SOLUTION FOR ARBITRARY CONFIGURATIONS
120 Citations2000Lou Pecora, TOM CARROLL +3 more
A very general formulation of the identical synchronization problem is developed, it is shown that asymptotic results can be derived for very general cases, and it is demonstrated that simple oscillator configurations can probe the Master Stability Function.
Physical Review LettersPower Laws, Highly Optimized Tolerance, and Generalized Source Coding
108 Citations2000John C. Doyle, Jean M. Carlson
Optimized solutions yield the "robust, yet fragile" features of highly optimized tolerance and exhibit power law tails in the distributions of events for all but the special case of Shannon coding for data compression.
NatureHow robust is the Internet?
70 Citations2000Yuhai Tu
A new study warns against complacency — the feature that makes the Internet immune to accidents also makes it vulnerable to attack.
IEEE Transactions on Circuits and Systems I Fundamental Theory and ApplicationsRobustness and stability of synchronized chaos: an illustrative model
36 Citations1997M. M. Sushchik, Nikolai F. Rulkov +1 more