Premium
A scaling limit for the degree distribution in sublinear preferential attachment schemes
Author(s) -
Choi Jihyeok,
Sethuraman Sunder,
Venkataramani Shankar C.
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20615
Subject(s) - sublinear function , preferential attachment , degree (music) , limit (mathematics) , mathematics , scaling limit , sequence (biology) , class (philosophy) , scaling , tree (set theory) , variety (cybernetics) , semigroup , random graph , statistical physics , ode , discrete mathematics , complex network , combinatorics , computer science , mathematical analysis , statistics , physics , geometry , genetics , artificial intelligence , biology , acoustics , graph
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 C 0 ‐semigroup/dynamical systems methods. These results also resolve a question in Chung, Handjani and Jungreis (2003). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 703–731, 2016