TY - JOUR

T1 - Connectivity transitions in networks with super-linear preferential attachment

AU - Oliveira, Roberto

AU - Spencer, Joel

N1 - Funding Information:
Acknowledgments. We thank Eleni Drinea and Michael Mitzenmacher for bringing this problem to our attention and for useful discussions. We also thank the anonymous referees for pointing out several typos and making suggestions that greatly improved our presentation. Work for this paper was done while the first author was a PhD student at the Courant Institute, New York University, supported by a fellowship from CNPq, Brazil.
Publisher Copyright:
© A K Peters, Ltd.

PY - 2005/1/1

Y1 - 2005/1/1

N2 - We analyze an evolving network model of Krapivsky and Redner in which new nodes arrive sequentially, each connecting to a previously existing node b with probability proportional to the pth power of the in-degree of b. We restrict to the super-linear case p > 1. When (Formula presented), the structure of the final countable tree is determined. There is a finite tree T with distinguished v (which has a limiting distribution) on which is “glued” a specific infinite tree; v has an infinite number of children, an infinite number of which have k − 1 children, and there are only a finite number of nodes (possibly only v) with k or more children. Our basic technique is to embed the discrete process in a continuous time process using exponential random variables, a technique that has previously been employed in the study of balls-in-bins processes with feedback.

AB - We analyze an evolving network model of Krapivsky and Redner in which new nodes arrive sequentially, each connecting to a previously existing node b with probability proportional to the pth power of the in-degree of b. We restrict to the super-linear case p > 1. When (Formula presented), the structure of the final countable tree is determined. There is a finite tree T with distinguished v (which has a limiting distribution) on which is “glued” a specific infinite tree; v has an infinite number of children, an infinite number of which have k − 1 children, and there are only a finite number of nodes (possibly only v) with k or more children. Our basic technique is to embed the discrete process in a continuous time process using exponential random variables, a technique that has previously been employed in the study of balls-in-bins processes with feedback.

UR - http://www.scopus.com/inward/record.url?scp=50249104858&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=50249104858&partnerID=8YFLogxK

U2 - 10.1080/15427951.2005.10129101

DO - 10.1080/15427951.2005.10129101

M3 - Article

AN - SCOPUS:50249104858

VL - 2

SP - 121

EP - 163

JO - Internet Mathematics

JF - Internet Mathematics

SN - 1542-7951

IS - 2

ER -