World Wide Web: A Graph-Theoretic Perspective
Narsingh Deo, Pankaj Gupta · 2001
The World Wide Web can be modeled as a directed graph in which a node represents a Web page and an edge represents a hyperlink. Currently, the number of nodes in this gigantic Web graph is estimated to be over four billion, and is growing at more than seven million nodes a day ⎯ without any centralized control. Recent studies suggest that despite its chaotic appearance, the Web is a highly structured digraph, in a statistical sense. The study of this graph can provide insight into Web algorithms for crawling, searching, and ranking Web resources. Knowledge of the graph-theoretic structure of the Web graph can be exploited for attaining efficiency and comprehensiveness in Web navigation as well as enhancing Web tools, e.g., better search engines and intelligent agents. In this proposal, we discuss various problems to be explored for understanding the structure of the WWW. Many research directions are identified such as Web caching, prevention of