11
Apr
Title : Analysis of the Random-Surfer Web-Graph model
Speaker : Pall Melsted
When : 4:30-5:30pm, April 12th
Where : Physical Plant Building(PPB) Room #300
Abstract:
We analyze the Random-Surfer Web-Graph Model introduced by Blum et al. In this model a new vertex picks a random vertex, performs a short random walk and connects to the end of the walk. We give the expected degree of a vertex and show that it follows a power law for early vertices thus showing a First Mover Advantage in the graph. We also show that for certain values of the parameters the first vertex will be connected to a considerable fraction of the vertices and give evidence of a phase transition for this behavior.
This is joint work with Prasad Chebolu.
