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}send{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