### Uittreksel

Originele taal-2 | Engels |
---|---|

Plaats van productie | Eindhoven |

Uitgeverij | Eurandom |

Aantal pagina's | 21 |

Status | Gepubliceerd - 2013 |

### Publicatie series

Naam | Report Eurandom |
---|---|

Volume | 2013029 |

ISSN van geprinte versie | 1389-2355 |

### Vingerafdruk

### Citeer dit

*Degrees and distances in random and evolving Apollonian networks*. (Report Eurandom; Vol. 2013029). Eindhoven: Eurandom.

}

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

Onderzoeksoutput: Boek/rapport › Rapport › Academic

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 -