Abstract
We consider a general class of preferential attachment schemes evolving by a reinforcement rule with respect to certain sublinear weights. In these schemes, which grow a random network, the sequence of degree distributions is an object of interest which sheds light on the evolving structures. In this article, we use a fluid limit approach to prove a functional law of large numbers for the degree structure in this class, starting from a variety of initial conditions. The method appears robust and applies in particular to 'non-tree' evolutions where cycles may develop in the network. A main part of the argument is to show that there is a unique nonnegative solution to an infinite system of coupled ODEs, corresponding to a rate formulation of the law of large numbers limit, through C0-semigroup/dynamical systems methods. These results also resolve a question in Chung, Handjani and Jungreis (2003).
| Original language | English (US) |
|---|---|
| Pages (from-to) | 703-731 |
| Number of pages | 29 |
| Journal | Random Structures and Algorithms |
| Volume | 48 |
| Issue number | 4 |
| DOIs | |
| State | Published - Jul 1 2016 |
Keywords
- Degree distribution
- Dynamical system
- Fluid limit
- Infinite
- Law of large numbers
- ODE
- Preferential attachment
- Random graphs
- Semigroup
- Sublinear weights
- Uniqueness
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
Fingerprint
Dive into the research topics of 'A scaling limit for the degree distribution in sublinear preferential attachment schemes'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS