Degrees and distances in random and evolving Apollonian networks

István Kolossváry, Júlia Komjáthy;, Lajos Vágó

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

In this paper we study random Apollonian networks (RANs) and evolving Apollonian networks (EANs), in d dimensions for any d≥2, i.e. dynamically evolving random d-dimensional simplices, looked at as graphs inside an initial d-dimensional simplex. We determine the limiting degree distribution in RANs and show that it follows a power-law tail with exponent τ=(2d-1)/(d-1). We further show that the degree distribution in EANs converges to the same degree distribution if the simplex-occupation parameter in the nth step of the dynamics tends to 0 but is not summable in n. This result gives a rigorous proof for the conjecture of Zhang et al. (2006) that EANs tend to exhibit similar behaviour as RANs once the occupation parameter tends to 0. We also determine the asymptotic behaviour of the shortest paths in RANs and EANs for any d≥2. For RANs we show that the shortest path between two vertices chosen u.a.r. (typical distance), the flooding time of a vertex chosen uniformly at random, and the diameter of the graph after n steps all scale as a constant multiplied by log n. We determine the constants for all three cases and prove a central limit theorem for the typical distances. We prove a similar central limit theorem for typical distances in EANs.
Original languageEnglish
Pages (from-to)865-902
Number of pages38
JournalAdvances in Applied Probability
Volume48
Issue number3
Early online date19 Sept 2016
DOIs
Publication statusPublished - Sept 2016

Keywords

  • Random graph
  • Random network
  • Typical distance
  • Diameter
  • Hopcount
  • Degree distribution

Fingerprint

Dive into the research topics of 'Degrees and distances in random and evolving Apollonian networks'. Together they form a unique fingerprint.

Cite this