On the second largest component of random hyperbolic graphs

DOI10.1137/18M121201XMaRDI QIDQ5244122zbMATH OpenOpenAlexWikidataFDO

Authors D. Mitsche, Marcos Kiwi

Publication date 20 November 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

component structurerandom hyperbolic graphsscale-free networks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: We show that in the random hyperbolic graph model as formalized by Gugelmann et al. in the most interesting range of $frac12<alpha<1$ the size of the second largest component is $Theta((logn{)}^{1/(1-alpha)})$, thus answering a question of Bode et al. We also show that for $alpha=frac12$ with constant probability the corresponding size is $Theta(logn)$, whereas for $alpha=1$ it is $Omega(n^b)$ for some $b>0$.

Recommendations

• A Bound for the Diameter of Random Hyperbolic Graphs
• On the largest component of subcritical random hyperbolic graphs
• On the largest component of a hyperbolic model of complex networks
• Law of large numbers for the largest component in a hyperbolic model of complex networks
• Component structure in the evolution of random hypergraphs

Cites work

• A Bound for the Diameter of Random Hyperbolic Graphs
• Bootstrap percolation and the geometry of complex networks
• Bootstrap percolation on geometric inhomogeneous random graphs
• Geometric inhomogeneous random graphs
• Greedy routing and the algorithmic small-world phenomenon
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 6303023 (Why is no real title available?)
• Law of large numbers for the largest component in a hyperbolic model of complex networks
• On a geometrization of the Chung-Lu model for complex networks
• On the diameter of hyperbolic random graphs
• On the largest component of a hyperbolic model of complex networks
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Scale-free percolation
• Spectral gap of random hyperbolic graphs and related parameters
• The probability of connectivity in a hyperbolic model of complex networks
• Typical distances in a geometric model for complex networks

Cited in

(15)

• The contact process on random hyperbolic graphs: metastability and critical exponents
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs
• Clustering in a hyperbolic model of complex networks
• On the largest component of subcritical random hyperbolic graphs
• Spatial networks and percolation. Abstracts from the workshop held January 17--23, 2021 (hybrid meeting)
• Assortativity and Bidegree Distributions on Bernoulli Random Graph Superpositions
• Assortativity and bidegree distributions on Bernoulli random graph superpositions
• Sub-tree counts on hyperbolic random geometric graphs
• Clustering and percolation on superpositions of Bernoulli random graphs
• Cover and hitting times of hyperbolic random graphs
• Average distance in a general class of scale-free networks
• Cluster-size decay in supercritical kernel-based spatial random graphs
• Tail bounds for detection times in mobile hyperbolic graphs
• Hamilton cycles and perfect matchings in the KPKVB model
• Hyperbolic random graphs: clique number and degeneracy with implications for colouring

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

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