Self-reinforced preferential attachment
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.
Fields of Study & Subjects
Complex Network Analysis Techniques
Stochastic processes and statistical mechanics
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Electronic Communications in Probability
- Volume
- 31
- Issue
- none
- Pages
- 1–14
- Publication date
- 1 January 2026