A Random Graph Model for Power Law Graphs

REFERENCES

• Abello , J. , Buchsbaum , A. L. and Westbrook , J. R. 1998 . “A functional approach to external graph algorithms”. ” . In Algorithms—ESA1998 (Venice, 1998) Edited by: Bilardi , G. 332 – 343 . Berlin : Springer. . [Abello et al. 1998], Lecture Notes in Comp. Sci. 1461
   Google Scholar
• Aiello , W. , Chung , F. and Lu , L. “A random graph model for massive graphs” . Proceedings of the 32nd Annual ACM Symposium on Theory of Computing . 2000 , Portland , OR . pp. 171 – 180 . New York : ACM Press. . [Aiello et al. 2000]
   Google Scholar
• Aiello , W. , Chung , F. and Lu , L. “Random evolution of power law graphs”. ” . In Handbook of massive data sets Edited by: Abello , J. vol. 2 , [Aiello et al. ≥2001], To appear
   Google Scholar
• Albert , R. , Jeong , H. and Barabási , A. 1999 . “Diameter of the World Wide Web” . Nature , 401 September 9 [Albert et al. 1999]
   Web of Science ®Google Scholar
• Alon , N. and Spencer , J. H. 1992 . The probabilistic method New York : Wiley. . [Alon and Spencer 1992]
   Google Scholar
• Barabási , A. and Albert , R. 1999 . “Emergence of scaling in random networks” . Science , 286 October 15 [Barábasi and Albert 1999]
   Google Scholar
• Barabási , A.-L. , Albert , R. and Jeong , H. 2000 . “Scale-free characteristics of random networks: The topology of the World Wide Web” . Physica A , 281 [Barabási et al. 2000], See http://www.nd.edu/∼hjeong/./paper.html
   Google Scholar
• Erdös , P. and Rényi , A. 1960 . “On the evolution of random graphs” . Magyar Tud. Akad. Mat. Kutató Int. Közl. , 5 : 17 – 61 . [Erdös and Rényi 1960]
   Google Scholar
• Erdös , P. and Renyi , A. 1961 . “On the strength of connectedness of a random graph” . Acta Math. Acad. Sci. Hungar. , 12 : 261 – 267 . [Erdös and Renyi 1961]
   Google Scholar
• Faloutsos , M. , Faloutsos , P. and Faloutsos , C. “On power-law relationships of the internet topology” . ACM SIGCOMM 1999 Conference: applications, technologies, architectures, and protocols for computer communications . 1999 , Cambridge , MA . pp. 251 – 262 . New York : ACM Press. . [Faloutsos et al. 1999]
   Google Scholar
• Hayes , B. 2000 . “Graph theory in practice, II” . American Scientist , 88 March-April : 104 – 109 . [Hayes 2000]
   Web of Science ®Google Scholar
• Kleinberg , J. M. , Kumar , R. , Raghavan , P. , Rajagopalan , S. and Tomkins , A. S. 1999 . “The web as a graph: measurements, models, and methods”. ” . In Computing and combinatorics (Tokyo, 1999) Edited by: Asano , T. 1 – 17 . Berlin : Springer. . [Kleinberg et al. 1999], Lecture Notes in Comp. Sci. 1627
   Google Scholar
• Kumar , S. R. , Raghavan , P. , Rajagopalan , S. and Tomkins , A. “Trawling the web for emerging cyber communities” . Proceedings of the 8th World Wide Web Conference . 1999 , Toronto . Amsterdam : Elsevier. . [Kumar et al. 1999a]
   Google Scholar
• Kumar , S. R. , Raghavan , P. , Rajagopalan , S. and Tomkins , A. “Extracting large-scale knowledge bases from the web” . VLDB1999, Proceedings of 25th International Conference on Very Large Data Bases . 1999 , Edinburgh . Edited by: Atkinson , M. P. pp. 639 – 650 . San Francisco : Morgan Kaufmann. . [Kumar et al. 1999b], See http://www.informatik.uni-trier.de/-ley/db/conf/vldb/vldb99.html
   Google Scholar
• Kumar , S. R. , Raghavan , P. , Rajagopalan , S. , Sivakumar , D. , Tomkins , A. and Upfal , E. “Stochastic models for the Web graph” . Proceedings of the 41st Annual Symposium on Foundations of Computer Science . 2000 , Redondo Beach , CA . Los Alamitos , CA : IEEE. . [Kumar et al. 2001]
   Google Scholar
• Luczak , T. 1992 . “Sparse random graphs with a given degree sequence”. ” . In Random graphs (Poznań, 1989) Edited by: Frieze , A. and Luczak , T. vol. 2 , 165 – 182 . New York : Wiley. . [Luczak 1992]
   Google Scholar
• Molloy , M. and Reed , B. 1995 . “A critical point for random graphs with a given degree sequence” . Random Structures and Algorithms , 6 ( 2–3 ) : 161 – 179 . [Molloy and Reed 1995]
   Web of Science ®Google Scholar
• Molloy , M. and Reed , B. 1998 . “The size of the giant component of a random graph with a given degree sequence” . Combin. Probab. Comput. , 7 ( 3 ) : 295 – 305 . [Molloy and Reed 1998]
   Web of Science ®Google Scholar
• Wormald , N. C. 1981 . “The asymptotic connectivity of labelled regular graphs” . J. Combin. Theory Ser. B , 31 ( 2 ) : 156 – 167 . [Wormald 1981]
   Web of Science ®Google Scholar
• Wormald , N. C. 1999 . “Models of random regular graphs”. ” . In Surveys in combinatorics (Canterbury, 1999) Edited by: Lamb , J. D. and Preece , D. A. 239 – 298 . Cambridge : Cambridge Univ. Press. . [Wormald 1999], London Math. Soc. Lecture Note Series 267
   Google Scholar