A random graph model for massive graphs

By William Aiello, Fan Chung Graham, Linyuan Lu. Symposium on the Theory of Computing, 2000

1,014 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/6c713899645b7bab57befbe220d4a5dc71470f0a

How researchers see this paper

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

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Statistical and Nonlinear Physics

Citations in the corpus

Resisting structural re-identification in anonymized social networks (2008, methodology): “The trend lines show the percentage of nodes whose candidate sets have sizes in the following buckets: [1] (black), [2, 4], [5, 10], [11, 20], [21,∞] (white).”
Characterization of complex networks: A survey of measurements (2005, methodology): “e is used in some results presented in Section 16.2. Due to its importance and amenability to analytical treatment, many works deal with this model, including the papers of Newman [23], Aiello et al. [55], Chung and Lu [56] and Cohen and Havlin [57]. 3.4 Scale-free Networks of Barabási and Albert Af”
Search in Power-Law Networks (2001, background): “48 a giant connected component exists [13], and all our measurements are performed on the LCC.”
Stochastic models for the Web graph (2000, methodology): “Aiello, Chung and Lu [3] describe “power-law random graphs” in which the degree sequence is given by a power-law.”
Power laws, Pareto distributions and Zipf's law (2005, background): “(e) Telephone calls: The cumulative distribution of the number of calls received on a single day by 51 million users of AT&T long distance telephone service in the United States. After Aiello et al. [ 24 ].”
E-Mail as Spectroscopy: Automated Discovery of Community Structure within Organizations (2003, background): “Given that our measured exponent is less than 3.5, we expect the graphs to consist of one giant connected component and many smaller isolated components of O(1) vertices [Aiello et al., 2000].”
A Random Graph Model for Power Law Graphs (2001, background): “An extended abstract of this paper has appeared in the Proceedings of the Thirtysecond Annual ACM Symposium on Theory of Computing 2000 [Aiello et al. 2000].”
The Structure and Function of Complex Networks (2003, background): “More recently, power-law degree distributions have been observed in a host of other networks, including notably other citation networks [351, 364], the World Wide Web [14, 34, 74], the Internet [86, 148, 401], metabolic networks [212, 214], telephone call graphs [8, 9], and the network of human sexu”
A Brief History of Generative Models for Power Law and Lognormal Distributions (2004, background): “) are now pervasive in computer science; see, for example, [1, 8, 7, 9, 16, 19, 21, 22, 24, 25, 27, 28, 33, 34, 40, 41, 43, 45, 47, 50, 61, 69].”
Evolution of networks (2001, background): “D (1982±June 1997) [100]; 5a is the ® exponent for the collaboration network of movie actors [55]; 5a 0 is the result of another ®tting for the same data [102]; 5b is ® for the collaboration network of Medline [13]; 5b 0 is ® for the collaboration net collected from mathematical journals [15]; 5b 00”
Graph structure in the Web (2000, neutral): “[3].”
Connected Components in Random Graphs with Given Expected Degree Sequences (2002, methodology): “It has been observed that many real graphs occurring in the Internet, social sciences, computational biology and nature have degrees obeying a power law [1] [2] [3] [7] [8] [12] [13] [20] [21] [25] [26] [36].”
The Power Grid as a Complex Network: a Survey (2011, background): “…has been used in many diﬀerent ﬁelds of knowledge, from biology [7] to chemistry [8], from linguistics to social sciences [9], from telephone call patterns [10] to computer networks [11] and web [12, 13] to virus spreading [14, 15, 16] to logistics [17, 18, 19] and also inter-banking systems [20].”
The origin of power laws in Internet topologies revisited (2002, background): “Several recent papers in the physics and biology literature have attempted to uncover the mechanisms that cause massive graphs such as Web linkage [18], telephone call [19], or biblio-”
Power-Law Distributions in Empirical Data (2007, background): “) (e) The number of calls received by customers of AT&T’s long distance telephone service in the United States during a single day [1, 5].”
Power laws and the AS-level internet topology (2003, background): “not attempt to emulate the process that leads to a power law [1], [26], [42].”