Degree Distribution of Competition-Induced Preferential Attachment Graphs
| dc.creator | Berger, N. | |
| dc.creator | Borgs, C. | |
| dc.creator | Chayes, J. T. | |
| dc.creator | D'Souza, R. M. | |
| dc.creator | Kleinberg, R. D. | |
| dc.date | 2005-02-08 | |
| dc.date | 2005-02-08 | |
| dc.date.accessioned | 2026-07-07T03:03:39Z | |
| dc.date.available | 2026-07-07T03:03:39Z | |
| dc.description | 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. | |
| dc.description | 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) | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0502205 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0502205 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/25830 | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.subject | Statistical Mechanics | |
| dc.subject | Networking and Internet Architecture | |
| dc.subject | Probability | |
| dc.title | Degree Distribution of Competition-Induced Preferential Attachment Graphs | |
| dc.type | text |