Typical distances in a geometric model for complex networks

DOI10.24166/IM.13.2017MaRDI QIDQ3389693zbMATH OpenOpenAlexFDO

Authors Michel Bode, Nikolaos Fountoulakis, Mohammed Abdullah

Publication date 23 March 2022

Published in Internet Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complex networksrandom graphstypical distances

Mathematics Subject Classification ID

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

Abstract: We study typical distances in a geometric random graph on the hyperbolic plane. Introduced by Krioukov et al.~cite{ar:Krioukov} as a model for complex networks, $N$ vertices are drawn randomly within a bounded subset of the hyperbolic plane and any two of them are joined if they are within a threshold hyperbolic distance. With appropriately chosen parameters, the random graph is sparse and exhibits power law degree distribution as well as local clustering. In this paper we show a further property: the distance between two uniformly chosen vertices that belong to the same component is doubly logarithmic in $N$, i.e., the graph is an ~emph{ultra-small world}. More precisely, we show that the distance rescaled by $loglogN$ converges in probability to a certain constant that depends on the exponent of the power law. The same constant emerges in an analogous setting with the well-known emph{Chung-Lu} model for which the degree distribution has a power law tail.

Recommendations

• On a geometrization of the Chung-Lu model for complex networks
• Typical distances in ultrasmall random networks
• On the largest component of a hyperbolic model of complex networks
• Clustering in a hyperbolic model of complex networks
• Law of large numbers for the largest component in a hyperbolic model of complex networks

Cites work

• scientific article; zbMATH DE number 227027 (Why is no real title available?)
• scientific article; zbMATH DE number 3106341 (Why is no real title available?)
• A Bound for the Diameter of Random Hyperbolic Graphs
• Complex graphs and networks
• Connected components in random graphs with given expected degree sequences
• Diameters in preferential attachment models
• Emergence of Scaling in Random Networks
• Lectures on Complex Networks
• Metric structure of random networks
• On Palm probabilities
• 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
• Paths in graphs
• Random graphs and complex networks. Volume 1
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Statistical mechanics of complex networks
• The average distances in random graphs with given expected degrees
• The degree sequence of a scale-free random graph process
• The diameter of a scale-free random graph
• The phase transition in inhomogeneous random graphs
• Typical distances in ultrasmall random networks
• Universality for distances in power-law random graphs

Cited in

(21)

• AVERAGE GEODESIC DISTANCE OF SIERPIŃSKI-TYPE NETWORKS
• On the largest component of subcritical random hyperbolic graphs
• The diameter of KPKVB random graphs
• The structure of distances in networks
• The probability of connectivity in a hyperbolic model of complex networks
• The contact process on random hyperbolic graphs: metastability and critical exponents
• scientific article; zbMATH DE number 6701955 (Why is no real title available?)
• On the second largest component of random hyperbolic graphs
• Spectral gap of random hyperbolic graphs and related parameters
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs
• Geometric inhomogeneous random graphs
• Typical distances in ultrasmall random networks
• Chemical distance in geometric random graphs with long edges and scale-free degree distribution
• On a geometrization of the Chung-Lu model for complex networks
• Sub-tree counts on hyperbolic random geometric graphs
• Clustering in a hyperbolic model of complex networks
• Sampling geometric inhomogeneous random graphs in linear time
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Comparison of mean distance in superposed networks
• Penalising transmission to hubs in scale-free spatial random graphs
• Distance distributions for graphs modeling computer networks

This page was built for publication: Typical distances in a geometric model for complex networks

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