Models of the web graph
Anthony Bonato
Department of Mathematics, Wilfrid Laurier U
abonato@rogers.com

One of the most widely studied real-world networks is the web graph, whose nodes represent web pages, and whose edges represent the links be- tween pages. Another well-studied real-world network consists of protein- protein interactions in a living cell. Both networks are self-organizing, as each node acts as an independent agent that bases its decision on how to link to the existing network on local knowledge. Many models for self-organizing networks are on-line: new nodes are born over time. Hence, it is natural to consider the infinite graphs that result in the limit as time tends to infinity.

We present new results on limit graphs generated by on-line random graph models. We will characterize properties of a generalized copying model via adjacency properties, and describe self-similarity properties of limit graphs generated by on-line processes. If time permits, then we will discuss a new geometric model for the web graph.

This is joint work with Peter Cameron, Dejan Delic, and Jeannette Janssen.