The phase transition in inhomogeneous random graphs

Abstract

We introduce a very general model of an inhomogenous random graph with independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p=c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied. We show that under one very weak assumption (that the expected number of edges is `what it should be'), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is `stable': for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n).

135 pages; revised and expanded slightly. To appear in Random Structures and Algorithms

References in corpus (2)

• Generating simple random graphs with prescribed degree distribution
• Random Graph Models with Hidden Color

Cited by in corpus (131)

• Spectral redemption: clustering sparse networks
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Latent Space Models for Dynamic Networks
• Sparse graphs using exchangeable random measures
• Conjoining Speeds up Information Diffusion in Overlaying Social-Physical Networks
• Scale-free Networks Well Done
• Placing Dynamic Content in Caches with Small Population
• The method of moments and degree distributions for network models
• Bayesian stochastic blockmodeling
• Critical random graphs: Diameter and mixing time
• Diameters in preferential attachment models
• Percolation on dense graph sequences
• Random graph models for directed acyclic networks
• Information-theoretic thresholds from the cavity method
• Multifractal Network Generator
• Epidemics on random intersection graphs
• Random networks with sublinear preferential attachment: The giant component
• The k-core and branching processes
• Anomaly Detection in Time Series of Graphs using Fusion of Graph Invariants
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• The largest component in a subcritical random graph with a power law degree distribution
• Subsampling bootstrap of count features of networks
• Universally consistent vertex classification for latent positions graphs
• Novel scaling limits for critical inhomogeneous random graphs
• Ising models on power-law random graphs
• Bootstrap percolation in inhomogeneous random graphs
• A preferential attachment model with random initial degrees
• Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations
• The diameter of sparse random graphs
• Edge-based compartmental modeling for epidemic spread Part II: Model Selection and Hierarchies
• Typology of phase transitions in Bayesian inference problems
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Sparse random graphs with clustering
• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Small worlds and clustering in spatial networks
• An old approach to the giant component problem
• Distance distribution in configuration model networks
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Zero-one laws for connectivity in inhomogeneous random key graphs
• Graphon Filters: Graph Signal Processing in the Limit
• Local clustering in scale-free networks with hidden variables
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• Generating hierarchial scale free graphs from fractals
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• The distribution of shortest path lengths in a class of node duplication network models
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Bridging the gap between graphs and networks
• Growing networks with preferential addition and deletion of edges
• Variational Bayes model averaging for graphon functions and motif frequencies inference in W-graph models
• Ising critical behavior of inhomogeneous Curie-Weiss models and annealed random graphs
• Clustering Spectrum of scale-free networks
• On edge exchangeable random graphs
• The diameter of weighted random graphs
• A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit
• Phase transitions for modified Erdös-Rényi processes
• Clique percolation
• Detecting hyperbolic geometry in networks: why triangles are not enough
• A Graphon Approach to Limiting Spectral Distributions of Wigner-type Matrices
• Long-range percolation on the hierarchical lattice
• The evolution of subcritical Achlioptas processes
• The cut metric, random graphs, and branching processes
• The structure of typical clusters in large sparse random configurations
• A large-deviations principle for all the cluster sizes of a sparse Erdős-Rényi graph
• Large deviation principles for empirical measures of colored random graphs
• First Passage Percolation on Inhomogeneous Random Graphs
• Weighted hypersoft configuration model
• Random Simplicial Complexes: Models and Phenomena
• A modified bootstrap percolation on a random graph coupled with a lattice
• Spread-out percolation in R^d
• Dynamic Hidden-Variable Network Models
• On sparsity, power-law and clustering properties of graphex processes
• Line-of-sight percolation
• Multiscale network renormalization: scale-invariance without geometry
• A dynamic network in a dynamic population: asymptotic properties
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Percolation in invariant Poisson graphs with i.i.d. degrees
• Bounded-size rules: The barely subcritical regime
• A limit theorem for small cliques in inhomogeneous random graphs
• Atomic subgraphs and the statistical mechanics of networks
• Cliques in dense inhomogeneous random graphs
• The interpolation method for random graphs with prescribed degrees
• The local limit of the uniform spanning tree on dense graphs
• On rate of convergence to the Poisson law of the number of cycles in the generalized random graphs
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• Linear embeddings of graphs and graph limits
• Scaling of the clustering function in spatial inhomogeneous random graphs
• Non Parametric Statistics of Dynamic Networks with distinguishable nodes
• Rotated multifractal network generator
• SIR-Model for Households
• Duality in inhomogeneous random graphs, and the cut metric
• A moment-generating formula for Erdős-Rényi component sizes
• Large deviations for the annealed Ising model on inhomogeneous random graphs: spins and degrees
• Convergence of Achlioptas processes via differential equations with unique solutions
• Understanding edge-connectivity in the Internet through core-decomposition
• Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Critical Exponents for Marked Random Connection Models
• Phase transitions of extremal cuts for the configuration model
• First passage percolation on the Newman-Watts small world model
• Projective, Sparse, and Learnable Latent Position Network Models
• Resilience of antagonistic networks with regard to the effects of initial failures and degree-degree correlations
• Random Popular Matchings with Incomplete Preference Lists
• Quantum Motif Clustering
• Targeted Vaccination Strategies for an Infinite-dimensional SIS Model
• Finiteness of the percolation threshold for inhomogeneous long-range models in one dimension
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Random minimum spanning tree and dense graph limits
• Degree-penalized contact processes
• Emergence of Multivariate Extremes in Multilayer Inhomogeneous Random Graphs
• Age evolution in the mean field forest fire model via multitype branching processes
• Asymptotics for cliques in scale-free random graphs
• Overlapping community detection in networks via sparse spectral decomposition
• Degrees and distances in random and evolving Apollonian networks
• A cluster expansion approach to exponential random graph models
• Atoms and associated spectral properties for positive operators on L^p
• Non-Uniqueness Phase in Hyperbolic Marked Random Connection Models using the Spherical Transform
• Measuring Interlayer Dependence of Large Degrees in Multilayer Inhomogeneous Random Graphs
• Poisson approximation for cycles in the generalised random graph
• The largest subcritical component in inhomogeneous random graphs of preferential attachment type
• Gelation in cluster coagulation processes
• Nonreciprocal random networks and their percolation properties
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon
• Inhomogeneous random graphs with infinite-mean fitness variables
• Sparse Models for Machine Learning
• Chemical distance in geometric random graphs with long edges and scale-free degree distribution
• Robust subgraph counting with distribution-free random graph analysis
• The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights
• Limits and consistency of non-local and graph approximations to the Eikonal equation
• Exponential bounds for inhomogeneous random graphs in a Gaussian case
• Finding induced subgraphs in scale-free inhomogeneous random graphs