Giant Components in Biased Graph Processes

Details Giant Components in Biased Graph Processes Giant Components in Biased Graph Processes

2005-11-21

arxiv.org/abs/math/0511526v2

Mathematics

Probability

31 pages, 3 figures

Scientific paper

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))\frac{n}{2}$ 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 $K \in [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) = \frac{4}{\sqrt{3K}}(1 + o(1))$. Numerical approximations of the differential equations agree both with computer simulations of the process $\Gorg(n)$ and with the analytical results.

Affiliated with

Also associated with

No associations

Rating

Giant Components in 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 Giant Components in Biased Graph Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Giant Components in Biased Graph Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-291294