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 a reticular edge and a tree edge.(A) The part of the network containing the two edges being transposed. The brown, blue, and green triangles (and edges) denote the subtrees adjacent to the edges. (B) The effect of the transposition on the structure of the spanning tree and its hierarchical levels.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368924&req=5

pone-0036715-g006: Effect of a single transposition of a reticular edge and a tree edge.(A) The part of the network containing the two edges being transposed. The brown, blue, and green triangles (and edges) denote the subtrees adjacent to the edges. (B) The effect of the transposition on the structure of the spanning tree and its hierarchical levels.

Mentions: is a reticular edge and is a tree edge. Let and be the two faces merged by removing . Notice that there will be no changes in the structure of or if is not adjacent to both and . So, let be adjacent to and . Then removing before merges the same and , so no changes to the structure of the co-tree happen. However, turns into a reticular edges, and becomes a tree edge. Consequently, the structure of the spanning tree changes. Let be the set of edges incident to both and , and let be the tree formed by the edges in and the edges connected to and having only or as an adjacent face (see Fig. 6). Removing and splits into three trees, , , and , such that and are connected to the boundary of , and is not (Fig. 6). If is removed before , then is connected to by . However, if the transposition happens and is removed before , then is connected to by (Fig. 6). To understand the effect of such a change on hierarchical levels, we first assume that does not contain the root of . Let be the vertex incident to and , and let be the vertex incident to and . Also, let , where is regarded as an edge in rooted at , and let , where is regarded as an edge in rooted at . Denote by the edge of which is next to in the path from to the root of , and by the edge of which is next to in the path from to the root of . Then we can see that removing before can decrease the level of by at most . At the same time, the level of can increase by at most . In the worst case, these changes can propagate up all the way to the root. The case when the root of belongs to can lead to more drastic changes. In this case, removing before leads to recomputing levels of all edges in by changing the root from to . Again, this change can then propagate further to the root of .


Hierarchical ordering of reticular networks.

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

Effect of a single transposition of a reticular edge and a tree edge.(A) The part of the network containing the two edges being transposed. The brown, blue, and green triangles (and edges) denote the subtrees adjacent to the edges. (B) The effect of the transposition on the structure of the spanning tree and its hierarchical levels.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0036715-g006: Effect of a single transposition of a reticular edge and a tree edge.(A) The part of the network containing the two edges being transposed. The brown, blue, and green triangles (and edges) denote the subtrees adjacent to the edges. (B) The effect of the transposition on the structure of the spanning tree and its hierarchical levels.
Mentions: is a reticular edge and is a tree edge. Let and be the two faces merged by removing . Notice that there will be no changes in the structure of or if is not adjacent to both and . So, let be adjacent to and . Then removing before merges the same and , so no changes to the structure of the co-tree happen. However, turns into a reticular edges, and becomes a tree edge. Consequently, the structure of the spanning tree changes. Let be the set of edges incident to both and , and let be the tree formed by the edges in and the edges connected to and having only or as an adjacent face (see Fig. 6). Removing and splits into three trees, , , and , such that and are connected to the boundary of , and is not (Fig. 6). If is removed before , then is connected to by . However, if the transposition happens and is removed before , then is connected to by (Fig. 6). To understand the effect of such a change on hierarchical levels, we first assume that does not contain the root of . Let be the vertex incident to and , and let be the vertex incident to and . Also, let , where is regarded as an edge in rooted at , and let , where is regarded as an edge in rooted at . Denote by the edge of which is next to in the path from to the root of , and by the edge of which is next to in the path from to the root of . Then we can see that removing before can decrease the level of by at most . At the same time, the level of can increase by at most . In the worst case, these changes can propagate up all the way to the root. The case when the root of belongs to can lead to more drastic changes. In this case, removing before leads to recomputing levels of all edges in by changing the root from to . Again, this change can then propagate further to the root of .

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