Sub-tree counts on hyperbolic random geometric graphs

DOI10.1017/APR.2022.1zbMATH Open1503.60030arXiv1802.06105OpenAlexW2788153713WikidataQ115563897 ScholiaQ115563897MaRDI QIDQ5055360FDOQ5055360

Authors: Takashi Owada, D. Yogeshwaran 

Publication date: 13 December 2022

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

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.

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

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

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)

Cites Work

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

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)