The Degree Distribution of Random k-Trees
arXiv:0808.0202 · doi:10.1016/j.tcs.2008.10.015
Abstract
A power law degree distribution is established for a graph evolution model based on the graph class of k-trees. This k-tree-based graph process can be viewed as an idealized model that captures some characteristics of the preferential attachment and copying mechanisms that existing evolving graph processes fail to model due to technical obstacles. The result also serves as a further cautionary note reinforcing the point of view that a power law degree distribution should not be regarded as the only important characteristic of a complex network, as has been previously argued.
References in corpus (3)
Cited by in corpus (11)
- Scalable Betweenness Centrality Maximization via Sampling
- Mathematical and Algorithmic Analysis of Network and Biological Data
- Elliptic Flow at Large Viscosity
- Generalized Belief Propagation on Tree Robust Structured Region Graphs
- The connectivity-profile of random increasing k-trees
- Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs
- Characterizing several properties of high-dimensional random Apollonian networks
- The Degree Sequence of Random Apollonian Networks
- High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks
- Randomized Rumor Spreading in Poorly Connected Small-World Networks
- Statistical Behavior of Embeddedness and Communities of Overlapping Cliques in Online Social Networks