Growth deletion models for the Web graph and other massive networks


Changping Wang

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2


We propose new evolutionary stochastic models for the web graph and other massive networks, where edges are deleted over time and an edge is chosen to be deleted with probability inversely proportional to the in-degree of the destination. The degree distributions of graphs generated by our models follow a power law. A rigorous proof of power law degree distributions is given using martingales and concentration results. Depending on the parameters, the exponent of the power law can be any number greater than 1. For this reason, our models apply not only to the web graph, but to certain biological networks, where the power law exponent lies between 1 and 2.

Tech Report Number: 
Report Date: 
April 2, 2005
PDF icon CS-2005-03.pdf159.92 KB