{
  "id": "math/0511526",
  "version": "v2",
  "published": "2005-11-21T19:08:18.000Z",
  "updated": "2008-11-26T19:48:24.000Z",
  "title": "Giant Components in Biased Graph Processes",
  "authors": [
    "Gideon Amir",
    "Ori Gurel-Gurevich",
    "Eyal Lubetzky",
    "Amit Singer"
  ],
  "comment": "31 pages, 3 figures",
  "categories": [
    "math.PR",
    "math.AP",
    "math.CO"
  ],
  "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))\\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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-11-26T19:48:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60C05"
    ],
    "keywords": [
      "giant component",
      "biased graph processes",
      "random graph process",
      "missing edges",
      "differential equations agree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 31,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math.....11526A"
    }
  }
}