Complexity of Hierarchical Systems

Consider, for definiteness, a set of otherwise identical lowest-level components of a system, so that the hierarchy is a tree of constant depth. Since we assume that the components are all identical, the only distinction among the various nodes of the hierarchy consists of the structure of the subtrees. Now suppose we have a tree T that consists of /3 subtrees branching out from the root at the top level. We need to determine the number of different interactions that can occur on each level, independent of the structure of each subtree i.e. isomorphic copies of trees do not contribute to our count. We therefore need to find the number of nonisomorphic subtrees. We can do this recursively. 

The diversity of the tree T, denoted by V(T), counts the total number of interactions between and within all subtrees. We therefore proceed in two steps. First count the number of distinct interactions within the clusters represented by the subtrees i.e. multiply the diversity of all nonisomorphic subtrees. Second, multiply this result by the number of ways, N, that k different clusters 

For example, consider the two trees shown in figure 12.4. The tree in figure 12.4-a has equal (binary) subtrees, so that its diversity V = 1 and complexity C = 0. The same is true for any tree all of whose nodes have a constant branching ratio. On the other hand, the tree shown in figure 12.4-b has two distinct subtrees, each of which has a diversity of 2 = 1. The diversity of the entire tree is therefore X) = 22 - 1 = 3. 

Huberman and Hogg ([liuber85b], [huber86j) extend this measure to metric trees (where the height of the roots of sub trees from their leaves is an added parameter) 

---