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

Effect of a single transposition of two reticular edges.(A) the part of the network containing the two edges being transposed and the effect of the transposition on the structure of the co-tree; (B) possible level changes caused by the transposition.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368924&req=5

pone-0036715-g005: Effect of a single transposition of two reticular edges.(A) the part of the network containing the two edges being transposed and the effect of the transposition on the structure of the co-tree; (B) possible level changes caused by the transposition.

Mentions: and are both reticular. Only the co-tree can be affected in this case. Let , and , be the faces merged by removing and , respectively. Also, let and . Notice that if and , then is not a child of in ), and there will be no changes to the structure of the co-tree. Suppose that (the case when follows the same argument). Then is adjacent to either or ; let us assume it’s . Removing before leads to merging with first, and then merging the resulting face with . The corresponding change in the tree structure, shown in Fig. 5, is a single rotation around . Possible changes in the levels of the nodes involved in the rotation are also shown in Fig. 5. We can see that these levels can change at most by one. However, in the worst case the change in levels may propagate up all the way to the root.


Hierarchical ordering of reticular networks.

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

Effect of a single transposition of two reticular edges.(A) the part of the network containing the two edges being transposed and the effect of the transposition on the structure of the co-tree; (B) possible level changes caused by the transposition.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0036715-g005: Effect of a single transposition of two reticular edges.(A) the part of the network containing the two edges being transposed and the effect of the transposition on the structure of the co-tree; (B) possible level changes caused by the transposition.
Mentions: and are both reticular. Only the co-tree can be affected in this case. Let , and , be the faces merged by removing and , respectively. Also, let and . Notice that if and , then is not a child of in ), and there will be no changes to the structure of the co-tree. Suppose that (the case when follows the same argument). Then is adjacent to either or ; let us assume it’s . Removing before leads to merging with first, and then merging the resulting face with . The corresponding change in the tree structure, shown in Fig. 5, is a single rotation around . Possible changes in the levels of the nodes involved in the rotation are also shown in Fig. 5. We can see that these levels can change at most by one. However, in the worst case the change in levels may propagate up all the way to the root.

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