The diameter of the world wide web

The diameter of the world wide web

10 Sep 1999 | Réka Albert, Hawoong Jeong and Albert-László Barabási
The World Wide Web (www) is an unregulated, large directed graph where documents are nodes and links are edges. Its topology determines connectivity and information retrieval efficiency. Despite its vast size (over 8×10⁸ documents), it is impossible to fully map the web due to its dynamic nature. Commercial search engines index only a fraction of the web, highlighting the need for a topological model. This study uses local connectivity measurements to construct such a model, revealing that both in-degree and out-degree distributions follow power-law distributions, differing from classical random graph models. The web exhibits scale-free properties, indicating highly connected nodes and self-organized behavior. The average shortest path between two documents, ⟨d⟩, scales logarithmically with the number of documents, indicating a small-world network. For N = 8×10⁸, ⟨d⟩ ≈ 18.59, meaning any two documents are on average 19 clicks apart. This small diameter suggests that intelligent agents can efficiently navigate the web, while robots, which rely on string matching, require extensive searches. The web's scale-free nature implies collective phenomena influence its structure, necessitating new models beyond traditional random graph theories. Understanding the web's topology is crucial for improving search algorithms and information accessibility. The web's surprisingly small diameter means most information is reachable in a few clicks.The World Wide Web (www) is an unregulated, large directed graph where documents are nodes and links are edges. Its topology determines connectivity and information retrieval efficiency. Despite its vast size (over 8×10⁸ documents), it is impossible to fully map the web due to its dynamic nature. Commercial search engines index only a fraction of the web, highlighting the need for a topological model. This study uses local connectivity measurements to construct such a model, revealing that both in-degree and out-degree distributions follow power-law distributions, differing from classical random graph models. The web exhibits scale-free properties, indicating highly connected nodes and self-organized behavior. The average shortest path between two documents, ⟨d⟩, scales logarithmically with the number of documents, indicating a small-world network. For N = 8×10⁸, ⟨d⟩ ≈ 18.59, meaning any two documents are on average 19 clicks apart. This small diameter suggests that intelligent agents can efficiently navigate the web, while robots, which rely on string matching, require extensive searches. The web's scale-free nature implies collective phenomena influence its structure, necessitating new models beyond traditional random graph theories. Understanding the web's topology is crucial for improving search algorithms and information accessibility. The web's surprisingly small diameter means most information is reachable in a few clicks.
Reach us at info@study.space
[slides] Internet%3A Diameter of the World-Wide Web | StudySpace