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.
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, Jun 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.313-324, 2007, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184769
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:58:48
Dernière modification le : mercredi 21 mars 2018 - 18:58:15
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:14:44

Fichier

dmAH0124.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184769, version 1

Collections

Citation

Alexis Darrasse, Michèle Soria. Degree distribution of random Apollonian network structures and Boltzmann sampling. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, Jun 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.313-324, 2007, DMTCS Proceedings. 〈hal-01184769〉

Partager

Métriques

Consultations de la notice

245

Téléchargements de fichiers

83