Structural results for the tree builder random walk

Authors:

Abstract
We study the tree builder random walk: a randomly growing tree, built by a walker as she is walking around the tree. Namely, at each time n, she adds a leaf to her current vertex with probability pn=n−γ, γ∈(2/3,1], then moves to a uniform random neighbor on the possibly modified tree. We show that the tree process at its growth times, after a random finite number of steps, can be coupled to be identical to the Barabási–Albert preferential attachment tree model. Thus, our TBRW-model is a local dynamics giving rise to the BA-model. The coupling also implies that many properties known for the BA-model, such as diameter and degree distribution, can be directly transferred to our TBRW-model, extending previous results.

This publication has 50 references indexed in Scilit: