ID: cond-mat/0202208

Random graphs as models of networks

February 12, 2002

View on ArXiv
M. E. J. Newman
Condensed Matter
Statistical Mechanics
Disordered Systems and Neura...

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.

Similar papers 1

Networks, Random Graphs and Percolation

September 8, 2014

93% Match
Philippe Deprez, Mario V. Wüthrich
Probability

The theory of random graphs goes back to the late 1950s when Paul Erd\H{o}s and Alfr\'ed R\'enyi introduced the Erd\H{o}s-R\'enyi random graph. Since then many models have been developed, and the study of random graph models has become popular for real-life network modelling such as social networks and financial networks. The aim of this overview is to review relevant random graph models for real-life network modelling. Therefore, we analyse their properties in terms of styli...

Find SimilarView on arXiv

Random graphs with arbitrary degree distributions and their applications

July 13, 2000

91% Match
M. E. J. Newman, S. H. Strogatz, D. J. Watts
Statistical Mechanics
Disordered Systems and Neura...

Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results...

Find SimilarView on arXiv

Random Networks with Tunable Degree Distribution and Clustering

May 17, 2004

91% Match
Erik Volz
Statistical Mechanics
Disordered Systems and Neura...

We present an algorithm for generating random networks with arbitrary degree distribution and Clustering (frequency of triadic closure). We use this algorithm to generate networks with exponential, power law, and poisson degree distributions with variable levels of clustering. Such networks may be used as models of social networks and as a testable null hypothesis about network structure. Finally, we explore the effects of clustering on the point of the phase transition where...

Find SimilarView on arXiv

Modelling Epidemics on Networks

November 21, 2011

90% Match
Thomas House
Popular Physics
Populations and Evolution

Infectious disease remains, despite centuries of work to control and mitigate its effects, a major problem facing humanity. This paper reviews the mathematical modelling of infectious disease epidemics on networks, starting from the simplest Erdos-Renyi random graphs, and building up structure in the form of correlations, heterogeneity and preference, paying particular attention to the links between random graph theory, percolation and dynamical systems representing transmiss...

Find SimilarView on arXiv

Bipartite Graphs as Models of Complex Networks

July 4, 2003

90% Match
Jean-Loup Guillaume, Matthieu Latapy
Statistical Mechanics

It appeared recently that the classical random graph model used to represent real-world complex networks does not capture their main properties. Since then, various attempts have been made to provide accurate models. We study here a model which achieves the following challenges: it produces graphs which have the three main wanted properties (clustering, degree distribution, average distance), it is based on some real-world observations, and it is sufficiently simple to make i...

Find SimilarView on arXiv

Random graphs with clustering

March 24, 2009

90% Match
M. E. J. Newman
Statistical Mechanics
Disordered Systems and Neura...
Physics and Society

We offer a solution to a long-standing problem in the physics of networks, the creation of a plausible, solvable model of a network that displays clustering or transitivity -- the propensity for two neighbors of a network node also to be neighbors of one another. We show how standard random graph models can be generalized to incorporate clustering and give exact solutions for various properties of the resulting networks, including sizes of network components, size of the gian...

Find SimilarView on arXiv

Random Geometric Graph: Some recent developments and perspectives

March 29, 2022

90% Match
Quentin LAMA Duchemin, Castro Yohann ICJ de
Social and Information Netwo...
Statistics Theory
Statistics Theory

The Random Geometric Graph (RGG) is a random graph model for network data with an underlying spatial representation. Geometry endows RGGs with a rich dependence structure and often leads to desirable properties of real-world networks such as the small-world phenomenon and clustering. Originally introduced to model wireless communication networks, RGGs are now very popular with applications ranging from network user profiling to protein-protein interactions in biology. RGGs ar...

Find SimilarView on arXiv

Statistical mechanics of random graphs

December 18, 2003

90% Match
Zdzislaw Burda, Jerzy Jurkiewicz, Andre Krzywicki
Statistical Mechanics

We discuss various aspects of the statistical formulation of the theory of random graphs, with emphasis on results obtained in a series of our recent publications.

Find SimilarView on arXiv

Random graph models for dynamic networks

July 26, 2016

89% Match
Xiao Zhang, Cristopher Moore, M. E. J. Newman
Social and Information Netwo...
Physics and Society

We propose generalizations of a number of standard network models, including the classic random graph, the configuration model, and the stochastic block model, to the case of time-varying networks. We assume that the presence and absence of edges are governed by continuous-time Markov processes with rate parameters that can depend on properties of the nodes. In addition to computing equilibrium properties of these models, we demonstrate their use in data analysis and statisti...

Find SimilarView on arXiv

Recent Advances in Scalable Network Generation

March 2, 2020

89% Match
Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, ... , Schulz Christian
Data Structures and Algorith...
Social and Information Netwo...

Random graph models are frequently used as a controllable and versatile data source for experimental campaigns in various research fields. Generating such data-sets at scale is a non-trivial task as it requires design decisions typically spanning multiple areas of expertise. Challenges begin with the identification of relevant domain-specific network features, continue with the question of how to compile such features into a tractable model, and culminate in algorithmic detai...

Find SimilarView on arXiv