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

Examples of networks with hierarchical structure.A common “root” or outlet denoted by the red dot at the bottom of each network: (A) Horton-Strahler stream order of branch hierarchy in a tree network; (B) Reticular network with possible loop hierarchy: the, blue, dashed loop might be less important than the red, dotted loop; (C) Reticular network of (B) with weights.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368924&req=5

pone-0036715-g001: Examples of networks with hierarchical structure.A common “root” or outlet denoted by the red dot at the bottom of each network: (A) Horton-Strahler stream order of branch hierarchy in a tree network; (B) Reticular network with possible loop hierarchy: the, blue, dashed loop might be less important than the red, dotted loop; (C) Reticular network of (B) with weights.

Mentions: We start by reviewing the algorithm for constructing the Horton-Strahler order. For the remainder of the paper, we shall adopt the language of graph theory [53], [54]. Note that in graph theory, the “leaves” of the network are those vertices which only have a single edge that connects to them. In this context, the input to the Horton-Strahler ordering algorithm is a rooted tree, , where V is the set of vertices and E is the set of edges. Given such a tree, the algorithm assigns a level, , to each edge in the following way. First, assign level 1 to all edges connected to the leaves of T. Next, for each vertex having only one incident edge, e, with undefined , let l be the maximal level among the other incident edges. If there is a single incident edge of level l, then . If there are two or more incident edges of level l, then . The result of this algorithm is illustrated in Fig. 1A. Conventionally in the study of river networks [42], this algorithm can be summarized by a single rule which states that the order of a downstream segment is equal to(1)where and are the order of the two upstream segments that are merging and is the Kronecker delta.


Hierarchical ordering of reticular networks.

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

Examples of networks with hierarchical structure.A common “root” or outlet denoted by the red dot at the bottom of each network: (A) Horton-Strahler stream order of branch hierarchy in a tree network; (B) Reticular network with possible loop hierarchy: the, blue, dashed loop might be less important than the red, dotted loop; (C) Reticular network of (B) with weights.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0036715-g001: Examples of networks with hierarchical structure.A common “root” or outlet denoted by the red dot at the bottom of each network: (A) Horton-Strahler stream order of branch hierarchy in a tree network; (B) Reticular network with possible loop hierarchy: the, blue, dashed loop might be less important than the red, dotted loop; (C) Reticular network of (B) with weights.
Mentions: We start by reviewing the algorithm for constructing the Horton-Strahler order. For the remainder of the paper, we shall adopt the language of graph theory [53], [54]. Note that in graph theory, the “leaves” of the network are those vertices which only have a single edge that connects to them. In this context, the input to the Horton-Strahler ordering algorithm is a rooted tree, , where V is the set of vertices and E is the set of edges. Given such a tree, the algorithm assigns a level, , to each edge in the following way. First, assign level 1 to all edges connected to the leaves of T. Next, for each vertex having only one incident edge, e, with undefined , let l be the maximal level among the other incident edges. If there is a single incident edge of level l, then . If there are two or more incident edges of level l, then . The result of this algorithm is illustrated in Fig. 1A. Conventionally in the study of river networks [42], this algorithm can be summarized by a single rule which states that the order of a downstream segment is equal to(1)where and are the order of the two upstream segments that are merging and is the Kronecker delta.

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