Random models for the web graph

Changping Wang

Abstract: The overwhelming success of search engines that use a
graph-based ranking system has made the web graph a popular
subject of study. The web graph is the graph formed by the web
pages or sites as nodes, and hyperlinks as directed edges. In this
talk, I will give a brief overview of some of the experimental
data and structural properties observed in the web graph. Next I
will present the most popular random models for the web graph, and
discuss how they fit the data. Finally, I will present a new model
that applies the principle of cumulative advantage to edge
deletion as well as node and edge addition. I show that this
allows for a wider range of parameters.