A Bound for the Diameter of Random Hyperbolic Graphs

DOI10.1137/1.9781611973761.3MaRDI QIDQ5194791zbMATH OpenOpenAlexFDO

Authors D. Mitsche, Marcos Kiwi

Publication date 17 September 2019

Published in 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Random hyperbolic graphs were recently introduced by Krioukov et. al. [KPKVB10] as a model for large networks. Gugelmann, Panagiotou, and Peter [GPP12] then initiated the rigorous study of random hyperbolic graphs using the following model: for $alpha>frac12$, $CinmathbbR$, $ninmathbbN$, set $R=2lnn+C$ and build the graph $G=(V,E)$ with $|V|=n$ as follows: For each $vinV$, generate i.i.d. polar coordinates $(r_v,het{a}_v)$ using the joint density function $f(r,heta)$, with $het{a}_v$ chosen uniformly from $[0,2pi)$ and $r_v$ with density $f(r)=fracalphasinh(alphar)cosh(alphaR)-1$ for $0leqr<R$. Then, join two vertices by an edge, if their hyperbolic distance is at most $R$. We prove that in the range $frac12<alpha<1$ a.a.s. for any two vertices of the same component, their graph distance is $O(lo{g}^{C_0+1+o(1)}n)$, where $C_0=2/(frac12-frac34alpha+fracalph{a}^{2}4)$, thus answering a question raised in [GPP12] concerning the diameter of such random graphs. As a corollary from our proof we obtain that the second largest component has size $O(lo{g}^{2C_0+1+o(1)}n)$, thus answering a question of Bode, Fountoulakis and M"{u}ller [BFM13]. We also show that a.a.s. there exist isolated components forming a path of length $Omega(logn)$, thus yielding a lower bound on the size of the second largest component.

Recommendations

• On the diameter of hyperbolic random graphs
• On the diameter of hyperbolic random graphs
• The diameter of a random graph with bounded diameter
• On the hyperbolicity of random graphs
• On the diameter of a class of random graphs
• scientific article; zbMATH DE number 6303023
• On the diameter of random planar graphs
• On the diameter of random planar graphs
• Diameters of random circulant graphs

Cited in

(24)

• Spectral gap of random hyperbolic graphs and related parameters
• Geometric inhomogeneous random graphs
• 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
• Greedy routing and the algorithmic small-world phenomenon
• Mathematical properties on the hyperbolicity of interval graphs
• A random link via bridge position is hyperbolic
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Typical distances in a geometric model for complex networks
• On the diameter of hyperbolic random graphs
• On the hyperbolicity of random graphs
• On the diameter of hyperbolic random graphs
• Updating dynamic random hyperbolic graphs in sublinear time
• Sub-tree counts on hyperbolic random geometric graphs
• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
• Sampling geometric inhomogeneous random graphs in linear time
• The diameter of KPKVB random graphs
• On the second largest component of random hyperbolic graphs
• Cover and hitting times of hyperbolic 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
• Bootstrap percolation and the geometry of complex networks

This page was built for publication: A Bound for the Diameter of Random Hyperbolic Graphs

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