Critical behavior in inhomogeneous random graphs. Issue 4 (28th August 2012)

• Record Type: Journal Article
• Authors: van der Hofstad, Remco
• Is Part Of: Random structures & algorithms. Volume 42:Issue 4(2013)
• Page Start: 480
• Page End: 508
• Publication Date: 2012-08-28
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20450
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We study the critical behavior of inhomogeneous random graphs in the so‐called rank‐1 case, where edges are present independently but with unequal edge occupation probabilities. The edge occupation probabilities are moderated by <italic>vertex weights</italic>, and are such that the degree of vertex <italic>i</italic> is close in distribution to a Poisson random variable with parameter <italic>w</italic><sub><italic>i</italic></sub>, where <italic>w</italic><sub><italic>i</italic></sub> denotes the weight of vertex <italic>i</italic>. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable <italic>W</italic>. In this case, the proportion of vertices with degree <italic>k</italic> is close to the probability that a Poisson random variable with <italic>random</italic> parameter <italic>W</italic> takes the value <italic>k</italic>. We pay special attention to the <italic>power‐law case</italic>, i.e., the case where <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}{\mathbb{P}}(W\geq k)\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q19g8t" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> is proportional to <italic>k</italic><sup>‐(τ‐1)</sup> for some power‐law exponent τ > 3, a property which is then inherited by the asymptotic degree distribution.</p> <p>We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution <italic>W</italic>. Indeed, when <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}{\mathbb{P}}(W > k) \leq ck^{-(\tau-1)}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q19g4m" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> for all <italic>k</italic> ≥ 1 and some τ > 4 and <italic>c</italic> > 0, the largest critical connected component in a graph of size <italic>n</italic> is of order <italic>n</italic><sup>2/3</sup>, as it is for the critical Erdős‐Rényi random graph. When, instead, <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}{\mathbb{P}}(W > k)=ck^{-(\tau-1)}(1+o(1))\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q19g1z" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> for <italic>k</italic> large and some τ∈(3, 4) and <italic>c</italic> > 0, the largest critical connected component is of the much smaller order <italic>n</italic><sup>(τ‐2)/(τ‐1)</sup>. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 480–508, 2013</p> </abstract>