Random graphs as models of networks
arXiv:cond-mat/0202208
Abstract
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.
35 pages, 6 figures
Cited by in corpus (40)
- The structure and function of complex networks
- Characterization of complex networks: A survey of measurements
- Critical phenomena in complex networks
- Why social networks are different from other types of networks
- Epidemic spreading in complex networks with degree correlations
- Second look at the spread of epidemics on networks
- Subgraphs in random networks
- Biased random walks on complex networks: the role of local navigation rules
- Compact Routing on Internet-Like Graphs
- Evolving Clustered Random Networks
- Network-based analysis of stochastic SIR epidemic models with random and proportionate mixing
- Organization of modular networks
- Network science: a review focused on tourism
- A Gap in the Community-Size Distribution of a Large-Scale Social Networking Site
- Mutually cooperative epidemics on power-law networks
- Exact and approximate formulas for contact tracing on random trees
- On Quantum Gravity If Non-Locality Is Fundamental
- Random Spatial Network Models with Core-Periphery Structure
- Asymptotic Equipartition Properties for simple hierarchical and networked structures
- On Reliability of Stochastic Networks
- The Cost of an Epidemic over a Complex Network: A Random Matrix Approach
- On the role of the plasmodial cytoskeleton in facilitating intelligent behaviour in slime mould Physarum polycephalum
- Improving Network Inference: The Impact of False Positive and False Negative Conclusions about the Presence or Absence of Links
- Lossy Asymptotic Equipartition property for Networked Data Structures
- Generating Hierarchically Modular Networks via Link Switching
- Exponential Approximation, Method of types for Empirical Neighbourhood Measures of Random graphs by Random Allocation
- Properties of Latent Variable Network Models
- DeepNC: Deep Generative Network Completion
- Default contagion risks in Russian interbank market
- Recovery and Analysis of Architecture Descriptions using Centrality Measures
- On the Degree Distribution of Faulty Peer-to-Peer Overlays
- Effect of Degree Distribution on Evolutionary Search
- Asymptotics of the partition function of Ising model on inhomogeneous random graphs
- Scale- free networks in cell biology
- Large deviations, Basic information theorem for fitness preferential attachment random networks
- Interplay between Network Topology and Dynamics in Neural Systems
- Reinventing the Triangles: Rule of Thumb for Assessing Detectability
- Symptoms of complexity in a tourism system
- Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks
- Extended Scale-Free Networks