Speaker: Mugizi Robert Rwebangira Time: Wednesday 12-1pm Place: NSH 1507 Title: A Random-Surfer Web-Graph Model Abstract: In this work 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.