Infinite limits of copying models of the web graph

Authors: 

Anthony Bonato
Jeannette Janssen

Author Addresses: 

Anthony Bonato (abonato@wlu.ca)
Dept. of Mathematics
Wilfrid Laurier University
N2L 3C5 Waterloo, ON

Jeannette Janssen (janssen@mathstat.dal.ca)
Dept. of Mathematics and Statistics
Dalhousie University
B3H 3J5 Halifax, NS

Abstract: 

Several models were proposed recently to model the dynamic evolution of the web graph. We study the infinite limits of the stochastic processes proposed to model the web graph when time goes to infinity. We prove that deterministic variations of the so-called copying model can lead to several non- isomorphic limits. Some models converge to the infinite random graph R, while the convergence of other models is sensitive to initial conditions or minor changes in the rules of the model. We explain how limits of the copying model of the web graphs share several properties of R that seem to reflect know properties of the web graph.

Tech Report Number: 
CS-2003-04
Report Date: 
April 30, 2003
AttachmentSize
PDF icon CS-2003-04.pdf338.05 KB