TY - JOUR

T1 - Degree distribution of competition-induced preferential attachment graphs

AU - Berger, N.

AU - Borgs, C.

AU - Chayes, J. T.

AU - D'Souza, R. M.

AU - Kleinberg, R. D.

PY - 2005/11

Y1 - 2005/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=26644456191&partnerID=8YFLogxK

U2 - 10.1017/S0963548305006930

DO - 10.1017/S0963548305006930

M3 - Article

AN - SCOPUS:26644456191

SN - 0963-5483

VL - 14

SP - 697

EP - 721

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 5-6

ER -