The phase transition in inhomogeneous random graphs

DOI10.1002/rsa.20168zbMath1123.05083arXivmath/0504589OpenAlexW2950850272WikidataQ105583236 ScholiaQ105583236MaRDI QIDQ5310264

Oliver Riordan, Svante Janson, Béla Bollobás

Publication date: 21 September 2007

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0504589

zbMATH Keywords

phase transition branching process giant component sparse inhomogeneous random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Related Items

Assortativity and Bidegree Distributions on Bernoulli Random Graph Superpositions, Birth of a Strongly Connected Giant in an Inhomogeneous Random Digraph, An elementary approach to component sizes in critical random graphs, Strong couplings for static locally tree-like random graphs, Assortativity and bidegree distributions on Bernoulli random graph superpositions, Random Simplicial Complexes: Models and Phenomena, Large deviation analysis for layered percolation problems on the complete graph, Inhomogeneous Financial Networks and Contagious Links, The scaling window for a random graph with a given degree sequence, Community Detection in Temporal Multilayer Networks, with an Application to Correlation Networks, The structure of typical clusters in large sparse random configurations, The evolution of subcritical Achlioptas processes, Cooperative epidemics spreading under resource control, Generating hierarchial scale-free graphs from fractals, The mixing time of the giant component of a random graph, Connectivity of inhomogeneous random graphs, Large deviations for empirical measures of generalized random graphs, Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs, Nonparametric statistics of dynamic networks with distinguishable nodes, A Dynamic Contagion Risk Model with Recovery Features, Continuous spin models on annealed generalized 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, Perfect matchings in inhomogeneous random bipartite graphs in random environment, Poisson approximation of subgraph counts in stochastic block models and a graphon model, Heavy-Traffic Analysis Through Uniform Acceleration of Queues with Diminishing Populations, The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘), Unnamed Item, Continuum limit of the nonlocal p-Laplacian evolution problem on random inhomogeneous graphs, Thresholds for virus spread on networks, A nonparametric view of network models and Newman–Girvan and other modularities, Spectral redemption in clustering sparse networks, Dismantling Sparse Random Graphs, Systemic cascades on inhomogeneous random financial networks, Sparse Graphs Using Exchangeable Random Measures, Mean-field BSDEs with jumps and dual representation for global risk measures, Justifying the small-world phenomenon via random recursive trees, Subcritical Random Hypergraphs, High-Order Components, and Hypertrees, KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation, Limit laws in the generalized random graphs with random vertex weights, Epidemics on random intersection graphs, Big Jobs Arrive Early: From Critical Queues to Random Graphs, Sparse random graphs with clustering, Maximizing the Size of the Giant, Line-of-Sight Percolation, Unnamed Item, Diameters in Supercritical Random Graphs Via First Passage Percolation, The Diameter of Sparse Random Graphs, Bounding basic characteristics of spatial epidemics with a new percolation model, Sparse exchangeable graphs and their limits via graphon processes, Community Detection and Stochastic Block Models, Statistical inference on random dot product graphs: a survey, Aggregation models with limited choice and the multiplicative coalescent, Clique percolation, Asymptotic equivalence and contiguity of some random graphs, Merging percolation onZdand classical random graphs: Phase transition, Giant Component in Random Multipartite Graphs with Given Degree Sequences, Small-world graphs: characterization and alternative constructions, Phase transition in random distance graphs on the torus, Inhomogeneous random graphs, isolated vertices, and Poisson approximation, Sparse graphs: Metrics and random models, Survey of Scalings for the Largest Connected Component in Inhomogeneous Random Graphs, Large Cliques in a Power-Law Random Graph, Random Networks with Preferential Growth and Vertex Death, Ramsey games with giants, The Largest Component in Subcritical Inhomogeneous Random Graphs, Evolution of social networks, A new approach to the giant component problem, SIR epidemics on a scale-free spatial nested modular network, Universality for distances in power-law random graphs, Spectral bounds in random graphs applied to spreading phenomena and percolation, Generalized quasirandom properties of expanding graph sequences, Managing Default Contagion in Inhomogeneous Financial Networks, Birds of a feather or opposites attract - effects in network modelling, Typical distances in a geometric model for complex networks, The shortest distance in random multi-type intersection graphs, Duality in inhomogeneous random graphs, and the cut metric, Optimal graphon estimation in cut distance, RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING, Bootstrap percolation in directed inhomogeneous random graphs, Coin-Flipping, Ball-Dropping, and Grass-Hopping for Generating Random Graphs from Matrices of Edge Probabilities, Analysis of spectral clustering algorithms for community detection: the general bipartite setting, Structural sparsity of complex networks: bounded expansion in random models and real-world graphs, Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs, Ruin probabilities for risk processes in a bipartite network, Component structure of the configuration model: Barely supercritical case, Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models, A Dynamic Network in a Dynamic Population: Asymptotic Properties, Random Popular Matchings with Incomplete Preference Lists, Critical behavior in inhomogeneous random graphs, Sampling Geometric Inhomogeneous Random Graphs in Linear Time, Large dicliques in a directed inhomogeneous random graph, Rate of Convergence to the Poisson Law of the Numbers of Cycles in the Generalized Random Graphs, The diameter of weighted random graphs, Analytic description of the phase transition of inhomogeneous multigraphs, Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1., Linear embeddings of graphs and graph limits, An old approach to the giant component problem, Joint Vertex Degrees in the Inhomogeneous Random Graph Model ℊ(n,{p_ij}), Large deviations for power-law thinned Lévy processes, Overlapping community detection in networks via sparse spectral decomposition, An impossibility result for reconstruction in the degree-corrected stochastic block model, First passage percolation on the Newman-Watts small world 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 preferential attachment model with random initial degrees, Minimum vertex cover in generalized random graphs with power law degree distribution, Random subcube intersection graphs. I: Cliques and covering, Ising critical behavior of inhomogeneous Curie-Weiss models and annealed random graphs, Information-theoretic thresholds from the cavity method, Cut norm discontinuity of triangular truncation of graphons, A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs, Variational Bayes model averaging for graphon functions and motif frequencies inference in $W$-graph models, Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm, MAX $\kappa$-cut and the inhomogeneous Potts spin Glass, Asymptotics for the size of the largest component scaled to ``$\log n$ in inhomogeneous random graphs, Universally consistent vertex classification for latent positions graphs, Scale-free percolation, Model hierarchies in edge-based compartmental modeling for infectious disease spread, Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels, Large deviation principles for empirical measures of colored random graphs, Universality for critical heavy-tailed network models: metric structure of maximal components, Ising models on power-law random graphs, On an anti-Ramsey threshold for random graphs, Subsampling bootstrap of count features of networks, Inhomogeneous long-range percolation on the hierarchical lattice, Asymptotic behaviour of estimates of link probability in random networks, Co-evolutionary dynamics and Bayesian interaction games, Bootstrap percolation and the geometry of complex networks, Catastrophic event phenomena in communication networks: a survey, Random networks with sublinear preferential attachment: the giant component, Matrix and discrepancy view of generalized random and quasirandom graphs, Classification and estimation in the stochastic blockmodel based on the empirical degrees, A latent process model for time series of attributed random graphs, 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, The method of moments and degree distributions for network models, A modified bootstrap percolation on a random graph coupled with a lattice, The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs, Modelling sexually transmitted infections: the effect of partnership activity and number of partners on $R_0$, The largest component in a subcritical random graph with a power law degree distribution, Critical random graphs: Diameter and mixing time, Reconstruction and estimation in the planted partition model, Degree distribution of a typical vertex in a general random intersection graph, Phase transition in inhomogenous Erdős-Rényi random graphs via tree counting, PageRank on inhomogeneous random digraphs, Optimal subgraph structures in scale-free configuration models, PageRank's behavior under degree correlations, 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, The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs, Limiting distribution of short cycles in inhomogeneous random uniform hypergraph, A moment-generating formula for Erdős-Rényi component sizes, Continuum limit of critical inhomogeneous random graphs, Law of large numbers for the largest component in a hyperbolic model of complex networks, Cluster tails for critical power-law inhomogeneous random graphs, Bootstrap percolation in power-law random graphs, Universality for the distance in finite variance 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, Counting cliques and cycles in scale-free inhomogeneous random graphs, Percolation in invariant Poisson graphs with i.i.d. degrees, Weakly interacting particle systems on inhomogeneous random graphs, A note on the derivation of epidemic final sizes, Phase transitions for modified Erdős--Rényi processes, Novel scaling limits for critical inhomogeneous random graphs, Potential games in volatile environments, Diameters in preferential attachment models, Dynamic random networks in dynamic populations, 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, Power-law partial correlation network models, Sampling and estimation for (sparse) exchangeable graphs, Two-sample Hypothesis Testing for 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, Community detection in sparse networks via Grothendieck's inequality, Limit theorems for eigenvectors of the normalized Laplacian for random graphs, Stochastic block model in a new critical regime and the interacting multiplicative coalescent, How liquid is biological signalling?, The spectra of multiplicative attribute graphs, Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs, Consistent nonparametric estimation for heavy-tailed sparse graphs, Limit laws for the number of triangles in the generalized random graphs with random node weights, 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, Penalising transmission to hubs in scale-free spatial random graphs, Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs, Mean field systems on networks, with singular interaction through hitting times, Berry-Esseen bounds for generalized $U$-statistics, The Fréchet mean of inhomogeneous random graphs, On connectivity and robustness of random graphs with inhomogeneity, Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs, A large-deviations principle for all the components in a sparse inhomogeneous random graph, A probabilistic approach to the leader problem in random graphs, Epidemic models on social networks—With inference, Local limits of spatial inhomogeneous random graphs, A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph, Successive minimum spanning trees, Voter models on subcritical scale‐free random graphs, Clustering and percolation on superpositions of Bernoulli random graphs, A limit theorem for small cliques in inhomogeneous random graphs, Rainbow connectivity and rainbow index of inhomogeneous random graphs, Fluctuations of subgraph counts in graphon based random graphs, Percolation and epidemic processes in one-dimensional small-world networks (extended abstract), Characterization of expansion-related properties of modular graphs, Combinatorial statistics and the sciences, Phase transitions in a power-law uniform hypergraph, Bootstrap percolation in inhomogeneous random graphs, Scaling of the clustering function in spatial inhomogeneous random graphs, Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes, Mutual information for the sparse stochastic block model, Connectivity of Poissonian inhomogeneous random multigraphs, Component behaviour and excess of random bipartite graphs near the critical point, Asymptotic uncertainty quantification for communities in sparse planted bi-section models, Improved baselines for causal structure learning on interventional data, Learning sparse graphons and the generalized Kesten-Stigum threshold, Unnamed Item, Projective, sparse and learnable latent position network models, Stochastic recursions on directed random graphs, Graphon mean field systems, Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes, On sparsity, power-law, and clustering properties of graphex processes, Convergence of Achlioptas Processes via Differential Equations with Unique Solutions, The Interpolation Method for Random Graphs with Prescribed Degrees, An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices, Unnamed Item, Unnamed Item, Site Percolation on the d-Dimensional Hamming Torus, Non-Hyperbolicity of Random Graphs with Given Expected Degrees, Graphs with specified degree distributions, simple epidemics, and local vaccination strategies, Thek-Core and Branching Processes, The cut metric, random graphs, and branching processes, Bounded-Size Rules: The Barely Subcritical Regime, FINANCIAL CONTAGION IN A STOCHASTIC BLOCK MODEL, The Phase Transition in Multitype Binomial Random Graphs, Unnamed Item, First Passage Percolation on Inhomogeneous Random Graphs, On local weak limit and subgraph counts for sparse random graphs

Cites Work