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).
WWWWWWWWWWWw
PREFACE
uuuThis book is about the growth and structure of random networks.
The book is written by physicists and
presents the point of view of a physicist,
but is 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 Poissontype distribution of connections.
Mathematicians have made truly great advances in the description of such networks.
uuuOnly recently have we realized that we reside in a world of networks.
The 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 country.
`Network' turns out to be a central notion in our time, and
the explosion 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 fattailed 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 evolution.
Only in the last few
years have physicists started extensive empirical and theoretical research
into
networks organized in such a way.
Earlier, physicists' interest was rather in neural and Boolean networks
where
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 phenomena,
diffusion, selforganized 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 minimal mathematics.
Special attention is given to real networks, both natural and artificial.
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 approach.
We feel that it is more important to be understood than to
be perfectly rigorous.
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 footnotes.
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
AlbertL'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 their coauthors
for permission to use data from their original figures for derivative reproduction.
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.
Our computers 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 and hospitality.
PortoWWWWWWWWWWWWWWWWWWWWWWWWWWWWWu. S.N.D.
May 2002WWWWWWWWWWWWWWWWWWWWWWWWWWW J.F.F.M.
Sergey Dorogovtsev
