TU Graz: Course: 707.000 Web Science and Web Technology: Lecture 3: Network Theory and Terminology

Markus StrohmaierEdShare 2008

Abstract: Based on the seminal research of Broder et al. (2000), this paper explores the global topology of the World Wide Web using massive crawl data from 1999. By analyzing over 200 million pages, the study identifies a distinct "bow-tie" structure characterized by a strongly connected core and peripheral components. The findings reveal that while the web follows predictable power-law distributions for connectivity, its macroscopic shape significantly limits reachability, with a random pair of pages having only a 24% chance of being connected by a directed path.

Introduction

In the late 1990s, the rapid expansion of the World Wide Web outpaced our understanding of its global structure. Early research, often limited to small-scale experiments of a few hundred thousand pages, suggested the web was a "small world" where any two pages were separated by just a few clicks. Broder et al. sought to determine if these local observations held true at a global scale. Mapping the macroscopic structure of the web was essential for improving crawling strategies, search algorithms like PageRank, and understanding the sociology of online content creation.

Methodology

The researchers utilized the Connectivity Server 2 (CS2), a high-performance system designed to store and query linkage information in memory. They analyzed two massive crawls from the AltaVista search engine:

  • May 1999: ~203 million pages and 1.46 billion links.
  • October 1999: ~271 million pages and 2.13 billion links.

To map the web, they applied three fundamental graph algorithms at an unprecedented scale: Breadth-First Search (BFS) for reachability, Weakly Connected Components (WCC) for undirected connectivity, and Strongly Connected Components (SCC) for directed mutual reachability.

The Bow-Tie Model

The paper’s most enduring contribution is the discovery of the "Bow-Tie" model. The web is not a uniform "ball of spaghetti" but is composed of four roughly equal-sized parts:

  1. SCC (The Core): A central heart where every page can reach every other page (~28% of the web).
  2. IN: Pages that link to the SCC but cannot be reached from it (e.g., newer sites).
  3. OUT: Pages reachable from the SCC that do not link back (e.g., corporate sites with internal-only links).
  4. TENDRILS/TUBES: Pages that hang off IN or OUT, or connect them without touching the SCC.
Figure 4: Distribution of Weakly Connected Components (WCC) and Strongly Connected Components (SCC) by size.

As shown in the component distributions, while there is a massive "giant component" (the SCC), there are also many smaller, isolated clusters. This structure leads to the 24% Rule: in a directed graph like the web, reachability is surprisingly low. If you pick two random pages, there is only a 24% chance that a directed path exists between them.

Power Laws and Fractal Connectivity

The study confirmed that the web’s connectivity follows predictable power laws. The probability that a page has i in-links follows a power law proportional to $1/i^{2.1}$. Remarkably, this distribution remains consistent whether examining a single university's domain or the entire web, suggesting a "fractal" nature of digital connectivity.

Figure 1: In-degree and out-degree distributions for the web, showing consistent power-law exponents.

Resilience and Distances

Despite its fragmented appearance, the web is incredibly robust. The "weak" connectivity of the web survives even if links to high-traffic hubs are removed, indicating that the web does not rely on a few "super-hubs" to maintain its basic structure. Regarding distances, the study found:

  • The average directed path length (when one exists) is approximately 16 clicks.
  • The average undirected distance is approximately 6 clicks.
  • The diameter of the SCC is at least 28.

Conclusion

The work of Broder et al. shifted the paradigm of web research from local "small world" theories to a macroscopic "bow-tie" understanding. While the web is statistically consistent and follows power-law growth, its directed nature creates significant barriers to reachability. Future work continues to investigate how this structure evolves dynamically as the web grows into the billions of pages.

Summary updated

Abstract

In this class, we will discuss network theory fundamentals, including concepts such as diameter, distance, clustering coefficient and others. We will also discuss different types of networks, such as scale-free networks, random networks etc. 
\n
\nReadings: Graph structure in the Web, A. Broder and R. Kumar and F. Maghoul and P. Raghavan and S. Rajagopalan and R. Stata and A. Tomkins and J. Wiener Computer Networks 33 309--320 (2000) [Web link, Alternative Link] 
\nOptional: The Structure and Function of Complex Networks, M.E.J. Newman, SIAM Review 45 167--256 (2003) [Web link]
\n
\nOriginal course at: http://kmi.tugraz.at/staff/markus/courses/SS2008/707.000_web-science/
BibTeX
@inproceedings{strohmaier2008tu,
  author = {Markus Strohmaier},
  title = {{TU Graz: Course: 707.000 Web Science and Web Technology: Lecture 3: Network Theory and Terminology}},
  booktitle = {EdShare},
  year = {2008},
}
Figure