Critical behavior in inhomogeneous random graphs

DOI10.1002/RSA.20450MaRDI QIDQ2841680zbMATH OpenOpenAlexFDO

Authors Remco van der Hofstad

Publication date 26 July 2013

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

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

zbMATH Keywords

critical behaviornovel scaling behaviorpower-law degree sequencesrank-1 inhomogeneous random graphsscaling window

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the critical behavior of inhomogeneous random graphs where edges are present independently but with unequal edge occupation probabilities. The edge probabilities are moderated by vertex weights, and are such that the degree of vertex i is close in distribution to a Poisson random variable with parameter w_i, where w_i denotes the weight of vertex i. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable W, in which case the proportion of vertices with degree k is close to the probability that a Poisson random variable with random parameter W takes the value k. We pay special attention to the power-law case, in which P(Wgeq k) is proportional to k^{-( au-1)} for some power-law exponent au>3, a property which is then inherited by the asymptotic degree distribution. We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution W. Indeed, when P(Wgeq k) leq ck^{-( au-1)} for all kgeq 1 and some au>4 and c>0, the largest critical connected component in a graph of size n is of order n^{2/3}, as on the ErdH{o}s-R'enyi random graph. When, instead, P(Wgeq k)=ck^{-( au-1)}(1+o(1)) for k large and some auin (3,4) and c>0, the largest critical connected component is of the much smaller order n^{( au-2)/( au-1)}.

Recommendations

• Novel scaling limits for critical inhomogeneous random graphs
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.
• Cluster tails for critical power-law inhomogeneous random graphs
• Scaling limits for critical inhomogeneous random graphs with finite third moments

Cites work

• A critical point for random graphs with a given degree sequence
• A new approach to the giant component problem
• An Elementary Proof of the Hitting Time Theorem
• Asymptotic equivalence and contiguity of some random graphs
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Connected components in random graphs with given expected degree sequences
• Generating simple random graphs with prescribed degree distribution
• scientific article; zbMATH DE number 1369842 (Why is no real title available?)
• On a conditionally Poissonian graph process
• On the largest component of the random graph at a nearcritical stage
• Random graph asymptotics on high-dimensional tori
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Random subgraphs of the 2D Hamming graph: The supercritical phase
• Scaling limits for critical inhomogeneous random graphs with finite third moments
• The Average Distance in a Random Graph with Given Expected Degrees
• The birth of the giant component
• The Critical Phase for Random Graphs with a Given Degree Sequence
• The Evolution of Random Graphs
• The largest component in a subcritical random graph with a power law degree distribution
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• The Multiplicative Process
• The phase transition in inhomogeneous random graphs
• The phase transition in the configuration model
• The Structure of a Random Graph at the Point of the Phase Transition
• The total progeny in a branching process and a related random walk
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees

Cited in

(38)

• On the instability of matching queues
• The degree analysis of an inhomogeneous growing network with two types of vertices
• Tight fluctuations of weight-distances in random graphs with infinite-variance degrees
• Evolution of a modified binomial random graph by agglomeration
• Cluster tails for critical power-law inhomogeneous random graphs
• Number of edges in inhomogeneous random graphs
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs
• Limitations of Chung Lu random graph generation
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• Universality for critical heavy-tailed network models: metric structure of maximal components
• Viral processes by random walks on random regular graphs
• Critical phenomena in exponential random graphs
• The densest subgraph problem in sparse random graphs
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• Scale-free property for degrees and weights in an \(N\)-interactions random graph model
• Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.
• Ising critical behavior of inhomogeneous Curie-Weiss models and annealed random graphs
• Some introductory notes on random graphs
• Scale-free percolation
• The component sizes of a critical random graph with given degree sequence
• Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees
• An elementary approach to component sizes in critical random graphs
• A PROBABILISTIC FRIENDSHIP NETWORK MODEL
• Heavy-traffic analysis through uniform acceleration of queues with diminishing populations
• Survey of scalings for the largest connected component in inhomogeneous random graphs
• The phase transition in multitype binomial random graphs
• The interpolation method for random graphs with prescribed degrees
• Using the bootstrap for statistical inference on 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
• Large deviation principles for empirical measures of colored random graphs
• Stable graphs: distributions and line-breaking construction
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• Continuum limit of critical inhomogeneous random graphs
• Emergence of multivariate extremes in multilayer inhomogeneous random graphs
• Novel scaling limits for critical inhomogeneous random graphs
• Inhomogeneous random graphs with infinite-mean fitness variables
• Limiting spectra of inhomogeneous random graphs

This page was built for publication: Critical behavior in inhomogeneous random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2841680)