Limits...
Hierarchical ordering of reticular networks.

Mileyko Y, Edelsbrunner H, Price CA, Weitz JS - PLoS ONE (2012)

Bottom Line: In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations.In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges.We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.

View Article: PubMed Central - PubMed

Affiliation: Department of Mathematics, Duke University, Durham, North Carolina, United States of America. yury@math.duke.edu

ABSTRACT
The structure of hierarchical networks in biological and physical systems has long been characterized using the Horton-Strahler ordering scheme. The scheme assigns an integer order to each edge in the network based on the topology of branching such that the order increases from distal parts of the network (e.g., mountain streams or capillaries) to the "root" of the network (e.g., the river outlet or the aorta). However, Horton-Strahler ordering cannot be applied to networks with loops because they they create a contradiction in the edge ordering in terms of which edge precedes another in the hierarchy. Here, we present a generalization of the Horton-Strahler order to weighted planar reticular networks, where weights are assumed to correlate with the importance of network edges, e.g., weights estimated from edge widths may correlate to flow capacity. Our method assigns hierarchical levels not only to edges of the network, but also to its loops, and classifies the edges into reticular edges, which are responsible for loop formation, and tree edges. In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations. In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges. We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.

Show MeSH

Related in: MedlinePlus

Example of the two extreme cases of the loop hierarchy.The network has m faces, where  for some integer .  of these faces are adjacent squares and the other one is the unbounded face. Vertical edges are removed before horizontal edges as follows: (A) The edges are removed sequentially from left to right. The corresponding co-tree has the shape of a “comb” and the maximal hierarchical level is 2; (B) The edges are removed from left to right skipping every second edge. The process is repeated until all vertical edges except the rightmost one are removed. The corresponding co-tree has the height  which is the maximal hierarchical level.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368924&req=5

pone-0036715-g004: Example of the two extreme cases of the loop hierarchy.The network has m faces, where for some integer . of these faces are adjacent squares and the other one is the unbounded face. Vertical edges are removed before horizontal edges as follows: (A) The edges are removed sequentially from left to right. The corresponding co-tree has the shape of a “comb” and the maximal hierarchical level is 2; (B) The edges are removed from left to right skipping every second edge. The process is repeated until all vertical edges except the rightmost one are removed. The corresponding co-tree has the height which is the maximal hierarchical level.

Mentions: We start by considering the worst possible change in the hierarchical levels of loops. Notice that the highest level in the hierarchy of loops can be as low as 2. This happens when the first reticular edge creates a level 2 face and every other reticular edge merges a level 1 face with the only level 2 face (see Fig. 4A). On the other hand, the highest level in the loop hierarchy can be as high as , where m is the number of faces. This happens when level 1 faces are merged only with level 1 faces until only faces of level 2 are left, then level 2 faces are merged with level 2 faces until only faces of level 3 are left, and so on (see Fig. 4B). It is clear from the example in Fig. 4 that there is a permutation of edges that can change the loop hierarchy from one of the extreme cases to the other. However, in practice such a permutation would generally result in from a significant perturbation in weights. For small perturbations, it is more likely that only a few transpositions of edges will occur.


Hierarchical ordering of reticular networks.

Mileyko Y, Edelsbrunner H, Price CA, Weitz JS - PLoS ONE (2012)

Example of the two extreme cases of the loop hierarchy.The network has m faces, where  for some integer .  of these faces are adjacent squares and the other one is the unbounded face. Vertical edges are removed before horizontal edges as follows: (A) The edges are removed sequentially from left to right. The corresponding co-tree has the shape of a “comb” and the maximal hierarchical level is 2; (B) The edges are removed from left to right skipping every second edge. The process is repeated until all vertical edges except the rightmost one are removed. The corresponding co-tree has the height  which is the maximal hierarchical level.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3368924&req=5

pone-0036715-g004: Example of the two extreme cases of the loop hierarchy.The network has m faces, where for some integer . of these faces are adjacent squares and the other one is the unbounded face. Vertical edges are removed before horizontal edges as follows: (A) The edges are removed sequentially from left to right. The corresponding co-tree has the shape of a “comb” and the maximal hierarchical level is 2; (B) The edges are removed from left to right skipping every second edge. The process is repeated until all vertical edges except the rightmost one are removed. The corresponding co-tree has the height which is the maximal hierarchical level.
Mentions: We start by considering the worst possible change in the hierarchical levels of loops. Notice that the highest level in the hierarchy of loops can be as low as 2. This happens when the first reticular edge creates a level 2 face and every other reticular edge merges a level 1 face with the only level 2 face (see Fig. 4A). On the other hand, the highest level in the loop hierarchy can be as high as , where m is the number of faces. This happens when level 1 faces are merged only with level 1 faces until only faces of level 2 are left, then level 2 faces are merged with level 2 faces until only faces of level 3 are left, and so on (see Fig. 4B). It is clear from the example in Fig. 4 that there is a permutation of edges that can change the loop hierarchy from one of the extreme cases to the other. However, in practice such a permutation would generally result in from a significant perturbation in weights. For small perturbations, it is more likely that only a few transpositions of edges will occur.

Bottom Line: In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations.In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges.We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.

View Article: PubMed Central - PubMed

Affiliation: Department of Mathematics, Duke University, Durham, North Carolina, United States of America. yury@math.duke.edu

ABSTRACT
The structure of hierarchical networks in biological and physical systems has long been characterized using the Horton-Strahler ordering scheme. The scheme assigns an integer order to each edge in the network based on the topology of branching such that the order increases from distal parts of the network (e.g., mountain streams or capillaries) to the "root" of the network (e.g., the river outlet or the aorta). However, Horton-Strahler ordering cannot be applied to networks with loops because they they create a contradiction in the edge ordering in terms of which edge precedes another in the hierarchy. Here, we present a generalization of the Horton-Strahler order to weighted planar reticular networks, where weights are assumed to correlate with the importance of network edges, e.g., weights estimated from edge widths may correlate to flow capacity. Our method assigns hierarchical levels not only to edges of the network, but also to its loops, and classifies the edges into reticular edges, which are responsible for loop formation, and tree edges. In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations. In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges. We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.

Show MeSH
Related in: MedlinePlus