The phase transition in inhomogeneous random graphs
From MaRDI portal
Publication:5310264
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).
Recommendations
Cites work
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A Random Graph Model for Power Law Graphs
- Analyticity in infinite dimensional spaces
- Continuity of the percolation threshold in randomly grown graphs.
- Coupling Scale-Free and Classical Random Graphs
- scientific article; zbMATH DE number 1713116 (Why is no real title available?)
- scientific article; zbMATH DE number 52632 (Why is no real title available?)
- scientific article; zbMATH DE number 1350307 (Why is no real title available?)
- scientific article; zbMATH DE number 1984542 (Why is no real title available?)
- scientific article; zbMATH DE number 747040 (Why is no real title available?)
- scientific article; zbMATH DE number 3274494 (Why is no real title available?)
- scientific article; zbMATH DE number 3349139 (Why is no real title available?)
- scientific article; zbMATH DE number 3410334 (Why is no real title available?)
- scientific article; zbMATH DE number 2212219 (Why is no real title available?)
- Limits of dense graph sequences
- On the spread of viruses on the Internet
- Robustness and Vulnerability of Scale-Free Random Graphs
- The Average Distance in a Random Graph with Given Expected Degrees
- Two phase transitions for the contact process on small worlds
Cited in
(only showing first 100 items - show all)- How liquid is biological signalling?
- Two-sample hypothesis testing for inhomogeneous random graphs
- An impossibility result for reconstruction in the degree-corrected stochastic block model
- Large deviations in generalized random graphs with node weights
- On edge exchangeable random graphs
- The local limit of the uniform spanning tree on dense graphs
- A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
- Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm
- MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
- Geometric inhomogeneous random graphs
- Exponential extinction time of the contact process on rank-one inhomogeneous random graphs
- The degree analysis of an inhomogeneous growing network with two types of vertices
- Generalized random dot product graph
- A modified bootstrap percolation on a random graph coupled with a lattice
- Phase transition in inhomogenous Erdős-Rényi random graphs via tree counting
- Critical random graphs and the differential equations technique
- Evolution of a modified binomial random graph by agglomeration
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- A moment-generating formula for Erdős-Rényi component sizes
- Law of large numbers for the largest component in a hyperbolic model of complex networks
- Cluster tails for critical power-law inhomogeneous random graphs
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- Large deviations for the annealed Ising model on inhomogeneous random graphs: spins and degrees
- Power-law partial correlation network models
- Limit theorems for eigenvectors of the normalized Laplacian for random graphs
- Co-evolutionary dynamics and Bayesian interaction games
- Random networks with sublinear preferential attachment: the giant component
- Classification and estimation in the stochastic blockmodel based on the empirical degrees
- PageRank on inhomogeneous random digraphs
- Counting cliques and cycles in scale-free inhomogeneous random graphs
- Weakly interacting particle systems on inhomogeneous random graphs
- On estimation and inference in latent structure random graphs
- Age evolution in the mean field forest fire model via multitype branching processes
- Network representation using graph root distributions
- Geometry of the minimal spanning tree of a random 3-regular graph
- Stochastic block model in a new critical regime and the interacting multiplicative coalescent
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Limits of multiplicative inhomogeneous random graphs and Lévy trees: limit theorems
- Greedy routing and the algorithmic small-world phenomenon
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Higher-order fluctuations in dense random graph models
- Penalising transmission to hubs in scale-free spatial random graphs
- Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs
- Berry-Esseen bounds for generalized U-statistics
- The Fréchet mean of inhomogeneous random graphs
- Overlapping community detection in networks via sparse spectral decomposition
- Cut norm discontinuity of triangular truncation of graphons
- Universality for critical heavy-tailed network models: metric structure of maximal components
- Optimal subgraph structures in scale-free configuration models
- PageRank's behavior under degree correlations
- Limiting distribution of short cycles in inhomogeneous random uniform hypergraph
- Bootstrap percolation in power-law random graphs
- Percolation on dense graph sequences
- Diameter, connectivity, and phase transition of the uniform random intersection graph
- Cliques in rank-1 random graphs: the role of inhomogeneity
- Sampling and estimation for (sparse) exchangeable graphs
- Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
- Limit laws for the number of triangles in the generalized random graphs with random node weights
- Optimal graphon estimation in cut distance
- Bootstrap percolation in directed inhomogeneous random graphs
- Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
- The diameter of weighted random graphs
- Analytic description of the phase transition of inhomogeneous multigraphs
- Linear embeddings of graphs and graph limits
- An old approach to the giant component problem
- The structure of typical clusters in large sparse random configurations
- Generating hierarchial scale-free graphs from fractals
- Nonparametric statistics of dynamic networks with distinguishable nodes
- Continuous spin models on annealed generalized random graphs
- Thresholds for virus spread on networks
- Limit laws in the generalized random graphs with random vertex weights
- Epidemics on random intersection graphs
- Evolution of social networks
- Large deviations for power-law thinned Lévy processes
- Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
- Sombor index and degree-related properties of simplicial networks
- Asymptotics for cliques in scale-free random graphs
- Chemical distance in geometric random graphs with long edges and scale-free degree distribution
- Systemic cascades on inhomogeneous random financial networks
- Mean-field BSDEs with jumps and dual representation for global risk measures
- Connectivity for a modified binomial random graph by agglomeration
- SIR epidemics on a scale-free spatial nested modular network
- First passage percolation on the Newman-Watts small world model
- Critical behavior in inhomogeneous random graphs
- Large dicliques in a directed inhomogeneous random graph
- The phase transition in random graphs: a simple proof
- Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.
- Joint vertex degrees in the inhomogeneous random graph model \(\mathcal g(n, \{p_{ij}\})\)
- Large deviation analysis for layered percolation problems on the complete graph
- The scaling window for a random graph with a given degree sequence
- The mixing time of the giant component of a random graph
- Connectivity of inhomogeneous random graphs
- scientific article; zbMATH DE number 6385345 (Why is no real title available?)
- Poisson approximation of subgraph counts in stochastic block models and a graphon model
- A nonparametric view of network models and Newman–Girvan and other modularities
- Spectral redemption in clustering sparse networks
- Justifying the small-world phenomenon via random recursive trees
- Sparse random graphs with clustering
- Bounding basic characteristics of spatial epidemics with a new percolation model
- Clique percolation
This page was built for publication: The phase transition in inhomogeneous random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5310264)
