Degrees and distances in random and evolving Apollonian networks

I. Kolossváry, J. Komjáthy, L. Vágó

Research output: Book/ReportReportAcademic

86 Downloads (Pure)

Abstract

This paper studies Random and Evolving Apollonian networks (RANs and EANs), in d dimension for any d = 2, i.e. dynamically evolving random d dimensional simplices looked 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 t = (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 is $q_n \rightarrow 0$ and \sum_{n=0}^\infty q_n = \infty$. This result gives a rigorous proof for the conjecture of Zhang et al [31] that EANs tend to show similar behavior as RANs once the occupation parameter $q \rightarrow 0$. We also determine the asymptotic behavior of shortest paths in RANs and EANs for arbitrary d dimensions. For RANs we show that the shortest path between two uniformly chosen vertices (typical distance), the flooding time of a uniformly picked vertex and the diameter of the graph after n steps all scale as constant times log n. We determine the constants for all three cases and prove a central limit theorem for the typical distances. We prove a similar CLT for typical distances in EANs.
Original languageEnglish
Place of PublicationEindhoven
PublisherEurandom
Number of pages21
Publication statusPublished - 2013

Publication series

NameReport Eurandom
Volume2013029
ISSN (Print)1389-2355

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

Cite this