A scaling limit for the degree distribution in sublinear preferential attachment schemes1. Issue 4 (28th November 2015)

• Record Type: Journal Article
• Authors: Choi, Jihyeok; Sethuraman, Sunder; Venkataramani, Shankar C.
• Is Part Of: Random structures & algorithms. Volume 48:Issue 4(2016)
• Page Start: 703
• Page End: 731
• Publication Date: 2015-11-28
• Subjects: preferential attachment -- random graphs -- degree distribution -- fluid limit -- law of large numbers -- sublinear weights -- dynamical system -- semigroup -- infinite -- ODE -- uniqueness; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20615
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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