You are here

Random Graphs and Complex Networks, Volume 1

Remco van der Hofstad
Cambridge University Press
Publication Date: 
Number of Pages: 
Cambridge Series in Statistical and Probabilistic Mathematics
[Reviewed by
Richard Durrett
, on

To quote the preface: “This book is intended to be used for a master-level course where students have a limited prior knowledge of special topics in probability.” For this reason, the first thing after the fifty-page overview of the subject is Chapter 2, which deals with convergence of random variables, coupling, stochastic ordering, martingales, order statistics, and extreme value theory. Chapter 3 develops various topics in the theory of branching processes that are important for understanding connectivity properties of random graphs. Intuitively, if one picks a vertex x at random in a random graph with \(N\) vertices and lets \(Z_n\) be the number of vertices at distance \(n\) from \(x\), then \(Z_n\) is a branching process (at least until the number of vertices explored is \(N^a\) with \(a < 1/2\)). This implies that the probability a vertex is part of a giant component, i.e., one whose size is of order \(N\), is equal to the probability the branching process does not die out.

Chapter 4 begins the study of the Erdös-Rényi graph, which is created by starting with the complete graph on \(N\) vertices and keeping edges with probability \(\lambda/N\). The expected degree of a vertex is \(\lambda\), so it is not hard to show that if \(\lambda < 1\), all of the components are small (the largest is \(O(\log N)\)), while if \(\lambda > 1\) there is a giant component. Chapter 5 delves further considering the delicate critical case \(\lambda = 1\), where the largest component is \(O(N^{2/3})\), and the case \(\lambda = c \log N\), where, as \(c\) is varied, we have a phase transition in which the graph becomes connected (i.e., there is only one component).

The Erdös-Rényi graph has, in the limit \(N\to\infty\), a Poisson degree distribution with mean \(\lambda\), while many of the examples in Chapter 1 have degree distributions with power law tails, so it is important to have models with that property. Chapter 6 introduces generalized random graphs, a rather vague term for a situation in which vertices are given weights \(w_i\) and the edge from \(i\) to \(j\) is occupied with a probability based on \(w_iw_j\). Chung and Lu were the first to do this, see (6.8.1), but later formulations, see (6.2.1), have improved the original definition. Chapter 7 treats the configuration model. In the simplest version, vertices are assigned independent random degrees \(d_i\) (conditioned to have an even sum), \(d_i\) half-edges are assigned to vertex \(i\), and then the half-edges are paired at random. This procedure might produce self-loops or parallel edges. The “erased” version deals with this problem in Section 7.3, while the next section calculates the probability it does not occur.

The final chapter covers the preferential attachment in which edges are added one at a time, have initial degree \(m\) and connect to vertices chosen at random with probability proportional to their degrees. Many fundamental properties of the objects introduced in volume I are not proved until Volume II. By analogy with the Lord of the Rings, by the end of Volume I we have met Gandalf and the Hobbits are about to leave the Shire.

If I were writing this book then I would have covered fewer models and squeezed it into one volume. That is not a theoretical statement. I did write a 200 page book in 2007 that covers many of the models discussed here as well as dynamics on random graphs, which are covered in Remco’s St. Flour Notes. I am not saying my book is better. Indeed one review of my book said “you shouldn’t believe all the proofs in Durrett’s book,” many of which are just sketches. Indeed, recently one of my graduate students was reading my book, and switched to Remco’s since mine had too many typos and small errors.

If you combine the two volumes of Remco’s book with his St. Flour Notes you will have almost a 1000 pages, which gives a solid and well-written encyclopedic treatment of random graphs. However, I can’t help thinking that this is a situation in which less would have been more. I.e., rather that investigate all the variations, pick a half-dozen models that span the variations that have been considered, and study them in detail.

Richard Durrett taught at UCLA and Cornell before he came to Duke in 2010. He is a member of the National Academy of Science, who for the last thirty years has used probability to study problems that arise from ecology, genetics, and cancer modeling.

Course outline
1. Introduction

Part I. Preliminaries:
2. Probabilistics methods
3. Branching processes

Part II. Basic Models:
4. Phase transition for the Erdos–Renyi random graph
5. Erdos–Renyi random graph revisited

Part III. Models for Complex Networks:
6. Generalized random graphs
7. Configuration model
8. Preferential attachment models