Alois Panholzer ; Georg Seitz - Ordered increasing k-trees: Introduction and analysis of a preferential attachment network model

dmtcs:2778 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2778
Ordered increasing k-trees: Introduction and analysis of a preferential attachment network modelConference paper

Authors: Alois Panholzer 1; Georg Seitz 1

  • 1 Institut für Diskrete Mathematik und Geometrie [Wien]

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.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: network model,increasing k-trees,degree distribution,local clustering coefficient,root-to-node distances,limiting distributions,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

2 Documents citing this article

Consultation statistics

This page has been seen 271 times.
This article's PDF has been downloaded 238 times.