Skip to Main content Skip to Navigation
Conference papers

Ordered increasing $k$-trees: Introduction and analysis of a preferential attachment network model

Abstract : We introduce a random graph model based on $k$-trees, which can be generated by applying a probabilistic preferential attachment rule, but which also has a simple combinatorial description. We carry out a precise distributional analysis of important parameters for the network model such as the degree, the local clustering coefficient and the number of descendants of the nodes and root-to-node distances. We do not only obtain results for random nodes, but in particular we also get a precise description of the behaviour of parameters for the $j$-th inserted node in a random $k$-tree of size $n$, where $j=j(n)$ might grow with $n$. The approach presented is not restricted to this specific $k$-tree model, but can also be applied to other evolving $k$-tree models.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185576
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:32:43 PM
Last modification on : Tuesday, March 7, 2017 - 3:07:55 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:12:00 AM

File

dmAM0138.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185576, version 1

Collections

Citation

Alois Panholzer, Georg Seitz. Ordered increasing $k$-trees: Introduction and analysis of a preferential attachment network model. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.549-564. ⟨hal-01185576⟩

Share

Metrics

Record views

118

Files downloads

542