Variations on Random Graph Models for the Web

Eleni Drinea, Mihaela Enachescu, Michael Mitzenmacher

Digital Access to Scholarship at Harvard (DASH) (Harvard University) · 2001 · 56 citations · 0 references

Full text

Open access

Concepts

Abstract

this paper, we introduce variations on random graph models for Web-like graphs. As a basis, we recall a model rst presented in [5]. We add vertices to the graph, one per unit time, with each vertex having one outedge. With probability this outedge loops back to the new vertex and with probability 1 the end is chosen to be the same as the end of a random extant edge. Notice that in this second case the end of a new edge is chosen proportionally to the current indegrees of the vertices. One feature of these graphs that makes them Web-like is that the indegrees obey a power law; that is, the fraction of vertices of degree i grows like 1=i , where in this case = 1=(1 ). Model 1: We grow a graph to n vertices, at a rate of one vertex per unit of time. (We may begin initially with t 0 vertices in a dir