Sub-tree counts on hyperbolic random geometric graphs

DOI10.1017/APR.2022.1MaRDI QIDQ5055360zbMATH OpenOpenAlexWikidataFDO

Authors Takashi Owada, D. Yogeshwaran

Publication date 13 December 2022

Published in Advances in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

central limit theoremPoisson point processhyperbolic spacesrandom geometric graphsMalliavin-Stein methodsub-tree counts

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Central limit and other weak theorems (60F05) Hyperbolic and elliptic geometries (general) and generalizations (51M10)

Abstract: We study the hyperbolic random geometric graph introduced in Krioukov et al. For a sequence $R_{n}oinfty$, we define these graphs to have the vertex set as Poisson points distributed uniformly in balls $B(0,R_n)subset{B}_d^{alpha}$, the $d$-dimensional Poincar'e ball (unit d-ball with the Poincar'e metric $d_{alpha}$ corresponding to negative curvature $-alph{a}^2,alpha>0$) by connecting any two points within a distance $R_n$ according to the metric $d_{zeta},zeta>0$. Denoting these graphs by $H{G}_n(R_n;alpha,zeta)$, we study asymptotic counts of copies of a fixed tree $Gamm{a}_k$ (with the ordered degree sequence $d_{(1)}leqldotsleq{d}_{(k)}$) in $H{G}_n(R_n;alpha,zeta)$. Unlike earlier works, we count more involved structures, allowing for $d>2$, and in many places, more general choices of $R_n$ rather than $R_n=2[zeta(d-1){]}^{-1}log(n/u),uin(0,infty)$. The latter choice of $R_n$ for $alpha/zeta>1/2$ corresponds to the thermodynamic regime. We show multiple phase transitions in $H{G}_n(R_n;alpha,zeta)$ as $alpha/zeta$ increases, i.e., the space $B_d^{alpha}$ becomes more hyperbolic. In particular, our analyses reveal that the sub-tree counts exhibit an intricate dependence on the degree sequence $d_{(1)},ldots,d_{(k)}$ of $Gamm{a}_k$ as well as the ratio $alpha/zeta$. Under a more general radius regime $R_n$ than that described above, we investigate the asymptotics of the expectation and variance of sub-tree counts. Moreover, we prove the corresponding central limit theorem as well. Our proofs rely crucially on a careful analysis of the sub-tree counts near the boundary using Palm calculus for Poisson point processes along with estimates for the hyperbolic metric and measure. For the central limit theorem, we use the abstract normal approximation result from Last et al. derived using the Malliavin-Stein method.

Recommendations

• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs
• On the largest component of subcritical random hyperbolic graphs
• Typical distances in a geometric model for complex networks

Cites work

• scientific article; zbMATH DE number 1149837 (Why is no real title available?)
• A Bound for the Diameter of Random Hyperbolic Graphs
• Bootstrap percolation and the geometry of complex networks
• Cliques in hyperbolic random graphs
• Clustering and the hyperbolic geometry of complex networks
• Clustering in a hyperbolic model of complex networks
• Coarse geometry and randomness. École d'Été de Probabilités de Saint-Flour XLI -- 2011
• Continuum Percolation
• Foundations of Hyperbolic Manifolds
• Law of large numbers for the largest component in a hyperbolic model of complex networks
• Lectures on the Poisson Process
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs
• Limit theory for point processes in manifolds
• Normal approximation on Poisson spaces: Mehler's formula, second order Poincaré inequalities and stabilization
• On a geometrization of the Chung-Lu model for complex networks
• On the largest component of a hyperbolic model of complex networks
• On the second largest component of random hyperbolic graphs
• Percolation in the hyperbolic plane
• Poisson approximation of the length spectrum of random surfaces
• Probability on trees and networks
• Probability theory of classical Euclidean optimization problems
• Random Geometric Graphs
• Random Plane Networks
• Random construction of Riemann surfaces
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Random Čech complexes on Riemannian manifolds
• Spectral gap of random hyperbolic graphs and related parameters
• Statistical regularities of self-intersection counts for geodesics on negatively curved surfaces
• Stochastic analysis for Poisson point processes. Malliavin calculus, Wiener-Itô chaos expansions and stochastic geometry
• Stochastic geometry and wireless networks. Volume I. Theory
• Stochastic geometry for wireless networks
• The diameter of KPKVB random graphs
• The probability of connectivity in a hyperbolic model of complex networks
• The topology of probability distributions on manifolds
• Typical distances in a geometric model for complex networks

Cited in

(6)

• Large nearest neighbour balls in hyperbolic stochastic geometry
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs
• A quantitative central limit theorem for Poisson horospheres in high dimensions
• Intersections of Poisson \(k\)-flats in constant curvature spaces
• Cover and hitting times of hyperbolic random graphs
• Counting subgraphs in hyperbolic graphs with symmetry

This page was built for publication: Sub-tree counts on hyperbolic random geometric graphs

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