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
NULL##NULL
Alois Panholzer;Georg Seitz
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)