{
  "id": "cond-mat/0502205",
  "version": "v2",
  "published": "2005-02-08T20:59:03.000Z",
  "updated": "2005-02-08T21:10:34.000Z",
  "title": "Degree Distribution of Competition-Induced Preferential Attachment Graphs",
  "authors": [
    "N. Berger",
    "C. Borgs",
    "J. T. Chayes",
    "R. M. D'Souza",
    "R. D. Kleinberg"
  ],
  "comment": "24 pages, one figure. To appear in the journal: Combinatorics, Probability and Computing. Note, this is a long version, with complete proofs, of the paper \"Competition-Induced Preferential Attachment\" (cond-mat/0402268)",
  "categories": [
    "cond-mat.dis-nn",
    "cond-mat.stat-mech",
    "cs.NI",
    "math.PR"
  ],
  "abstract": "We introduce a family of one-dimensional geometric growth models, constructed iteratively by locally optimizing the tradeoffs between two competing metrics, and show that this family is equivalent to a family of preferential attachment random graph models with upper cutoffs. This is the first explanation of how preferential attachment can arise from a more basic underlying mechanism of local competition. We rigorously determine the degree distribution for the family of random graph models, showing that it obeys a power law up to a finite threshold and decays exponentially above this threshold. We also rigorously analyze a generalized version of our graph process, with two natural parameters, one corresponding to the cutoff and the other a ``fertility'' parameter. We prove that the general model has a power-law degree distribution up to a cutoff, and establish monotonicity of the power as a function of the two parameters. Limiting cases of the general model include the standard preferential attachment model without cutoff and the uniform attachment model.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-02-08T21:10:34.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "competition-induced preferential attachment graphs",
      "degree distribution",
      "preferential attachment random graph models",
      "standard preferential attachment model",
      "one-dimensional geometric growth models"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005cond.mat..2205B"
    }
  }
}