Typical distances in a geometric model for complex networks

Mohammed Amin Abdullah, Michel Bode, Nikolaos Fountoulakis

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)
141 Downloads (Pure)

Abstract

We study typical distances in a geometric random graph on the hyperbolic plane. Introduced by Krioukov et al. 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 ultra-small world. More precisely, we show that the distance rescaled by loglog N 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 Chung-Lu model for which the degree distribution has a power law tail.
Original languageEnglish
Number of pages38
JournalInternet Mathematics
DOIs
Publication statusPublished - 15 Aug 2017

Fingerprint

Dive into the research topics of 'Typical distances in a geometric model for complex networks'. Together they form a unique fingerprint.

Cite this