Algorithms and Experiments for the Webgraph

Abstract

In this paper we present an experimental study of the statistical and topological properties of the Webgraph. This work has required the development of a set of external and semi-external algorithms for computing properties of massive graphs, and for the large scale simulation of stochastic graph models. We use these algorithms for running experiments on a large crawl from 2001 of 200M pages and about 1.4 billion edges made available by the WebBase project at Stanford [], and on synthetic graphs obtained by the large scale simulation of stochastic graph models for the Webgraph.