Deliverables - D04

In the first publication we proposed a "Multi-Layer" model of the Webgraph in which every new page that enters the graph is assigned with a constant number of regions it belongs to and it is allowed to link only to vertices in the same region. When deciding the end-points of the edges we adopt a combination of Copying and Evolving Network in the sub graph of the specific region. In particular, if an edge is not copied from the prototype vertex, its end-point is chosen with probability proportional to the in-degree in the existing graph. The final outcome of the stochastic process is the graph obtained by merging the edges inserted between vertices of all layers. This model shows surprising stability properties with respect to the variability of the parameters. In the second of the publications reported below we presented the first extensive comparison study of the statistical properties of large scale simulations of the most important models for the Webgraph presented so far in literature. These models are compared on several relevant observables such as in-degree, out-degree, PageRank, correlation between different measures, e.g. in-degree and Pagerank, number of small bipartite cliques. These models are also compared with a large sample of 300Ml documents and about 1 Billion edges crawled by Alexa in 2001. The analysis of this new sample has allowed discovering some new properties of the Webgraph. For instance, the out-degree does not follow a power law distribution and we can observe a much larger number of cyber-communities with respect to a 3 years older sample always collected by Alexa. This comparison study has required the development of external and semi-external algorithms for computing several graph properties and large scale simulation of stochastic graph models. This deliverable consists of the following publications