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 <>
Submitted on : Monday, August 17, 2015 - 4:58:48 PM
Last modification on : Tuesday, January 12, 2021 - 9:36:03 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:14:44 PM

File

dmAH0124.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184769, version 1

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. ⟨hal-01184769⟩

Share

Metrics

Record views

318

Files downloads

662