Self-reinforced preferential attachment

Electronic Communications in Probability, vol. 31, pp. 1–14

Abstract

We consider a preferential attachment random graph with self-reinforcement. Each time a new vertex comes in, it attaches itself to an old vertex with a probability that is proportional to the sum of the degrees of that old vertex at all prior times. The resulting growing graph is a random tree whose vertices have degrees that grow polynomially fast in time. We compute the growth exponent, show that it is strictly larger than the growth exponent in the absence of self-reinforcement, and develop insight into how the self-reinforcement affects the growth. Proofs are based on a stochastic approximation scheme.

Authors 2

1. Yogesh Dahiya

   Indian Institute of Science Education and Research Mohali

   Affiliation as printed

   Department of Mathematical Sciences, IISER Mohali, Knowledge City, Sector 81, Manauli, PO, Sahibzada Ajit Singh Nagar, Punjab, 140306, India

2. Frank den Hollander Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Mathematical Institute, Leiden University, Einsteinweg 55, 2333 CC Leiden, The Netherlands