A Multi-Layer Model for the Web Graph

Luigi Laura, Stefano Leonardi, Guido Caldarelli, P. De Los RiosWebDyn @ WWW 2002 · OpenReview

Introduction

Early research into the structure of the World Wide Web revealed that it is not a random network but follows a "power-law" degree distribution. This "rich-get-richer" phenomenon was successfully modeled by early frameworks like the Albert-Barabási (ABJ) model. However, these "flat" models failed to capture the Web's inherent community structure—dense local clusters and bipartite cliques that give the Web a fractal-like quality. This paper proposes a "Multi-Layer" model that simulates the Web as a collection of overlapping regions governed by independent growth processes, bridging the gap between global statistics and localized community structures.

Methodology: The Multi-Layer Model

The proposed Multi-Layer (ML) model integrates the Evolving Network model (preferential attachment) with the Copying Model. The innovation lies in its organizational hierarchy:

  1. Layer Assignment: New pages are assigned to a fixed number of "regions" or layers, representing thematic or geographic domains.
  2. Zipfian Distribution: The distribution of pages across regions follows a Zipfian curve, mirroring real-world imbalances where a few large communities coexist with many smaller ones.
  3. Localized Growth and Hybrid Linking: Pages primarily link to others within their assigned regions. Within these layers, targets are selected through a combination of copying an existing "prototype" page's links and preferential attachment to high-degree nodes.
Conceptual diagram of the Multi-Layer model showing nodes interacting within specific layers.

This structure forces links to remain within specific layers, naturally generating the dense, thematically unified clusters observed in real-world data.

Experimental Setup

To validate the ML model, the authors compared synthetic graphs against several established models and a real-world dataset:

  • NotreDame: A crawl of the nd.edu subnet (~325k nodes).
  • Baseline Models: ABJ (Albert-Barabási), ACL (Aiello-Chung-Lu), CL (Kumar's Copying Model), ER (Erdős-Rényi), and SWP (Small-World Model).

All simulations were standardized to approximately 300,000 vertices and 2.1 million edges to ensure comparative accuracy.

Key Results and Discussion

The ML model significantly outperformed traditional models in replicating the structural "fingerprint" of the NotreDame dataset.

Comparison of structural metrics across different graph models and real-world data (NotreDame).

Community Structure and Cliques

A critical finding was the model's ability to generate bipartite cliques—groups of "fans" pointing to "authorities." While the ABJ and ER models failed to produce any (3,3) or (4,3) cliques, the ML model produced counts that closely mirrored the NotreDame data, confirming that the "Copying" mechanism within layers is essential for community formation.

Clustering and Connectivity

The ML model exhibited clustering coefficients ($CC_d$ and $CC_u$) much higher than those of the ABJ or ACL models, aligning with the dense connectivity of real subnets. Furthermore, the model maintained the "Small World" property, showing a low average distance between nodes despite the layered growth constraints.

The Fractal Nature of the Web

The results support the hypothesis that the Web is fractal; it maintains structural similarity across different scales (site-level vs. global). High clustering is not a byproduct of global growth but a result of "locality of interest," where users link to content within their specific thematic layers.

Conclusion and Future Work

While the Multi-Layer model provides a more accurate representation of the Web's community structure, it remains an approximation. Future research will focus on scaling simulations to multi-million node samples and analyzing the distribution of "Strongly Connected Components" (the "bow-tie" structure). Additionally, refining the parameters for layer assignment and copying factors will be necessary to model the entirety of the World Wide Web more precisely.

Summary updated

BibTeX
@inproceedings{laura2002multi,
  author = {Luigi Laura and Stefano Leonardi and Guido Caldarelli and P. De Los Rios},
  title = {{A Multi-Layer Model for the Web Graph}},
  booktitle = {WebDyn @ WWW},
  year = {2002},
  url = {https://openreview.net/forum?id=ry-wXbZOWB},
}
Figure