2010/03/01 by Alois Panholzer, Panholzer, Alois, Georg Seitz +1
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques #Stochastic processes and statistical mechanics #math.CO #msc:05A15 #msc:05A16 #msc:05C82
paper · pdf · doi:10.48550/arxiv.1003.0320
12 pages, 2 figures
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.