ALCOMFT-TR-03-120

Luigi Laura, Stefano Leonardi, Stefano Millozzi, Ulrich Meyer and Jop Sibeyn
Algorithms and Experiments for the Webgraph
Rome and MPI. Work packages 1 and 5. December 2003.

Abstract: In this paper we present an experimental study of the properties of web graphs. We study a large crawl from 2001 of 200M pages and about 1.4 billion edges made available by the WebBase project at Stanford and synthetic graphs obtained by the large scale simulation of stochastic graph models for the webgraph.

This work has required the development and the use of external and semi-external algorithms for computing properties of massive graphs, and for the large scale simulation of stochastic graph models. We report our experimental findings on the topological properties of such graphs, describe the algorithmic tools developed within this project and report the experiments on their time performance.

Postscript file: ALCOMFT-TR-03-120.ps.gz (317 kb).