Giant components in biased graph processes

DOI10.1512/IUMJ.2010.59.4008MaRDI QIDQ2879948zbMATH OpenOpenAlexFDO

Authors Gideon Amir, Ori Gurel-Gurevich, Eyal Lubetzky, A. Singer

Publication date 10 April 2012

Published in Indiana University Mathematics Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0511526, http://www.iumj.indiana.edu/IUMJ/ABS/2010/4008

zbMATH Keywords

random graphsgiant componentwormald's differential equation method

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analytic approximation of solutions (perturbation methods, asymptotic methods, series, etc.) of dynamical problems in solid mechanics (74H10)

Abstract: A random graph process, $Gorg[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))fracn2$ 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, $Gorg[K](n)$, which gives a weight of size 1 to missing edges between pairs of isolated vertices, and a weight of size $Kin[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 cite{SpencerWormald} 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 $Gorg$, and in particular, we show that $t_c(K)$ strictly decreases from 3/2 to 0 as $K$ increases from 0 to $infty$, and that $t_c(K)=frac4sqrt3K(1+o(1))$. Numerical approximations of the differential equations agree both with computer simulations of the process $Gorg(n)$ and with the analytical results.

Recommendations

• Birth control for giants
• On a random graph with immigrating vertices: Emergence of the giant component
• Component behavior near the critical point of the random graph process
• Creating a Giant Component
• scientific article; zbMATH DE number 1984542

Cited in

(1)

• Giant components in random graphs

This page was built for publication: Giant components in biased graph processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2879948)