On two biased graph processes

Details On two biased graph processes On two biased graph processes

2006-08-03

arxiv.org/abs/math/0608097v1

Mathematics

Combinatorics

Scientific paper

In [Amir et al.], the authors consider the generalization $\Gor$ of the Erd\H{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 $K\in[0,\infty)$ otherwise. This can correspond to the linking of settlements or the spreading of an epidemic. The authors investigate $\tgor(K)$, the critical time for the appearance of a giant component as a function of $K$, and prove that $\tgor=(1+o(1))\frac{4}{\sqrt{3K}}$, 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 $\tgand / \tgor$ tends to $\frac{64\sqrt{6}}{\pi(24+\pi^2)}\approx 1.47$ as $K\to\infty$. However, the corresponding thresholds for connectivity satisfy $\tcand / \tcor=\max\{{1/2},K\}$ for every $K>0$. Following the methods of [Amir et al.], $\tgand$ 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 $\tgand(0)$, which we show to be ${3/2}+\frac{4}{3\mathrm{e}^2-1}$.

Affiliated with

Also associated with

No associations

Rating

On two biased graph processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On two biased graph processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On two biased graph processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-50896