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 hierarchical levels.The levels are assigned to the loops and branches of the network from Fig. 1C. Edge levels are shown on the left, where black edges have order 1, light blue edges have order 2 and gold edges have order 3; reticular edges are dashed. Face levels are shown in the co-tree on the right, where white nodes have order 1, light blue nodes have order 2 and gold nodes have order 3. Leaves of the co-tree are labeled by the corresponding faces while other nodes are labeled by the reticular edges causing the merger of the two child nodes. Numbers  are Tokunaga statistics for the spanning tree and indicate the number of edges of level j joining with edges of level i[43]. Similarly,  are Tokunaga statistics for the reticulate co-tree and indicate the number of edges and faces of level j merging with edges of level i. For both M and N, statistics are only collected when .
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368924&req=5

pone-0036715-g003: Example of hierarchical levels.The levels are assigned to the loops and branches of the network from Fig. 1C. Edge levels are shown on the left, where black edges have order 1, light blue edges have order 2 and gold edges have order 3; reticular edges are dashed. Face levels are shown in the co-tree on the right, where white nodes have order 1, light blue nodes have order 2 and gold nodes have order 3. Leaves of the co-tree are labeled by the corresponding faces while other nodes are labeled by the reticular edges causing the merger of the two child nodes. Numbers are Tokunaga statistics for the spanning tree and indicate the number of edges of level j joining with edges of level i[43]. Similarly, are Tokunaga statistics for the reticulate co-tree and indicate the number of edges and faces of level j merging with edges of level i. For both M and N, statistics are only collected when .

Mentions: The construction of removes edges from G which are responsible for the existence of loops. We shall call such edges reticular. Assignment of levels for such edges is based on the assumption that a merger should not be more significant than any of the merging elements. Notice that after removing reticular edges from G we have a spanning tree of G, which we denote by . This tree captures the tree-like structure of the original network, and we can assign hierarchical levels to its edges using the original Horton-Strahler algorithm. We only need to determine which vertex should be the root, and we do this by finding the vertex with a single incident weight of maximum weight. Hence, as noted in the Methods, the final step is to aply the Horton-Strahler ordering to the remainder of the graph (which is a rooted tree). The result of the complete algorithm applied to the tree in Fig. 1C is provided in Fig. 3.


Hierarchical ordering of reticular networks.

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

Example of hierarchical levels.The levels are assigned to the loops and branches of the network from Fig. 1C. Edge levels are shown on the left, where black edges have order 1, light blue edges have order 2 and gold edges have order 3; reticular edges are dashed. Face levels are shown in the co-tree on the right, where white nodes have order 1, light blue nodes have order 2 and gold nodes have order 3. Leaves of the co-tree are labeled by the corresponding faces while other nodes are labeled by the reticular edges causing the merger of the two child nodes. Numbers  are Tokunaga statistics for the spanning tree and indicate the number of edges of level j joining with edges of level i[43]. Similarly,  are Tokunaga statistics for the reticulate co-tree and indicate the number of edges and faces of level j merging with edges of level i. For both M and N, statistics are only collected when .
© Copyright Policy
Related In: Results  -  Collection

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

pone-0036715-g003: Example of hierarchical levels.The levels are assigned to the loops and branches of the network from Fig. 1C. Edge levels are shown on the left, where black edges have order 1, light blue edges have order 2 and gold edges have order 3; reticular edges are dashed. Face levels are shown in the co-tree on the right, where white nodes have order 1, light blue nodes have order 2 and gold nodes have order 3. Leaves of the co-tree are labeled by the corresponding faces while other nodes are labeled by the reticular edges causing the merger of the two child nodes. Numbers are Tokunaga statistics for the spanning tree and indicate the number of edges of level j joining with edges of level i[43]. Similarly, are Tokunaga statistics for the reticulate co-tree and indicate the number of edges and faces of level j merging with edges of level i. For both M and N, statistics are only collected when .
Mentions: The construction of removes edges from G which are responsible for the existence of loops. We shall call such edges reticular. Assignment of levels for such edges is based on the assumption that a merger should not be more significant than any of the merging elements. Notice that after removing reticular edges from G we have a spanning tree of G, which we denote by . This tree captures the tree-like structure of the original network, and we can assign hierarchical levels to its edges using the original Horton-Strahler algorithm. We only need to determine which vertex should be the root, and we do this by finding the vertex with a single incident weight of maximum weight. Hence, as noted in the Methods, the final step is to aply the Horton-Strahler ordering to the remainder of the graph (which is a rooted tree). The result of the complete algorithm applied to the tree in Fig. 1C is provided in Fig. 3.

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