Limits...
Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Bottom Line: We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph.We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex.This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.

View Article: PubMed Central - PubMed

Affiliation: Center for Studies in Physics and Biology, The Rockefeller University, New York, New York, United States of America. ekatifori@rockefeller.edu

ABSTRACT
Biology presents many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture containing closed loops at many different levels. Although a number of approaches have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex. We calculate various metrics based on the asymmetry, the cumulative size distribution and the Strahler bifurcation ratios of the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.

Show MeSH
Digitized arterial vasculature of rat neocortex and corresponding nesting tree representation.(a)The arterial network forms a planar graph. Different segments of the network, as identified by hierarchical decomposition are represented by different colors. (b) Nesting tree of the digitized network. the highlighted segments of the network are color-coded.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g011: Digitized arterial vasculature of rat neocortex and corresponding nesting tree representation.(a)The arterial network forms a planar graph. Different segments of the network, as identified by hierarchical decomposition are represented by different colors. (b) Nesting tree of the digitized network. the highlighted segments of the network are color-coded.

Mentions: The analysis and framework presented in this work can be useful not only for leaves, but any other, biological or man made, planar graphs. A notable example is the arterial vasculature of the rodent neocortex which forms a planar network with multiple loops [3]. We extracted the diameters of the arterial blood vessels from a composite rat brain image provided to us by the Kleinfeld group in UCSD and augmented the connectivity information in [3] to obtain a weighted map of the arterial vasculature of the rat brain, as seen in Fig. 11(a). Although the resolution of the image in our disposal does not allow us to determine the vein widths with absolute confidence, we were able to identify major vascular sectors and determine that, according to the data at hand and the corresponding nesting trees shown in Fig. 11(b), the architecture of the network in question is primarily additive. Five sectors in Fig. 11(a) and their associated nesting subtrees are shown in color.


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Digitized arterial vasculature of rat neocortex and corresponding nesting tree representation.(a)The arterial network forms a planar graph. Different segments of the network, as identified by hierarchical decomposition are represented by different colors. (b) Nesting tree of the digitized network. the highlighted segments of the network are color-coded.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037994-g011: Digitized arterial vasculature of rat neocortex and corresponding nesting tree representation.(a)The arterial network forms a planar graph. Different segments of the network, as identified by hierarchical decomposition are represented by different colors. (b) Nesting tree of the digitized network. the highlighted segments of the network are color-coded.
Mentions: The analysis and framework presented in this work can be useful not only for leaves, but any other, biological or man made, planar graphs. A notable example is the arterial vasculature of the rodent neocortex which forms a planar network with multiple loops [3]. We extracted the diameters of the arterial blood vessels from a composite rat brain image provided to us by the Kleinfeld group in UCSD and augmented the connectivity information in [3] to obtain a weighted map of the arterial vasculature of the rat brain, as seen in Fig. 11(a). Although the resolution of the image in our disposal does not allow us to determine the vein widths with absolute confidence, we were able to identify major vascular sectors and determine that, according to the data at hand and the corresponding nesting trees shown in Fig. 11(b), the architecture of the network in question is primarily additive. Five sectors in Fig. 11(a) and their associated nesting subtrees are shown in color.

Bottom Line: We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph.We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex.This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.

View Article: PubMed Central - PubMed

Affiliation: Center for Studies in Physics and Biology, The Rockefeller University, New York, New York, United States of America. ekatifori@rockefeller.edu

ABSTRACT
Biology presents many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture containing closed loops at many different levels. Although a number of approaches have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex. We calculate various metrics based on the asymmetry, the cumulative size distribution and the Strahler bifurcation ratios of the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.

Show MeSH