Typical distances in a geometric model for complex networks

DOI10.24166/IM.13.2017zbMATH Open1491.05163arXiv1506.07811OpenAlexW2963822936MaRDI QIDQ3389693FDOQ3389693

Authors: Michel Bode, Nikolaos Fountoulakis, Mohammed Abdullah 

Publication date: 23 March 2022

Published in: Internet Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Statistical mechanics of complex networks
• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• Metric structure of random networks
• The phase transition in inhomogeneous random graphs
• Title not available (Why is that?)
• Connected components in random graphs with given expected degree sequences
• The degree sequence of a scale-free random graph process
• Lectures on Complex Networks
• Paths in graphs
• The average distances in random graphs with given expected degrees
• Complex graphs and networks
• The diameter of a scale-free random graph
• Diameters in preferential attachment models
• Typical distances in ultrasmall random networks
• On the Diameter of Hyperbolic Random Graphs
• A Bound for the Diameter of Random Hyperbolic Graphs
• On the largest component of a hyperbolic model of complex networks
• Title not available (Why is that?)
• Universality for distances in power-law random graphs
• Random Hyperbolic Graphs: Degree Sequence and Clustering
• On a geometrization of the Chung–Lu model for complex networks
• On Palm probabilities

Cited In (17)

• The diameter of KPKVB random graphs
• On the Second Largest Component of Random Hyperbolic Graphs
• On the largest component of subcritical random hyperbolic graphs
• The structure of distances in networks
• The contact process on random hyperbolic graphs: metastability and critical exponents
• Title not available (Why is that?)
• Sampling Geometric Inhomogeneous Random Graphs in Linear Time
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs
• Spectral gap of random hyperbolic graphs and related parameters
• Geometric inhomogeneous random graphs
• Sub-tree counts on hyperbolic random geometric graphs
• Clustering in a hyperbolic model of complex networks
• 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
• AVERAGE GEODESIC DISTANCE OF SIERPIŃSKI-TYPE 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)