Asymptotic coarse Ricci curvature of inhomogeneous random graph

DOI10.1016/J.SPL.2024.110245MaRDI QIDQ6606045zbMATH OpenFDO

Publication date 16 September 2024

Published in Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.SPL.2024.110245

coarse Ricci curvature inhomogeneous random graph phase transition

Random graphs (graph-theoretic aspects) (05C80) Minimal surfaces in differential geometry, surfaces with prescribed mean curvature (53A10) Methods of global Riemannian geometry, including PDE methods; curvature restrictions (53C21) Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces (53C23)

Review text

This paper is about the Ricci curvature of inhomogeneous random graphs. The model of (undirected, loopless) random graphs considered is denoted \(\mathcal{G}(n,\alpha)\) for a constant \(\alpha\in [0,1]\); it has vertex set \([n]=\{1,2,\ldots, n\}\) and (for a constant \(\lambda\) and a symmetric function \(g:[0,1]^{2}\rightarrow [0,1]\)) vertices \(i\neq j\) with \(1\leq i<j\leq n\) are adjacent with probability \(\lambda g(i/n,j/n)/n^{\alpha}\) independent of all other pairs of vertices. For \(\alpha=1\) this is (a case of) the inhomogeneous random graph in [\textit{B. Bollobàs} et al., Random Struct. Algorithms 31, No. 1, 3--122 (2007; Zbl 1123.05083)]. Note that when \(g\) is non-constant this random graph can be inhomogeneous.\N\NThe Ricci curvature, in geometry, is a measure of the local geometrical difference between a Riemannian manifold and Euclidean space. This has been extended in various ways to the context of graphs, the relevant notion we consider is the so-called coarse Ricci curvature first defined in [\textit{Y. Ollivier}, J. Funct. Anal. 256, No. 3, 810--864 (2009; Zbl 1181.53015)]. Given a metric space \((S,d)\) and two probability distributions \(P_{1}\) and \(P_{2}\) on \(S\), let \(L_{1}\) be the space of all Lipschitz 1-functions on \(S\), i.e. functions \(f(x)\) such that \(\vert f(x)-f(y)\vert \leq d(x,y)\) for all \(x,y\in S\). The transportation distance between \(P_{1}\) and \(P_{2}\) is then defined to be \(W_{1}(P_{1},P_{2})=\sup_{f\in L_{1}}\{ \int f dP_{1}-\int f dP_{2}\}\). The coarse Ricci curvature of \((x,y)\in S\times S\) is then defined to be \(\kappa(x,y)=1-W_{1}(P_{x},P_{y})/d(x,y)\). In the graph context we of course take \(d(x,y)\) to be the shortest path distance between \(x\) and \(y\) and \(P_{i}\) is defined to be, when \(i\) is a vertex of degree \(d(i)\), \(1/d(i)\) for each neighbour of \(i\) and 0 for non-neighbours of \(i\). In this case, we refer to the coarse Ricci curvature as \(\kappa_{n}(x,y)\), \(n\) being the number of vertices.\N\NRecently, in [\textit{B. B. Bhattacharya} and \textit{S. Mukherjee}, Discrete Math. 338, No. 1, 23--42 (2015; Zbl 1301.05078)], the asymptotic value of \(\kappa_{n}(i,j)\) for coarse Ricci curvature of Erdős-Rényi random graphs \(G(n,p)\) is obtained, conditional on \(i\) and \(j\) being adjacent, and the paper under review uses a number of their results. The main result of the paper under review (Theorem 2.1) is to give the asymptotic value of the Ricci curvature for \(\mathcal{G}(n,\alpha)\) for various values of \(\alpha\), again conditional on \(i\) and \(j\) being adjacent and subject to the important additional condition that, for all \(x\), \(y\), \(g(x,y)\geq \delta>0\) for some \(\delta\). There are a number of phase transitions as the value: of \(\alpha\) varies; for example, when \(\alpha=1\) we get \(\kappa_{n}(i,j)\) converges in probability to \(-2\left(1-\frac{1}{1+X_{i}}+\frac{1}{1+X_{j}}\right)\). Here, \(X_{k}\) is Poisson with parameter \(\lambda g_{1}(k/n)\) and \(g_{1}(x)=\int_{y=0}^{1}g(x,y) dy\). However, if \(\alpha\in (2/3,1)\) we get \(\kappa_{n}(i,j)\) converges in probability to \(-2\) and if \(\alpha\in (1/2,2/3)\) it converges in probability to \(-1\). Generally, provided the \(g(x,y)>\delta>0\) condition holds, there is actually no difference from Bhattacharya and Mukherjee's results [loc. cit.] except at the two extremes \(\alpha=1\) and \(\alpha=0\). In particular, for \(\alpha\neq 0\) it does not depend on \(i\) and \(j\) or on \(g(x,y)\).\N\NWhen the additional condition \(g(x,y)>\delta>0\) does not hold, it seems harder to analyse the process, as the model can become extremely complex. The author looks in the other main result at the special case of the `rank 1' model where \(g(x,y)=xy\) which of course does not satisfy the additional condition. This result is more complex: there are more ranges of \(\alpha\) to consider than in the previous theorem, and within each such range different behaviours may arise from varying values of \(i\) and \(j\) relative to \(n\) as well.

Recommendations

Cites work

This page was built for publication: Asymptotic coarse Ricci curvature of inhomogeneous random graph

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