Evolution of Networks

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 Poisson-type 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 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
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, 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
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
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
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.