A random graph model for massive graphs

William Aiello, Fan Chung, Linyuan Lü · Symposium on the Theory of Computing · 2000

Summary

A random graph model is proposed which is a special case of sparse random graphs with given degree sequences which involves only a small number of parameters, called logsize and log-log growth rate, which capture some universal characteristics of massive graphs.

Type: article
Published: 2000-05-01
Cited by: 1,013
References: 25
Access: Open access
DOI: https://doi.org/10.1145/335305.335326
OpenAlex: https://openalex.org/W2097147952
Semantic Scholar: https://api.semanticscholar.org/CorpusID:2993917

Keywords

Citation, Computer science, Graph, Random graph, World Wide Web

References

A Functional Approach to External Graph AlgorithmsAbello, Buchsbaum, Westbrook — 1998
On power-law relationships of the Internet topologyMichalis Faloutsos, Petros Faloutsos, Christos Faloutsos — 1999
On the evolution of random graphsBéla Bollobás — 1984
A personal communicationMicheál Jacob — 1989
The asymptotic connectivity of labelled regular graphsNicholas Wormald — 1981
A Critical Point for Random Graphs with a Given Degree SequenceMichael Molloy, Bruce Reed — 1995
The Probabilistic MethodJoel Spencer — 1992
Scale-free characteristics of random networks: the topology of the world-wide webAlbert-Ĺaszló Barabási, Réka Albert, Hawoong Jeong — 2000
The Size of the Giant Component of a Random Graph with a Given Degree SequenceMichael Molloy, Bruce Reed — 1998
Extracting Large-Scale Knowledge Bases from the WebRavi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan — 1999
Trawling the Web for Emerging Cyber-CommunitiesRavi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan — 1999
Internet: Diameter of the World-Wide WebRéka Albert, Hawoong Jeong, Albert-Ĺaszló Barabási — 1999
On the Evolution of Random GraphsP. Erd6s, A. R~nyi
The Web as a Graph: Measurements, Models, and MethodsJ. Kleinberg, Ravi Kumar, P. Raghavan — 1999
Emergence of Scaling in Random NetworksB. McInnes, Jannene S. McBride, N. Evans — 1999
Emergence of Scaling in Random NetworksJannene S. McBride, N. Evans, David D. Lambert
ON THE STRENGTH OF CONNECTEDNESS OF A RANDOM GRAPHP. ERDbS — 2001

Cited by

An adaptive randomised structured search network for locating objects in a distributed computing systemJia-bin Li, C. Fung, D. Myers — 2007
Fast generation of dynamic complex networks with underlying hyperbolic geometryMoritz von Looz, Christian Staudt, Henning Meyerhenke — 2015
FISH: A Novel Peer-to-Peer Overlay Network Based on Hyper-deBruijnYe Yuan, Guoren Wang, Yongjiao Sun — 2010
A Fast Community Based Algorithm for Generating Web Crawler Seeds SetShervin Daneshpajouh, Mojtaba Nasiri, Mohammad Ghodsi — 2016
Security Analysis on Network Systems Based on Some Stochastic ModelsXiaohu Li — 2014
Случайные графы, модели и генераторы безмасштабных графовМ. М. Берновски, Н. Н. Кузюрин — 2012
Etude de la robustesse des graphes sociaux émergents. (Study of the robustness of emerging social graphs)Slimane Lemmouchi — 2012
Power Laws in Object Oriented Systems ArchitecturesNicola Serra — 2005
Culture and generalized inattentional blindnessRodrick Wallace — 2006
Epidemic Spreading in Technological NetworksJasmin Léveillé — 2002
Institutional paraconsciousness and its pathologiesRodrick Wallace — 2006
Tools for large graph miningDeepayan Chakrabarti, Christos Faloutsos — 2005
Power-laws and spectral analysis of the Internet topologyLaxmi Subedi — 2010
A Random-Surfer Web-Graph ModelAvrim Blum, T-H. Hubert Chan, Mugizi Robert Rwebangira — 2006
Entering the blackboard jungle: canonical dysfunction in conscious machinesRodrick Wallace — 2005
Markov Model of Biological NetworksCaifeng Du, Fuzhou Gong — 2009
Social Network Structures and Their Impact on Multi-Agent System DynamicsMatthew E. Gaston, Marie desJardins — 2005
Biologically inspired distributed machine cognition: a new formal approach to hyperparallel computationRodrick Wallace — 2007
Context-addressed communication dispatchAlisa Devlić — 2009
Traffic Analysis of a Mobile Communication System Based on a Scale-Free User NetworkWai M. Tam, Francis C. M. Lau, Yuanjun Xia — 2005

A random graph model for massive graphs

Summary

Keywords

References

Cited by

Related papers