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
Asymmetry and cumulative size distribution for two dicotyledonous leaves.(a) Asymmetry of Bursera and Protium intercostal areas. The average asymmetry  is plotted as a function of the normalized subtree degree d. Red solid line: Protium, cleaned. Red dashed line: Protium, full graph. Blue line: Bursera. Dark diamonds: random edges model. Dark circles: nested model. (b) Asymmetry of Protium intercostal segments.  is plotted as a function of the normalized subtree degree d. Black dashed line: Protium, cleaned. Red, blue, green, magenta, cyan, yellow lines: Protium segments, colorcoded as in Fig. 8. Gray squares: average of segment asymmetry with standard error. (c) Adjusted cumulative size distribution, Bursera and Protium. Red solid line: Protium, cleaned. Red dashed line: Protium, full graph. Blue line: Bursera.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g009: Asymmetry and cumulative size distribution for two dicotyledonous leaves.(a) Asymmetry of Bursera and Protium intercostal areas. The average asymmetry is plotted as a function of the normalized subtree degree d. Red solid line: Protium, cleaned. Red dashed line: Protium, full graph. Blue line: Bursera. Dark diamonds: random edges model. Dark circles: nested model. (b) Asymmetry of Protium intercostal segments. is plotted as a function of the normalized subtree degree d. Black dashed line: Protium, cleaned. Red, blue, green, magenta, cyan, yellow lines: Protium segments, colorcoded as in Fig. 8. Gray squares: average of segment asymmetry with standard error. (c) Adjusted cumulative size distribution, Bursera and Protium. Red solid line: Protium, cleaned. Red dashed line: Protium, full graph. Blue line: Bursera.

Mentions: The asymmetry curve of the intercostal area of Bursera, shown in Fig. 9(a), reaches a plateau. On the contrary, the Protium asymmetry does not approach a constant value. However, if we clean the sample by disregarding the high asymmetry nodes with , we see that the Protium asymmetry curve similarly reaches a plateau, which is nevertheless higher than Bursera, indicating an architectural model based on more additive than multiplicative building blocks compared to Bursera. We can calculate the asymmetry for each individual segment of Protium in Fig. 8 and see that, as expected, the different segments exhibit the same architecture and the asymmetry curves relax to a value of approximately , significantly different than the value of 0.45 of the Bursera (Fig. 9(b)).


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Asymmetry and cumulative size distribution for two dicotyledonous leaves.(a) Asymmetry of Bursera and Protium intercostal areas. The average asymmetry  is plotted as a function of the normalized subtree degree d. Red solid line: Protium, cleaned. Red dashed line: Protium, full graph. Blue line: Bursera. Dark diamonds: random edges model. Dark circles: nested model. (b) Asymmetry of Protium intercostal segments.  is plotted as a function of the normalized subtree degree d. Black dashed line: Protium, cleaned. Red, blue, green, magenta, cyan, yellow lines: Protium segments, colorcoded as in Fig. 8. Gray squares: average of segment asymmetry with standard error. (c) Adjusted cumulative size distribution, Bursera and Protium. Red solid line: Protium, cleaned. Red dashed line: Protium, full graph. Blue line: Bursera.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037994-g009: Asymmetry and cumulative size distribution for two dicotyledonous leaves.(a) Asymmetry of Bursera and Protium intercostal areas. The average asymmetry is plotted as a function of the normalized subtree degree d. Red solid line: Protium, cleaned. Red dashed line: Protium, full graph. Blue line: Bursera. Dark diamonds: random edges model. Dark circles: nested model. (b) Asymmetry of Protium intercostal segments. is plotted as a function of the normalized subtree degree d. Black dashed line: Protium, cleaned. Red, blue, green, magenta, cyan, yellow lines: Protium segments, colorcoded as in Fig. 8. Gray squares: average of segment asymmetry with standard error. (c) Adjusted cumulative size distribution, Bursera and Protium. Red solid line: Protium, cleaned. Red dashed line: Protium, full graph. Blue line: Bursera.
Mentions: The asymmetry curve of the intercostal area of Bursera, shown in Fig. 9(a), reaches a plateau. On the contrary, the Protium asymmetry does not approach a constant value. However, if we clean the sample by disregarding the high asymmetry nodes with , we see that the Protium asymmetry curve similarly reaches a plateau, which is nevertheless higher than Bursera, indicating an architectural model based on more additive than multiplicative building blocks compared to Bursera. We can calculate the asymmetry for each individual segment of Protium in Fig. 8 and see that, as expected, the different segments exhibit the same architecture and the asymmetry curves relax to a value of approximately , significantly different than the value of 0.45 of the Bursera (Fig. 9(b)).

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