The Web as a Graph: Measurements, Models, and Methods
Computing and Combinatorics, (1999)Abstract
The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating
object of study: it has several hundred million nodes today, over a billion links, and appears to grow exponentially withtime. There are many reasons — mathematical, sociological, and commercial — for studying the evolution of this graph. In thispaper we begin by describing two algorithms that operate on the Web graph, addressing problems from Web search and automaticcommunity discovery. We then report a number of measurements and properties of this graph that manifested themselves as weran these algorithms on the Web. Finally, we observe that traditional random graph models do not explain these observations,and we propose a new family of random graph models. These models point to a rich new sub-field of the study of random graphs,and raise questions about the analysis of graph algorithms on the Web.
