# Degree distribution of random Apollonian network structures and Boltzmann sampling

Abstract : Random Apollonian networks have been recently introduced for representing real graphs. In this paper we study a modified version: random Apollonian network structures (RANS), which preserve the interesting properties of real graphs and can be handled with powerful tools of random generation. We exhibit a bijection between RANS and ternary trees, that transforms the degree of nodes in a RANS into the size of particular subtrees. The distribution of degrees in RANS can thus be analysed within a bivariate Boltzmann model for the generation of random trees, and we show that it has a Catalan form which reduces to a power law with an exponential cutoff: $α ^k k^{-3/2}$, with $α = 8/9$. We also show analogous distributions for the degree in RANS of higher dimension, related to trees of higher arity.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [9 references]

https://hal.inria.fr/hal-01184769
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 4:58:48 PM
Last modification on : Sunday, June 26, 2022 - 5:18:54 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:14:44 PM

### File

dmAH0124.pdf
Publisher files allowed on an open archive

### Citation

Alexis Darrasse, Michèle Soria. Degree distribution of random Apollonian network structures and Boltzmann sampling. 2007 Conference on Analysis of Algorithms, AofA 07, Jun 2007, Juan les Pins, France. pp.313-324, ⟨10.46298/dmtcs.3521⟩. ⟨hal-01184769⟩

Record views