HORTON LAW IN SELF-SIMILAR TREES

作者：Kovchegov Yevgeniy^*; Zaliapin Ilya

来源：Fractals-Complex Geometry Patterns and Scaling in Nature and Society, 2016, 24(2): 1650017.

DOI：10.1142/S0218348X16500171

• Random Trees
• Horton Law
• Tokunaga Self-Similarity

Self-similarity of random trees is related to the operation of pruning. Pruning R cuts the leaves and their parental edges and removes the resulting chains of degree-two nodes from a finite tree. A Horton-Strahler order of a vertex v and its parental edge is defined as the minimal number of prunings necessary to eliminate the subtree rooted at v. A branch is a group of neighboring vertices and edges of the same order. The Horton numbers N-k[K] and N-ij[K] are defined as the expected number of branches of order k, and the expected number of order-i branches that merged order-j branches, j > i, respectively, in a finite tree of order K. The Tokunaga coefficients are defined as T-ij[K] = N-ij [K]/N-j[K]. The pruning decreases the orders of tree vertices by unity. A rooted full binary tree is said to be mean-self-similar if its Tokunaga coefficients are invariant with respect to pruning: T-k := T-i,T- i+k[K]. We show that for self-similar trees, the condition lim sup(k ->infinity) T-k(1/k) < infinity is necessary and sufficient for the existence of the strong Horton law: N-k[K]/N-1[K] -> R1-k, as K -> 8 for some R > 0 and every k >= 1. This work is a step toward providing rigorous foundations for the Horton law that, being omnipresent in natural branching systems, has escaped so far a formal explanation.

• 出版日期2016-6