article

Title: Giant components in biased graph processes

Authors: Gideon Amir, Ori Gurel-Gurevich, Eyal Lubetzky and Amit Singer

Issue: Volume 59 (2010), Issue 6, 1893-1930

Abstract:

$A random graph process, $\mathcal{G}_1(n)$, is a sequence of graphs on $n$ vertices which begins with the edgeless graph, and where at each step a single edge is added according to a uniform distribution on the missing edges. It is well known that in such a process a giant component (of linear size) typically emerges after $(1+o(1))n/2$ edges (a phenomenon known as `the double jump'), i.e., at time $t=1$ when using a timescale of $n/2$ edges in each step. We consider a generalization of this process, $\mathcal{G}_K(n)$, proposed by Itai Benjamini in order to model the spreading of an epidemic. This generalized process gives a weight of size $1$ to missing edges between pairs of isolated vertices, and a weight of size $K\in[0,\infty)$ otherwise. This corresponds to a case where links are added between $n$ initially isolated settlements, where the probability of a new link in each step is biased according to whether or not its two endpoint settlements are still isolated. Combining methods of [J. Spencer and N.C. Wormald, \textit{Birth control for giants}, Combinatorica \textbf{27} (2007), 587--628] with analytical techniques, we describe the typical emerging time of a giant component in this process, $t_c(K)$, as the singularity point of a solution to a set of differential equations. We proceed to analyze these differential equations and obtain properties of $\mathcal{G}_K$, and in particular, we show that $t_c(K)$ strictly decreases from $\frac{3}{2}$ to $0$ as $K$ increases from $0$ to $\infty$, and that $t_c(K) = (4/\sqrt{3K})(1+o(1))$, where the $o(1)$-term tends to $0$ as $K\to\infty$. Numerical approximations of the differential equations agree both with computer simulations of the process $\mathcal{G}_K(n)$ and with the analytical results.$