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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom