It is October. Very soon the inspiring canvas of the Fall foliage will be gone and we will raise our eyes once in a while to enjoy an unexplained beauty of the branched architecture of the naked trees. Yet, there might be more than a shear aesthetic pleasure in those views and this is what today’s blog is about.
The Nature exhibits many branching tree-like structures beyond the botanical trees. River networks, Martian drainage basins, veins of botanical leaves, lung and blood systems, and lightening all can be represented as tree graphs. Besides, a number of dynamic processes like spread of a disease or rumor, evolution of an earthquake aftershock sequence, or transfer of gene characteristics from parent to children also can be described by a (time-oriented) tree. This would sound as a trivial observation if not for the following fact. A majority of rigorously studied branching structures is shown to be closely approximated by a simple two-parametric statistical model, a Tokunaga self-similar (TSS) tree. In other words, apparently diverse branching phenomena (think of Mississippi river vs. a birch tree) are statistically similar to each other, with the observed differences being related to the value of a particular model parameter rather than qualitative structural traits.
There exist two important types of self-similarity for trees. They are related to the Horton-Strahler and Tokunaga indexing schemes for tree branches. Introduced in hydrology in the mid 20-th century to describe the dendritic structure of river networks these schemes have been rediscovered and used in other applied fields since then.
We give below some definitions, which do not affect the later parts of this blog and can be safely skipped.
The Horton-Strahler indexing assigns orders to the tree branches according to their relative importance in the hierarchy. Namely, for a rooted tree T we consider the operation of pruning – cutting the leaves as well as the single-child chains of vertices that contain a leaf. Clearly, consecutive application of pruning eliminates any finite tree in a finite number of steps. A vertex in T is assigned order r if it is removed from the tree during the r-th application of pruning. A branch is a sequence of adjacent vertices with the same order.
Quite often, observed systems exhibit geometric decrease of the numbers Nr of branches of Horton-Strahler order r ³ 1; this property is called Horton self-similarity. The common ratio R of the respective geometric series is called the Horton exponent.
A stronger Tokunaga self-similarity addresses so-called side branching – merging of branches of distinct orders. In a Tokunaga tree, the average number of branches of order i ≥ 1 that join a branch of order (i+k), k ≥ 1 is given by Tk = ack-1. The positive numbers (a,c) are called Tokunaga parameters. Informally, the Tokunaga self-similarity implies that different levels of a hierarchical system have the same statistical structure, as is signified by the fact that Tk depends on the difference k between the child and parental branch orders but not on their absolute values.
A classical model that exhibits Horton and Tokunaga self-similarity is the critical binary Galton-Watson branching process (Burd et al., 2000), also known in hydrology as Shreve’s random topology model. This model has R = 4 and (a,c) = (1,2).
The general interest to fractals and self-similar structures in natural sciences during the 1990s led to a quest, mainly inspired and led by Donald Turcotte, for Tokunaga self-similar tree graphs of diverse origin. As a result, the Horton and Tokunaga self-similarity with a broad range of respective parameters have been empirically or rigorously established in numerous observed and modeled systems, well beyond river networks. This includes botanical trees, vein structure of botanical leaves, diffusion limited aggregation, two dimensional site percolation, nearest-neighbor clustering in Euclidean spaces, earthquake aftershock series, dynamics of billiards and some others (e.g., Newman et al., 1997; Turcotte et al., 1998; Kovchegov and Zaliapin, 2013 and references therein).
The increasing empirical evidence prompts the question: What basic probability models can generate Tokunaga self-similar trees with a range of parameters? (Or, more informally, do we see Tokunaga trees everywhere because of our inability to reject the Tokunaga hypothesis, or because of actual importance of the Tokunaga constraint?)
Burd et al. (2000) demonstrated that Tokunaga self-similarity is a characteristic property of the critical binary branching in the broad class of (not necessarily binary) Galton-Watson processes. Recently, Zaliapin and Kovchegov (2012) studied the level-set tree representation of time series (an inverse of the Harris path) and established Horton and Tokunaga self-similarity of a symmetric random walk and a regular Brownian motion. They also demonstrated Horton self-similarity of the Kingman’s coalescent process, and presented the respective Tokunaga self-similarity as a numerical conjecture (Kovchegov and Zaliapin, 2013). Other recent numerical experiments suggest that multiplicative and additive coalescents, as well as fractional Brownian motions also correspond to Tokunaga self-similar trees.
These results (i) expand the class of Horton and Tokunaga self-similar processes beyond the critical binary Galton-Watson branching, and (ii) suggest that simple models of branching, aggregation, and time series generically lead to the Tokunaga self-similarity. This makes the omnipresence of Tokunaga trees in observations less mysterious and opens an interesting avenue for further research. In particular, the equivalence of different processes via their respective tree representation (as is the case for Kingman’s coalescent and white noise, see Zaliapin and Kovchegov (2013)) may broaden the toolbox of empirical and theoretical exploration of various branching phenomena.
References:
G. A. Burd, E.C. Waymire, R.D. Winn, A self-similar invariance of critical binary Galton-Watson trees, Bernoulli, 6 (2000) 1–21.
Y. Kovchegov and I. Zaliapin, Horton self-similarity of Kingman’s coalescent tree, arXiv:1207.7108, 2013
W. I. Newman, D.L. Turcotte, A.M. Gabrielov, Fractal trees with side branching, Fractals, 5 (1997) 603–614.
D.L. Turcotte, J.D. Pelletier, and W.I. Newman, Networks with side branching in biology, J. Theor. Biol., 193 (1998) 577–592.
I. Zaliapin and Y. Kovchegov, Tokunaga and Horton self-similarity for level set trees of Markov chains, Chaos, Solitons & Fractals, 45, Issue 3 (2012) 358–372.
Ilya Zaliapin
Associate Professor
Department of Mathematics and Statistics
University of Nevada, Reno