Degrees and distances in random and evolving Apollonian networks

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

Onderzoeksoutput: Boek/rapportRapportAcademic

65 Downloads (Pure)

Uittreksel

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-2Engels
Plaats van productieEindhoven
UitgeverijEurandom
Aantal pagina's21
StatusGepubliceerd - 2013

Publicatie series

NaamReport Eurandom
Volume2013029
ISSN van geprinte versie1389-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).

Onderzoeksoutput: Boek/rapportRapportAcademic

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).