On the largest component of subcritical random hyperbolic graphs

DOI10.1214/21-ECP380MaRDI QIDQ2064858zbMATH OpenWikidataFDO

Authors Roland Diel, D. Mitsche

Publication date 6 January 2022

Published in Electronic Communications in Probability (Search for Journal in Brave)

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

zbMATH Keywords

geometric probabilityrandom hyperbolic graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Geometric probability and stochastic geometry (60D05)

Abstract: We consider the random hyperbolic graph model introduced by [KPK + 10] and then formalized by [GPP12]. We show that, in the subcritical case $alpha$ > 1, the size of the largest component is n^{1/(2$alpha$)+o(1)} , thus strengthening a result of [BFM15] which gave only an upper bound of n^{1/$alpha$+o(1)}.

Recommendations

• On the second largest component of random hyperbolic graphs
• A Bound for the Diameter of Random Hyperbolic Graphs
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• Largest component of subcritical random graphs with given degree sequence
• The largest component in a subcritical random graph with a power law degree distribution

Cites work

• A Bound for the Diameter of Random Hyperbolic Graphs
• Cliques in hyperbolic random graphs
• Clustering and the hyperbolic geometry of complex networks
• Clustering in a hyperbolic model of complex networks
• Concentration inequalities. A nonasymptotic theory of independence
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Geometric inhomogeneous random graphs
• Greedy routing and the algorithmic small-world phenomenon
• Hyperbolic random graphs: separators and treewidth
• Law of large numbers for the largest component in a hyperbolic model of complex networks
• On the diameter of hyperbolic random graphs
• On the largest component of a hyperbolic model of complex networks
• On the second largest component of random hyperbolic graphs
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Sampling geometric inhomogeneous random graphs in linear time
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Spectral gap of random hyperbolic graphs and related parameters
• The diameter of KPKVB random graphs
• The probability of connectivity in a hyperbolic model of complex networks
• Typical distances in a geometric model for complex networks

Cited in

(11)

• Law of large numbers for the largest component in a hyperbolic model of complex networks
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• Asymptotics for the size of the largest component scaled to ``\(\log n\) in inhomogeneous random graphs
• On the largest component of a hyperbolic model of complex networks
• Sub-tree counts on hyperbolic random geometric graphs
• The Asymptotic Size of the Largest Component in Random Geometric Graphs with Some Applications
• On the second largest component of random hyperbolic graphs
• Largest component of subcritical random graphs with given degree sequence
• Tail bounds for detection times in mobile hyperbolic graphs
• Capturing an invisible robber using separators
• The largest component in a subcritical random graph with a power law degree distribution

This page was built for publication: On the largest component of subcritical random hyperbolic graphs

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