A Random-Surfer Web-Graph Model

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 at random and then performing a short random walk. We show that in certain formulations, this results in the same distribution as the preferentialattachment 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