SCIENCE@home

Degree Distribution of Competition-Induced Preferential Attachment Graphs

Noam Berger,C. Borgs,J. Chayes,Raissa M. D’Souza,Robert D. Kleinberg

Published 2005 in Combinatorics, probability & computing

ABSTRACT

We introduce a family of one-dimensional geometric growth models, constructed iteratively by locally optimizing the trade-offs between two competing metrics, and show that this family is equivalent to a family of preferential attachment random graph models with upper cut-offs. 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 analyse a generalized version of our graph process, with two natural parameters, one corresponding to the cut-off and the other a ‘fertility’ parameter. We prove that the general model has a power-law degree distribution up to a cut-off, 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 cut-off and the uniform attachment model.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-22 of 22 references · Page 1 of 1

CITED BY

Showing 1-29 of 29 citing papers · Page 1 of 1