Title: Modelling and simulation of the web graph: evaluating an exponential growth copying model

Authors: Antonios Kogias, Mara Nikolaidou, Dimosthenis Anagnostopoulos

Addresses: University of Athens, Panepistimiopolis, 15771, Athens, Greece. ' University of Athens, Panepistimiopolis, 15771, Athens, Greece. ' Harokopio University of Athens, 70 El. Venizelou Str., 17671, Athens, Greece

Abstract: Valid models of the WWW are important for creating WWW-like representations upon which new algorithms and applications for searching, indexing, compression etc. can be tested, and mostly for predicting the evolution of the web and the emergence of important new phenomena. Researchers have viewed the WWW as a graph, the so-called web graph. We present a brief review of the most typical random graph models for the web and introduce a validation process for web graph models. We evaluate the behaviour of the Exponential Growth Copying (EGC) model, which has been explicitly designed to model the WWW, and analyse the effect of individual parameters on its effectiveness through simulation modelling. Specifically, we derive the in and out degree distributions of the resulting graphs for various parameter values and measure them against the empirical analytical results from the real web (i.e. power laws for in and out degrees). Finally, we suggest appropriate values to improve EGC effectiveness and deliver a realistic model of the web graph.

Keywords: copying models; simulation; web modelling; web graph; exponential growth copying; internet.

DOI: 10.1504/IJWET.2005.007463

International Journal of Web Engineering and Technology, 2005 Vol.2 No.1, pp.29 - 49

Published online: 22 Jul 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article