Evolution of Networks
to home page
S.N. Dorogovtsev and J.F.F. Mendes,
Evolution of Networks:
From Biological Nets to the Internet and WWW
(Oxford University Press, Oxford, 2003).
uuuThis book is about the growth and structure of random networks.
is written by physicists and
presents the point of view of a physicist,
addressed to all researchers involved in this subject and students.
uuuWhere was physics 50 years ago, and where is it now?
At first sight, the
role of physics is decreasing; other natural sciences are developing more rapidly.
However, physics has penetrated into all sciences. A natural step for a physicist
is to jump from the traditional topics of physics to new intriguing problems.
Actually, our book describes a flight from physics to the new interdisciplinary
field of networks. This escape is, however,
still dependent on physics.
uuuFor many years the term `random graphs' usually meant to mathematicians
static, `equilibrium' networks with a Poisson-type distribution of connections.
Mathematicians have made truly great advances in the description of such
uuuOnly recently have we realized that we reside in a world of networks.
Internet and World Wide Web (WWW) are changing our lives. Our physical
existence is based on various biological networks. The extent of the development
of communications networks is a good indicator of
the level of development in a
`Network' turns out to be a central notion in our time, and
of interest in networks is already
a social and cultural phenomenon.
uuuGraph theory has made great progress.
However, the most important natural
and artificial networks have a
specific architecture based on a fat-tailed
distribution of the number of connections of vertices
that differs crucially from the
`classical random graphs' studied by mathematicians.
As a rule, these networks
are not static but evolving objects. Their state is far from equilibrium and their
structure cannot be understood without insight into the principles of their
Only in the last few
years have physicists started extensive empirical and
networks organized in such a way.
interest was rather in neural and Boolean networks
the arrangement of
connections was secondary.
uuuWe think that the physics approach
is the most advantageous for understanding
the evolution of networks. Actually, what we physicists are now doing on this
active topic is a direct generalization of the usual physics of growth, percolation
diffusion, self-organized criticality, mesoscopic systems, etc.
uuuOur aim is to understand networks: that is, to understand the basic principles
of their structural organization and evolution.
We believe that this understanding
is necessary to find the best solutions to the problems of real networks.
uuuWe decided to present a concise informative book which could be used even
by students without a deep knowledge of mathematics and statistical physics
and which would be a good source of reference material.
Therefore we have tried
to introduce the main ideas and concepts in as simple a manner as possible, with
Special attention is given to real networks, both natural
We discuss in detail the collected empirical data and numerous
real applications of existing theories. The urgent problems of communication
networks are highlighted and discussed.
uuuFor a description of network evolution, we prefer to use a simpler continuum
We feel that it is more important to be understood than to
Also, we follow the hierarchy of values in Western science: an
experiment and empirical data are more valuable than an estimate; an estimate
is more valuable than an approximate calculation; an approximate calculation
is more valuable than a rigorous result.
More cumbersome calculations and
supplementary materials are placed in appendices. We hope that all of the results
and statements that we discuss can be easily found in the text and understood
without undertaking detailed calculations.
Therefore, we ask our brave readers
to skim over difficult pages without hesitation and not to pay any attention to
However, as this is a monograph written by theoretical physicists, we
try to keep a `physical level' of strictness in our explanations and definitions.
Although, we try to avoid superfluous words,
we are not afraid to repeat important
statements at a different level.
We hope that the book will also be useful to
mathematicians, as a source
of interesting new objects and ideas.
uuuWe thank our friends and colleagues for their help. Foremost among these are
our collaborators in this field: Alexander V. Goltsev and Alexander N. Samukhin
from the Ioffe Institute in St Petersburg.
We did not reprint figures with
empirical data from original papers but made sketches of data. We are grateful to
Albert-L'aszl'o Barab'asi, Stefan Bornholdt, Jonathan Doye, Jennifer Dunne, Lee
Giles, Ramesh Govindan, Byungnam Kahng, Ravi Kumar, Neo Martinez, Sergei
Maslov, Mark Newman, Sidney Redner, Ricard Sol'e, Alessandro Vespignani, and
for permission to use data from their original figures for derivative
We are much indebted to John Bulger, Ester Richards, Chris
Fowler, David Duckitt, Goutam Tripathy, and Neville Hankins, the copy editor
at Oxford University Press for correcting the English of our book.
did not crash only thanks to Miguel Dias Costa and Joao Viana Lopes.
When this book was written, one of us (SND) was on leave from his native Ioffe
Institute, and he acknowledges the Centre of Physics of Porto for their support
May 2002WWWWWWWWWWWWWWWWWWWWWWWWWWW J.F.F.M.