Physics Reports 424 (2006) 175 – 308
www.elsevier.com/locate/physrep
Complex networks: Structure and dynamics
S. Boccaletti
a,∗
, V. Latora
b,c
, Y. Moreno
d, e
, M. Chavez
f
, D.-U. Hwang
a
a
CNR-Istituto dei Sistemi Complessi, Largo E. Fermi, 6, 50125 Florence, Italy
b
Dipartimento di Fisica e Astronomia, Universitá di Catania, Via S. Sofia, 64, 95123 Catania, Italy
c
Istituto Nazionale di Fisica Nucleare, Sezione di Catania, Via S. Sofia, 64, 95123 Catania, Italy
d
Instituto de Biocomputación y Física de Sistemas Complejos, Universidad de Zaragoza, Zaragoza 50009, Spain
e
Departamento de Fisica Teórica, Universidad de Zaragoza, Zaragoza 50009, Spain
f
Laboratoire de Neurosciences Cognitives et Imagerie Cérébrale (LENA) CNRS UPR-640, Hôpital de la Salpêtrière. 47 Bd. de l’Hôpital,
75651 Paris CEDEX 13, France
Accepted 27 October 2005
Available online 10 January 2006
editor: I. Procaccia
Abstract
Coupled biological and chemical systems, neural networks, social interacting species, the Internet and the World Wide Web,
are only a few examples of systems composed by a large number of highly interconnected dynamical units. The first approach to
capture the global properties of such systems is to model them as graphs whose nodes represent the dynamical units, and whose
links stand for the interactions between them. On the one hand, scientists have to cope with structural issues, such as characterizing
the topology of a complex wiring architecture, revealing the unifying principles that are at the basis of real networks, and developing
models to mimic the growth of a network and reproduce its structural properties. On the other hand, many relevant questions arise
when studying complex networks’ dynamics, such as learning how a large ensemble of dynamical systems that interact through a
complex wiring topology can behave collectively. We review the major concepts and results recently achieved in the study of the
structure and dynamics of complex networks, and summarize the relevant applications of these ideas in many different disciplines,
ranging from nonlinear science to biology, from statistical mechanics to medicine and engineering.
© 2005 Elsevier B.V. All rights reserved.
PACS: 05.45.−a
Contents
1. Introduction ...........................................................................................................177
1.1. The network approach to nature .....................................................................................177
1.2. Outline of the report ...............................................................................................179
2. The structure of complex networks........................................................................................180
2.1. Definitions and notations ...........................................................................................180
2.1.1. Node degree, degree distributions and correlations ...............................................................181
2.1.2. Shortest path lengths, diameter and betweenness .................................................................182
2.1.3. Clustering .................................................................................................183
2.1.4. Motifs ....................................................................................................184
∗
Corresponding author.
E-mail address: stefano@ino.it (S. Boccaletti).
0370-1573/$ - see front matter © 2005 Elsevier B.V. All rights reserved.
doi:10.1016/j.physrep.2005.10.009
176 S. Boccaletti et al. / Physics Reports 424 (2006) 175 – 308
2.1.5. Community structures .......................................................................................184
2.1.6. Graph spectra ..............................................................................................185
2.2. Topology of real networks ..........................................................................................186
2.2.1. The small-world property ....................................................................................187
2.2.2. Scale-free degree distributions ................................................................................187
2.2.3. Some examples .............................................................................................188
2.3. Networks models .................................................................................................191
2.3.1. Random graphs .............................................................................................191
2.3.2. Generalized random graphs ...................................................................................192
2.3.3. Small-world networks .......................................................................................193
2.3.4. Static scale-free networks ....................................................................................194
2.3.5. Evolving scale-free networks .................................................................................195
2.4. Weighted networks ................................................................................................198
2.4.1. Measures for weighted networks ..............................................................................198
2.4.2. Real weighted networks......................................................................................201
2.4.3. Modelling weighted networks .................................................................................203
2.5. Spatial networks ..................................................................................................205
2.5.1. The small-world behavior in Euclidean space ....................................................................207
2.5.2. Scale-free networks in Euclidean space .........................................................................208
2.5.3. Modelling real geographical networks ..........................................................................209
3. Static and dynamic robustness ...........................................................................................213
3.1. Static tolerance to errors and attacks ..................................................................................213
3.1.1. Numerical results ...........................................................................................213
3.1.2. Resilience in uncorrelated networks ............................................................................214
3.1.3. Resilience in correlated networks ..............................................................................216
3.1.4. Tolerance to attacks .........................................................................................219
3.2. Dynamical effects .................................................................................................220
3.2.1. Modelling cascading failures .................................................................................220
3.2.2. Congestion in communication networks ........................................................................225
4. Spreading processes ....................................................................................................228
4.1. Epidemic spreading ...............................................................................................228
4.1.1. The homogeneous mixing hypothesis ..........................................................................229
4.1.2. Uncorrelated networks
.......................................................................................230
4.1.3. Correlated networks .........................................................................................232
4.1.4. Fluctuating diseases .........................................................................................233
4.2. Rumor spreading ..................................................................................................234
5. Synchronization and collective dynamics ..................................................................................237
5.1. Introduction to synchronization ......................................................................................237
5.2. The Master stability function approach ...............................................................................238
5.3. Network propensity for synchronization ..............................................................................241
5.3.1. Synchronization in weighted networks: coupling matrices with real spectra ...........................................241
5.3.2. Synchronization in weighted networks: coupling matrices with complex spectra.......................................243
5.4. Synchronization of coupled oscillators ................................................................................246
5.5. Synchronization of chaotic dynamics .................................................................................248
5.6. Other collective behaviors in networks of ordinary differential equations ...................................................250
6. Applications ..........................................................................................................251
6.1. Social networks ...................................................................................................251
6.1.1. Structure ..................................................................................................251
6.1.2. Dynamics I: opinion formation ................................................................................253
6.1.3. Dynamics II: strategic games .................................................................................255
6.2. The Internet and the World Wide Web ................................................................................256
6.2.1. Structure of the Internet ......................................................................................257
6.2.2. Structure of the World Wide Web ..............................................................................259
6.2.3. Dynamics .................................................................................................260
6.3. Metabolic, protein, and genetic networks ..............................................................................260
6.3.1. Structure ..................................................................................................261
6.3.2. Dynamics .................................................................................................266
6.4. Brain networks ...................................................................................................267
6.4.1. Structure ..................................................................................................268
6.4.2. Dynamics .................................................................................................272
6.4.3. Open questions .............................................................................................274
7. Other topics ...........................................................................................................275
S. Boccaletti et al. / Physics Reports 424 (2006) 175 – 308 177
7.1. Algorithms for finding community structures ..........................................................................275
7.1.1. Spectral graph partitioning ...................................................................................276
7.1.2. Hierarchical clustering .......................................................................................276
7.1.3. The algorithm by Girvan and Newman .........................................................................279
7.1.4. Variations and extensions of the GN algorithm ...................................................................283
7.1.5. Fast methods based on the modularity ..........................................................................284
7.1.6. Other methods based on spectral analysis .......................................................................284
7.1.7. Other algorithms ............................................................................................286
7.2. Navigation and searching ...........................................................................................287
7.2.1. Searching with local information ..............................................................................287
7.2.2. Network navigability ........................................................................................289
7.3. Adaptive and dynamical wirings .....................................................................................291
Acknowledgements ........................................................................................................293
Note added in proof........................................................................................................293
References ...............................................................................................................294
1. Introduction
1.1. The network approach to nature
Networks are all around us, and we are ourselves, as individuals, the units of a network of social relationships of
different kinds and, as biological systems, the delicate result of a network of biochemical reactions. Networks can be
tangible objects in the Euclidean space, such as electric power grids, the Internet, highways or subway systems, and
neural networks. Or they can be entities defined in an abstract space, such as networks of acquaintances or collaborations
between individuals.
Historically, the study of networks has been mainly the domain of a branch of discrete mathematics known as graph
theory. Since its birth in 1736, when the Swiss mathematician Leonhard Euler published the solution to the Königsberg
bridge problem (consisting in finding a round trip that traversed each of the bridges of the prussian city of Königsberg
exactly once), graph theory has witnessed many exciting developments and has provided answers to a series of practical
questions such as: what is the maximum flow per unit time from source to sink in a network of pipes, how to color the
regions of a map using the minimum number of colors so that neighboring regions receive different colors, or how to
fill n jobs by n people with maximum total utility. In addition to the developments in mathematical graph theory, the
study of networks has seen important achievements in some specialized contexts, as for instance in the social sciences.
Social networks analysis started to develop in the early 1920s and focuses on relationships among social entities, as
communication between members of a group, trades among nations, or economic transactions between corporations.
The last decade has witnessed the birth of a new movement of interest and research in the study of complex networks,
i.e. networks whose structure is irregular, complex and dynamically evolving in time, with the main focus moving from
the analysis of small networks to that of systems with thousands or millions of nodes, and with a renewed attention to
the properties of networks of dynamical units. This flurry of activity, triggered by two seminal papers, that by Watts and
Strogatz on small-world networks, appeared in Nature in 1998, and that by Barabási and Albert on scale-free networks
appeared one year later in Science, has seen the physics’ community among the principal actors, and has been certainly
induced by the increased computing powers and by the possibility to study the properties of a plenty of large databases
of real networks. These include transportation networks, phone call networks, the Internet and the World Wide Web,
the actors’ collaboration network in movie databases, scientific coauthorship and citation networks from the Science
Citation Index, but also systems of interest in biology and medicine, as neural networks or genetic, metabolic and
protein networks.
The massive and comparative analysis of networks from different fields has produced a series of unexpected and
dramatic results. The first issue that has been faced is certainly structural. The research on complex networks begun
with the effort of defining new concepts and measures to characterize the topology of real networks. The main result has
been the identification of a series of unifying principles and statistical properties common to most of the real networks
considered. A relevant property regards the degree of a node, that is the number of its direct connections to other nodes.
In real networks, the degree distribution P(k), defined as the probability that a node chosen uniformly at random has
degree k or, equivalently, as the fraction of nodes in the graph having degree k, significantly deviates from the Poisson
distribution expected for a random graph and, in many cases, exhibits a power law (scale-free) tail with an exponent
178 S. Boccaletti et al. / Physics Reports 424 (2006) 175 – 308
taking a value between 2 and 3. Moreover, real networks are characterized by correlations in the node degrees, by
having relatively short paths between any two nodes (small-world property), and by the presence of a large number of
short cycles or specific motifs.
These empirical findings have initiated a revival of network modelling, since the models proposed in mathematical
graph theory turned out to be very far from the real needs. Scientists had to do with the development of new models to
mimic the growth of a network and to reproduce the structural properties observed in real topologies. The structure of
a real network is the result of the continuous evolution of the forces that formed it, and certainly affects the function
of the system. So that this stage of the research was motivated by the expectancy that understanding and modelling
the structure of a complex network would lead to a better knowledge of its evolutionary mechanisms, and to a better
cottoning on its dynamical and functional behavior.
And, indeed, it was shown that the coupling architecture has important consequences on the network functional
robustness and response to external perturbations, as random failures, or targeted attacks. At the same time, it outcropped
for the first time the possibility of studying the dynamical behavior of large assemblies of dynamical systems interacting
via complex topologies, as the ones observed empirically. This led to a series of evidences pointing to the crucial role
played by the network topology in determining the emergence of collective dynamical behavior, such as synchronization,
or in governing the main features of relevant processes that take place in complex networks, such as the spreading of
epidemics, information and rumors.
A number of review articles [1–4] and books [5–8] on complex networks, which the reader may find useful to consult,
have already appeared in the literature. Watts’ pioneering book on the subject deals with the structure and the dynamics
of small-world networks [5], while Strogatz’ review article in the Nature’s special issue on complex systems contains
a discussion on networks of dynamical units [1]. Albert and Barabási [2], and Dorogovtsev and Mendes [3,7] have
mainly focused their reviews on models of growing graphs, from the point of view of statistical mechanics. The review
by Newman is a critical account on the field [4], containing an accurate list of references, an exhaustive overview on
structural properties, measures and models, and also a final chapter devoted to processes taking place on networks.
Four other references are worthwhile to mention at the beginning of this Report. They are the collection of contributed
papers edited by Bornholdt and Schuster [6], that edited by Pastor-Satorras et al. [9], that edited by Ben-Naim et al.
[10], and the book by Pastor-Satorras and Vespignani on the analysis and modelling of the Internet [8]. There is also
a series of popular books on complex networks available on the market for the lay audience [11–13]. See for instance
Buchanan’s Nexus, for having the point of view of a science journalist on the field [11]. Furthermore, a variety of
related books dealing with networks in specific fields of research has been published. In the context of graph theory,
the books by Bollobás [14,15], West [16] and Harary [17] deserve to be quoted. The textbooks by Wasserman and
Faust [18] and by Scott [19] are widely known among people working in social networks analysis. Refs. [20–22] are,
instead, useful sources for the description of the standard graph algorithms.
Is this subject deserving another report? At least three reasons have motivated our work.
The first is that new research lines have emerged, covering novel topics and problems in network structure. An
example is the fresh and increasingly challenging care to study weighted networks, i.e. networks in which a real
number is associated to each link. This is motivated by the fact that in most of the real cases a complex topology
is often associated with a large heterogeneity in the capacity and intensity of the connections. Paradigmatic cases
are the existence of strong and weak ties between individuals in social systems, different capabilities of transmitting
electric signals in neural networks, unequal traffic on the Internet. Ignoring such a diversity in the interactions would
mean leaving away a lot of information on complex networks which is, instead, available and very useful for their
characterization. A further novel topic concerns spatial networks. While most of the early works on complex networks
have focused on the characterization of the topological properties, the spatial aspect has received less attention, when
not neglected at all. However, it is not surprising that the topology could be constrained by the geographical embedding.
For instance, the long range connections in a spatial network are constrained by the Euclidean distance, this having
important consequences on the network’s statistical properties. Also the degree is constrained because the number of
edges that can be connected to a single node is limited by the physical space to connect them. This is particularly evident
in planar networks (e.g. networks forming vertices whenever two edges cross), as urban streets, where only a small
number of streets can cross in an intersection. And even in non-planar spatial networks, such as airline networks the
number of connections is limited by the space available at the airport. These facts contribute to make spatial networks
different from other complex networks. Along with a full account on structural properties, the present review includes
all this novel material, and its many applications to relevant concrete situations.
S. Boccaletti et al. / Physics Reports 424 (2006) 175 – 308 179
The second reason is that most of the interest in the subject has lately switched to investigate the dynamical behavior
of networks, with a special emphasis on how the network structure affects the properties of a networked dynamical
system. An example is the concerned attention to study the emergence of collective synchronized dynamics in complex
networks, from the point of view of relating the propensity for synchronization of a network to the interplay between
topology and local properties of the coupled dynamical systems. This phenomenon, indeed, represents a crucial feature
in many relevant circumstances. For instance, evidence exists that some brain diseases are the result of an abnormal
and, some times, abrupt synchronization of a large number of neural populations, so that the investigation on the
network mechanisms involved in the generation, maintenance and propagation of the epileptic disorders is an issue
nowadays at the forefront of neuroscience. Synchronization phenomena are very relevant also in sociology to gather
a better understanding of the mechanisms underlying the formation of social collective behaviors, as the sudden
emergence of new habits, fashions or leading opinions. A large portion of the second part of this Report is devoted
to summarize the main achievements that have been obtained so far in dealing with collective behaviors in complex
networks, reviewing the major ideas and concepts that have been developed, and assessing the rigorous results that are
nowadays available.
Finally, we present a survey of a series of topics that are currently attracting much attention in the scientific community.
These include the problem of building manageable algorithms to find community structures, the issue of searching
within a complex network, and the modelling of adaptive networks.
Community structures are an important property of complex networks. For example, tightly connected groups of
nodes in a social network represent individuals belonging to social communities, tightly connected groups of nodes in
the World Wide Web often correspond to pages on common topics, while communities in cellular and genetic networks
are somehow related to functional modules. Consequently, finding the communities within a network is a powerful
tool for understanding the functioning of the network, as well as for identifying a hierarchy of connections within a
complex architecture.
Another relevant problem is how to reach a node of the network from another one, by navigating the network often
in the absence of information on the global structure, or how to optimize a searching procedure based only on some
local information on the network topology.
Adaptive and dynamical wirings are a peculiarity of those networks that are themselves dynamical entities. This
means that the topology is not fixed, or grown, once forever. Instead it is allowed to evolve and adapt in time, driven
by some external action, or by the action of the internal elements, or following specific predetermined evolving rules.
This step forward has been motivated by the need of suitably modelling some specific cases, such as genetic regulatory
networks, ecosystems, financial markets, as well as to properly describe a series of technologically relevant problems
emerging, e.g., in mobile and wireless connected units. In some cases, the research work has just begun, and, even
though the results are not so firmly established, we believe that the state of the art calls for future relevant achievements.
1.2. Outline of the report
The Report is organized as follows.
Chapter 2 is about network structure. We describe some of the common properties observed in the topology of real
networks, and how they are measured. We then briefly review the main models that have been proposed over the years,
focusing on random graphs, small-world models and scale-free networks. Finally, we give a special emphasis to the
study and modelling of weighted networks, as well as networks with a spatial structure.
In Chapter 3 we discuss the network robustness against external perturbations consisting in the malfunctioning,
or the deliberate damage, of some of its components. We review both static and dynamical approaches. Specifically,
we describe percolation processes on uncorrelated and correlated networks, cascading failures, and congestion in
transportation and communication networks.
In Chapter 4 we consider cellular automata on complex topologies and we analyze a series of models for the spreading
of epidemics and rumors.
Chapter 5 is concerned with the emergence of collective synchronized dynamics in complex networks. In this context,
we review the most significant advancement represented by the Master Stability Function approach, giving conditions in
the wiring topology that maximize the propensity for synchronization of a network. We furthermore consider networks
whose dynamical units evolve nonlinearly, and we review the main results obtained with networks of chaotic maps,
networks of chaotic systems, and with networks of periodic oscillators.
- 1
- 2
前往页