Random graph models for the web graph

The Web may be viewed as a directed graph each of whose vertices is a static HTML Web page, and each of whose edges corresponds to a hyperlink from one Web page to another. We propose and analyze random graph models inspired by a series of empirical observations on the Web. Our graph models differ from the traditional G/sub n, p/ models in two ways: 1. Independently chosen edges do not result in the statistics (degree distributions, clique multitudes) observed on the Web. Thus, edges in our model are statistically dependent on each other. 2. Our model introduces new vertices in the graph as time evolves. This captures the fact that the Web is changing with time. Our results are two fold: we show that graphs generated using our model exhibit the statistics observed on the Web graph, and additionally, that natural graph models proposed earlier do not exhibit them. This remains true even when these earlier models are generalized to account for the arrival of vertices over time. In particular, the sparse random graphs in our models exhibit properties that do not arise in far denser random graphs generated by Erdos-Renyi models.

Authors

• Ravi Kumar 0001
• Prabhakar Raghavan
• Sridhar Rajagopalan
• D. Sivakumar 0001
• Andrew Tomkins
• Eli Upfal

Keywords

• Stochastic processes
• Web pages
• HTML
• Statistics
• Computer science
• Couplings
• Predictive models
• Web Graph
• Web Page
• Graphical Model
• Directed Graph
• Degree Distribution
• Vertices
• Random Graph
• Sparse Graph
• Random Graph Models
• Exponential Growth
• Random Variables
• Upper Bound
• Error Probability
• Linear Growth
• Linear Case
• Vertex Degree
• Branching Process
• Degree Sequence
• Linear Growth Model