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

Related in: MedlinePlus

Strahler bifurcation ratio for the various generated, optimized and natural graphs.Red error bar: standard error of the linear regression fit (represents goodness of linear fit). Black error bar: standard deviation of the logarithm of the bifurcation ratio (average over 20 realizations). Insets: Number of Strahler streams  of order  as a function of  for the random lines, nested and gradient model and the Bursera leaf. Note that in each case, the  follows closely an inverse geometric progression with  (shown with the red dashed line).
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g010: Strahler bifurcation ratio for the various generated, optimized and natural graphs.Red error bar: standard error of the linear regression fit (represents goodness of linear fit). Black error bar: standard deviation of the logarithm of the bifurcation ratio (average over 20 realizations). Insets: Number of Strahler streams of order as a function of for the random lines, nested and gradient model and the Bursera leaf. Note that in each case, the follows closely an inverse geometric progression with (shown with the red dashed line).

Mentions: The Strahler bifurcation ratio (10) (discussed in the Methods section), when computed on the nesting tree can provide a metric to quantify the overall nestedness of graphs. It is defined as the ratio of the number of streams of order to the number of streams of order . Since the Strahler law of stream numbers is an inevitable reality for most trees, it is possible to fit the plots versus with a straight line the slope of which will determine the logarithm of the Strahler bifurcation ratio for the whole graph. Examples of this fit are shown in the inset of Fig. 10. The best fit is found in the least squares sense, and it is forced to pass through ( is equal to the total number of ultimate loops, or leaf nodes in the nesting tree). The data point for is discarded, as it is very sensitive to noise.


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Strahler bifurcation ratio for the various generated, optimized and natural graphs.Red error bar: standard error of the linear regression fit (represents goodness of linear fit). Black error bar: standard deviation of the logarithm of the bifurcation ratio (average over 20 realizations). Insets: Number of Strahler streams  of order  as a function of  for the random lines, nested and gradient model and the Bursera leaf. Note that in each case, the  follows closely an inverse geometric progression with  (shown with the red dashed line).
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037994-g010: Strahler bifurcation ratio for the various generated, optimized and natural graphs.Red error bar: standard error of the linear regression fit (represents goodness of linear fit). Black error bar: standard deviation of the logarithm of the bifurcation ratio (average over 20 realizations). Insets: Number of Strahler streams of order as a function of for the random lines, nested and gradient model and the Bursera leaf. Note that in each case, the follows closely an inverse geometric progression with (shown with the red dashed line).
Mentions: The Strahler bifurcation ratio (10) (discussed in the Methods section), when computed on the nesting tree can provide a metric to quantify the overall nestedness of graphs. It is defined as the ratio of the number of streams of order to the number of streams of order . Since the Strahler law of stream numbers is an inevitable reality for most trees, it is possible to fit the plots versus with a straight line the slope of which will determine the logarithm of the Strahler bifurcation ratio for the whole graph. Examples of this fit are shown in the inset of Fig. 10. The best fit is found in the least squares sense, and it is forced to pass through ( is equal to the total number of ultimate loops, or leaf nodes in the nesting tree). The data point for is discarded, as it is very sensitive to noise.

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
Related in: MedlinePlus