Large deviations for the degree structure in preferential attachment schemes
arXiv:1105.6047 · doi:10.1214/12-AAP854
Abstract
Preferential attachment schemes, where the selection mechanism is linear and possibly time-dependent, are considered, and an infinite-dimensional large deviation principle for the sample path evolution of the empirical degree distribution is found by Dupuis-Ellis-type methods. Interestingly, the rate function, which can be evaluated, contains a term which accounts for the cost of assigning a fraction of the total degree to an "infinite" degree component, that is, when an atypical "condensation" effect occurs with respect to the degree structure. As a consequence of the large deviation results, a sample path a.s. law of large numbers for the degree distribution is deduced in terms of a coupled system of ODEs from which power law bounds for the limiting degree distribution are given. However, by analyzing the rate function, one can see that the process can deviate to a variety of atypical nonpower law distributions with finite cost, including distributions typically associated with sub and superlinear selection models.
arXiv commentPublished in at http://dx.doi.org/10.1214/12-AAP854 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (14)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- The architecture of complex weighted networks
- Organization of Growing Random Networks
- Evolution of reference networks with aging
- Degree Distributions of Growing Networks
- Scaling properties of scale-free evolving networks: Continuous approach
- Scale-free network growth by ranking
- Finiteness and Fluctuations in Growing Networks
- Re-inventing Willis
- Transition from small to large world in growing networks
- Multigraph limit of the dense configuration model and the preferential attachment graph
- Large deviations for the leaves in some random trees