Digital Access to Scholarship at Harvard (DASH) (Harvard University) · 2001 · 56 citations · 0 references
Open access
Natural SciencesComputer SystemsMathematicsInformation RetrievalProbability TheoryStatisticsDirected Acyclic GraphsGraph AlgorithmsGraph TheoryMarkov ChainsPercolation TheoryRandom WalksRandom Graph ModelsRandom Graph TheoryRandom Graphs
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