3 - Connectivity and Poisson approximation

Summary

Introduction

In Chapter 2 we saw that, when the average degree np of an Erdős–Rényi graph is of constant order λ > 1, the graph contains a giant component of size of order n with high probability. However, in that regime, this component's size is strictly less than n, so that the graph is disconnected.

In the present chapter we shall establish that connectivity appears when the product np is of order log n. We shall more precisely evaluate the probability of connectivity when np is asymptotic to log n + c for some constant c. In the framework of the Reed–Frost epidemic this corresponds to a regime known as atomic infection wherein all nodes are ultimately infected. In this regime we can analyse the time, in terms of the number of rounds, it takes the epidemic or the rumour to reach the whole population. This will be illustrated in Chapter 4 for the Reed–Frost epidemic and revisited in Chapter 6 when we introduce the small-world phenomenon.

The main mathematical tool required to prove the connectivity regime consists of Poisson approximation techniques, namely the Stein–Chen method. The Stein–Chen method provides bounds on how accurately a sum of {0, 1}-valued or Bernoulli random variables can be approximated by a Poisson distribution.