Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

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

Identifiers

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⟩

Share

Metrics

Record views

193

Files downloads

428