The Degree Distribution of Thickened Trees

Abstract

We develop a combinatorial structure to serve as model of random real world networks. Starting with plane oriented recursive trees we substitute the nodes by more complex graphs. In such a way we obtain graphs having a global tree-like structure while locally looking clustered. This fits with observations obtained from real-world networks. In particular we show that the resulting graphs are scale-free, that is, the degree distribution has an asymptotic power law.

Keywords

• scale free networks
• recursive trees
• generating functions
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-ds] mathematics [math]/dynamical systems [math.ds]
• [math.math-co] mathematics [math]/combinatorics [math.co]