Answers are grounded in this paper and cite their sources.
In this paper we provide theoretical and experimental results on a random-surfer model for construction of a random graph. In this model, a new node connects to the existing graph by choosing a start node uniformly at random and then performing a short random walk. We show that in certain formulations, this results in the same distribution as the preferential-attachment random-graph model, and in others we give a direct analysis of power-law distribution of degrees or “virtual degrees” of the resulting graphs. We also present experimental results for a number of settings of parameters that we are not able to analyze mathematically.
No takes yet. Share an insight, caveat, or question.
Blum et al. (2006) studied this question.