Random Graphs as Models of Networks

By Mark Newman. 2002

496 citations recorded by the source corpus.

The random graph of Erdos and Renyi is one of the oldest and best studied models of a network, and possesses the considerable advantage of being exactly solvable for many of its average properties. However, as a model of real-world networks such as the Internet, social networks or biological networks it leaves a lot to be desired. In particular, it differs from real networks in two crucial ways: it lacks network clustering or transitivity, and it has an unrealistic Poissonian degree distribution. In this paper we review some recent work on generalizations of the random graph aimed at correcting these shortcomings. We describe generalized random graph models of both directed and undirected networks that incorporate arbitrary non-Poisson degree distributions, and extensions of these models that incorporate clustering too. We also describe two recent applications of random graph models to the problems of network robustness and of epidemics spreading on contact networks.

Subfields: Modeling and Simulation, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/1c6e408e6d425d9d8ab38cacb2c3ecddad02d5b2

How researchers see this paper

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

In Modeling and Simulation

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Scale-free networks in cell biology (2005, background): “, 2003), and they are similar to random graphs in terms of their local cohesiveness (Newman, 2003a).”
Network Models and Financial Stability (2007, unknown): “For many social networks, clustering coefficients are several orders of magnitude higher than would be implied by the random graph model, see Newman (2003) .”
The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-Based Implementations (2004, background): “Note that this phenomenon is well known for traditional random graphs [21].”
Symptoms of complexity in a tourism system (2007, background): “peculiar characteristics such as ( Newman, 2003a ):”
Gossip-based peer sampling (2007, background): “Note that this phenomenon is well known for traditional random graphs [Newman 2002].”
Critical phenomena in complex networks (2007, methodology): “Their degree correlated networks were generated by using the method proposed by Newman (2003d).”
Complex systems: Network thinking (2006, unknown): “Such networks were studied from a pure mathematics point of view by Erod˜os and R¶enyi [43].”
Large-scale network analysis reveals the sequence space architecture of antibody repertoires (2019, background): “In Erd ő s – Rényi (ER) random graph models, degrees follow a Poisson distribution in the limit of large numbers of nodes, while degree distributions have an exponential tail P(k) ~ e − α k in exponential networks 65 .”
CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays (2005, background): “It has also been observed that some of these overlays exhibit properties of small-world and scale-free networks [3, 4].”
Patterns of coevolving amino acids unveil structural and dynamical domains (2017, methodology): “A commonly used term of reference is a random graph, for which Crand = k̄/(N − 1), where N is the number of nodes and k̄ is the average number of neighbors per node (96).”
Social Media Mining: An Introduction (2014, background): “As a general reference, readers can refer to [Bollobás, 2001; Newman, Watts, and Strogatz, 2002; Newman, 2002b].”
Characterization of complex networks: A survey of measurements (2005, methodology): “uch stubs are selected uniformly and joined together to form an edge. When all stubs have been used up, a random graph that is a member of the ensemble of graphs with that degree sequence is obtained [51, 52, 53]. Another possibility, the rewiring method, is to start with a network (possibly a real ”
The Structure and Function of Complex Networks (2003, background): “Examples include the Internet, the World Wide Web, social networks of acquaintance or other connections between individuals, organizational networks and networks of business relations between companies, neural networks, metabolic networks, food webs, distribution networks such as blood vessels or po”