On two biased graph processes

MaRDI QIDQ6477633zbMATH OpenFDO

Authors Gideon Amir, Eyal Lubetzky

Publication date 3 August 2006

Abstract: In [Amir et al.], the authors consider the generalization $Gor$ of the ErdH{o}s-R'enyi random graph process $G$, where instead of adding new edges uniformly, $Gor$ gives a weight of size 1 to missing edges between pairs of isolated vertices, and a weight of size $Kin[0,infty)$ otherwise. This can correspond to the linking of settlements or the spreading of an epidemic. The authors investigate $gor(K)$, the critical time for the appearance of a giant component as a function of $K$, and prove that $gor=(1+o(1))frac4sqrt3K$, using a proper timescale. In this work, we show that a natural variation of the model $Gor$ has interesting properties. Define the process $Gand$, where a weight of size $K$ is assigned to edges between pairs of non-isolated vertices, and a weight of size 1 otherwise. We prove that the asymptotical behavior of the giant component threshold is essentially the same for $Gand$, and namely $gand/gor$ tends to $frac64sqrt6pi(24+p{i}^2)approx1.47$ as $Koinfty$. However, the corresponding thresholds for connectivity satisfy $cand/cor=max1/2,K$ for every $K>0$. Following the methods of [Amir et al.], $gand$ is characterized as the singularity point to a system of differential equations, and computer simulations of both models agree with the analytical results as well as with the asymptotic analysis. In the process, we answer the following question: when does a giant component emerge in a graph process where edges are chosen uniformly out of all edges incident to isolated vertices, while such exist, and otherwise uniformly? This corresponds to the value of $gand(0)$, which we show to be $3/2+frac43mathrm{e}^2-1$.

This page was built for publication: On two biased graph processes

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