Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.

Consider the random graph on n vertices 1,…,n. Each vertex i is assigned a type x_i with x₁,…,x_n being independent identically distributed as a nonnegative random variable X. We assume that EX³< ∞. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability \begin{align*}\min \{1, \frac{x_ix_j}{n}\left(1+\frac{a}{n^{1/3}} \right) \}\end{align*}. We study the critical phase, which is known to take place when EX² = 1. We prove that normalized by n^‐2/3the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient \begin{align*}\sqrt{{\textbf{ E}}X{\textbf{ E}}X^3}\end{align*}and drift \begin{align*}a-\frac{{\textbf{ E}}X^3}{{\textbf{ E}}X}s\end{align*}. In particular, we conclude that the size of the largest connected component is of order n^2/3. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486–539, 2013