Stochastic models for the Web graph

By Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, Eli Upfal. Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000

746 citations recorded by the source corpus.

Subfields: Information Systems, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/fb3ddb504c4f6d3e4dc110349578b6496e4a7d50

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

The Structure and Function of Complex Networks (2003, background): “3), as well as a variety of other interesting properties [2, 14, 74, 158, 240, 253].”
Graph mining: Laws, generators, and algorithms (2006, neutral): “For the model of Kumar et al. [1999], both the in-degree and out-degree distributions follow power laws”
Graph evolution: Densification and shrinking diameters (2006, background): “…models based on preferential attachment [Albert and Barabasi 1999; Abello et al. 2002; Cooper and Frieze 2003], copying model [Kleinberg et al. 1999; Kumar et al. 2000], and the related growing network with redirection model [Krapivsky and Redner 2001], which produces graphs with constant…”
Directed scale-free graphs (2003, background): “Here we propose a very natural model of directed web graphs andshow that it gives power laws consistent with those that have been observed in the world-wide web.”
A Survey of Statistical Network Models (2009, methodology): “[185] is on deriving results about topological properties of duplication-attachment graphs, described as functions of the two parameters (α, d).”
Microscopic evolution of social networks (2008, background): “The copying [14] and the preferential attachment [1] models belong to this category.”
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. (2000, methodology): “Prof-itable use has been made of a variety of physical modeling techniques [4,5,6], exact solutions [7,8,9,10,11,12], Monte Carlo simulation [13,14,15,16], scaling and renormalization group methods [14,15,16], mean-ﬁeld theory [17,18], percolation theory [19,20,21], the replica method [22],…”
Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet (2002, background): “That is, if the growth of individuals in a population follows a stochastic process that is independent of the individual’s size (so that larger individuals attract more growth), then a power law will result (see, from among dozens of examples, [6] for an elegant argument in the domain of city popula”
What's new on the web?: the evolution of the web from a search engine perspective (2004, background): “Although there has been a rich body of theoretical work on Web growth models, e.g., [12, 14, 20 ] to the best of our knowledge, our work is the first to study the evolution of Web link structure experimentally.”
Distances in Random Graphs with Finite Mean and Infinite Variance Degrees (2005, neutral): “See [2, 3, 4, 7, 8, 9, 10, 11, 15, 26] and the references therein.”
Social Network Analysis and Mining for Business Applications (2011, neutral): “The copy-model [Kumar et al. 2000] states that a new node that connects to a network selects some nodes to which to connect by the preferential attachment rule, but also picks an existing node at random and “copies” some of its out-links.”
Self-similarity in the web (2001, background): “Furthermore, if the web is decomposed into these cohesive collections, for a wide range of deﬁnitions of “cohesive,” the resulting collections are tightly and robustly connected via a navigational backbone that affords strong connectivity between the collections.”
A Random Graph Model for Power Law Graphs (2001, background): “The authors of [12, 14] will offer a partial analysis in a recent paper [15].”
Evolution of social-attribute networks: measurements, modeling, and implications using google+ (2012, methodology): “Our model includes two new components, i.e., attribute-augmented preferential attachment and attribute-augmented triangle-closing , which extend the classical preferential attachment [5, 27] and triangle-closing [29, 43, 53, 2], respectively.”
Supervised random walks: predicting and recommending links in social networks (2010, methodology): “We generate scale-free graphs G on 10,000 nodes by using the Copying model [18]: Graph starts with three nodes connected in a triad.”
Bipartite Graphs as Models of Complex Networks (2003, neutral): “[3, 27, 37].”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “, preferential attachment models [127], copying models [102], hierarchical models [138], etc.”