The diameter of KPKVB random graphs

DOI10.1017/APR.2019.23MaRDI QIDQ5203939zbMATH OpenOpenAlexWikidataFDO

Authors Tobias Müller, Merlijn Staps

Publication date 9 December 2019

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

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

zbMATH Keywords

complex networkgraph diameterhyperbolic planerandom graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Geometric probability and stochastic geometry (60D05) Percolation (82B43)

Abstract: We consider a model for complex networks that was recently proposed as a model for complex networks by Krioukov et al. In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most a certain hyperbolic distance from each other. It has been previously shown that this model has various properties associated with complex networks, including a power-law degree distribution and a strictly positive clustering coefficient. The model is specified using three parameters : the number of nodes $N$, which we think of as going to infinity, and $alpha,u>0$ which we think of as constant. Roughly speaking $alpha$ controls the power law exponent of the degree sequence and $u$ the average degree. Earlier work of Kiwi and Mitsche has shown that when $alpha<1$ (which corresponds to the exponent of the power law degree sequence being $<3$) then the diameter of the largest component is a.a.s.~polylogarithmic in $N$. Friedrich and Krohmer have shown it is a.a.s.~$Omega(logN)$ and they improved the exponent of the polynomial in $logN$ in the upper bound. Here we show the maximum diameter over all components is a.a.s.~$O(logN)$ thus giving a bound that is tight up to a multiplicative constant.

Recommendations

• A Bound for the Diameter of Random Hyperbolic Graphs
• On the largest component of a hyperbolic model of complex networks
• Clustering in a hyperbolic model of complex networks
• 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

Cites work

• A Bound for the Diameter of Random Hyperbolic Graphs
• Efficient embedding of scale-free graphs in the hyperbolic plane
• Geometry of surfaces
• scientific article; zbMATH DE number 3826957 (Why is no real title available?)
• scientific article; zbMATH DE number 227027 (Why is no real title available?)
• 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
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• 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

(21)

• Law of large numbers for the largest component in a hyperbolic model of complex networks
• 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)
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Does a central limit theorem hold for the \(k\)-skeleton of Poisson hyperplanes in hyperbolic space?
• The probability of connectivity in a hyperbolic model of complex networks
• On the diameter of hyperbolic random graphs
• On the diameter of hyperbolic random graphs
• Sub-tree counts on hyperbolic random geometric graphs
• The diameter of KPKVB random graphs
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Cover and hitting times of hyperbolic random graphs
• Average distance in a general class of scale-free networks
• A quadtree, a Steiner spanner, and approximate nearest neighbours in hyperbolic space
• Tail bounds for detection times in mobile hyperbolic graphs
• Hyperbolic random graphs: clique number and degeneracy with implications for colouring
• Structure and independence in hyperbolic uniform disk graphs
• Statistical mechanics of random hyperbolic graphs within the fermionic maximum-entropy framework

This page was built for publication: The diameter of KPKVB random graphs

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