Degree Distribution of Competition-Induced Preferential Attachment Graphs
<|reference_start|>Degree Distribution of Competition-Induced Preferential Attachment Graphs: 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.<|reference_end|>
@article{berger2005degree,
    title={Degree Distribution of Competition-Induced Preferential Attachment
  Graphs},
    author={N. Berger, C. Borgs, J. T. Chayes, R. M. D'Souza, R. D. Kleinberg},
    journal={arXiv preprint arXiv:cond-mat/0502205},
    year={2005},
    archivePrefix={arXiv},
    eprint={cond-mat/0502205},
    primaryClass={cond-mat.dis-nn cond-mat.stat-mech cs.NI math.PR}
}