# Degrees and distances in random and evolving Apollonian networks

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

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. Originele taal-2 Engels Eindhoven Eurandom 21 Gepubliceerd - 2013 ### Publicatie series Naam Report Eurandom 2013029 1389-2355 ### Vingerafdruk Degree Distribution Shortest path Flooding Graph in graph theory Time Constant Limiting Distribution Central limit theorem Tail Power Law Asymptotic Behavior Exponent Tend Converge Arbitrary Vertex of a graph ### Citeer dit Kolossváry, I., Komjáthy, J., & Vágó, L. (2013). Degrees and distances in random and evolving Apollonian networks. (Report Eurandom; Vol. 2013029). Eindhoven: Eurandom. Kolossváry, I. ; Komjáthy, J. ; Vágó, L. / Degrees and distances in random and evolving Apollonian networks. Eindhoven : Eurandom, 2013. 21 blz. (Report Eurandom). @book{3de3fd3b2b6b47eab92d45a9e1bc1a56, title = "Degrees and distances in random and evolving Apollonian networks", 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.",
author = "I. Kolossv{\'a}ry and J. Komj{\'a}thy and L. V{\'a}g{\'o}",
year = "2013",
language = "English",
series = "Report Eurandom",
publisher = "Eurandom",

}

Kolossváry, I, Komjáthy, J & Vágó, L 2013, Degrees and distances in random and evolving Apollonian networks. Report Eurandom, vol. 2013029, Eurandom, Eindhoven.

Degrees and distances in random and evolving Apollonian networks. / Kolossváry, I.; Komjáthy, J.; Vágó, L.

Eindhoven : Eurandom, 2013. 21 blz. (Report Eurandom; Vol. 2013029).

TY - BOOK

T1 - Degrees and distances in random and evolving Apollonian networks

AU - Kolossváry, I.

AU - Komjáthy, J.

AU - Vágó, L.

PY - 2013

Y1 - 2013

N2 - 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. AB - 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.

M3 - Report

T3 - Report Eurandom

BT - Degrees and distances in random and evolving Apollonian networks

PB - Eurandom

CY - Eindhoven

ER -

Kolossváry I, Komjáthy J, Vágó L. Degrees and distances in random and evolving Apollonian networks. Eindhoven: Eurandom, 2013. 21 blz. (Report Eurandom).