By S N Dorogovstsev and J F F Mendes, Oxford University Press. Hardback ISBN 0198515901, £49.95 ($95).
Imagine some collections of diverse objects: autonomous systems on the Internet, pages on the World Wide Web, neurons, genes, proteins, citations of scientific publications, the words in a human language, etc. Is it not fascinating that the graph-based abstractions of these different systems reveal that certain qualitative relationships among the objects remain invariant from one system to another? For instance, it was found that in a graph of the protein interactions of the yeast S.cerevisiae, the number of nearest neighbours follows a power-law distribution just as in a graph of the pages on the World Wide Web.
This book is an introduction to the exciting area of networks modelled as random graphs. The authors describe some fundamental structural properties of these graphs, and give a tour through a variety of real-world examples. They explain the underlying mechanisms that drive the evolution of graphs over time, and discuss the impact that a structural property of a graph may have on performance issues such as virus spreading and network connectivity.
As Dorogovstev and Mendes put it, this book was written by physicists but is aimed at a broader audience. The technical developments are kept at a low level, so no particular prerequisites are needed to follow them, and the authors present timely examples that cover the broad scope of the book.
The first chapter gives definitions of basic metrics that characterize a graph. The next chapter is devoted to exposing the preferential linking, a principle that, for instance, explains the emergence of the power-law distribution of the number of nearest neighbours of a vertex in a graph. The book proceeds with a discussion of a broad set of network examples, including scientific literature, communication systems and biological systems. In the subsequent two chapters, the authors separately cover equilibrium and non-equilibrium networks. The chapter on equilibrium networks analyses the stochastic recursive evolutions that drive a random graph to its steady state (equilibrium). A standard example in this context is the construction of a random graph by Erdos and Renyi. The chapter on non-equilibrium networks focuses on temporal aspects, especially the evolution of some probability measures of a graph over time. The book continues with a chapter on the global properties of graphs and their effect on performance. The authors end with appendices including some mathematical content and a detailed bibliography on the graph literature.
The exposition of the book is very pedagogical. Instead of rushing to examples, the authors first introduce readers to important elementary notions. After motivating the problems through well-chosen examples, they delve into specific subjects in detail, and the fundamental principles are unveiled in a suitable manner. There is, however, a certain imbalance in the lengths of different chapters.
This book should benefit readers who seek to gain an insight into the fundamental principles that underlie the random graphs found in diverse scientific disciplines.
