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

Asymmetry and cumulative size distribution of optimized graphs.(a) Optimized networks, fluctuations in the load (sink model). Instances of optimized graphs () when the load is concentrated at a single, moving, point. (b) Optimized networks, robustness to damage (bond model). Instances of optimized graphs () when robustness is required under the presence of random damage. (c) Asymmetry of sink model. (d) Asymmetry of bond model. The average asymmetry  is plotted as a function of the normalized subtree degree . Red line: . Green line: . Blue line: . Black dashed line: random links model. The colored area represents the standard error after averaging over 20 realizations of each model. (e) Adjusted cumulative size distribution, sink models. The gray line overlayed on the blue,  line is the random links model. (f) Adjusted cumulative size distribution, bond models. The adjusted cumulative size distribution  is plotted for  (red, green, blue respectively) The adjusted cumulative size distribution is averaged over 20 realizations for the bond, sink and random edges model. The colored area represents the standard error after averaging over 20 realizations of each model.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g007: Asymmetry and cumulative size distribution of optimized graphs.(a) Optimized networks, fluctuations in the load (sink model). Instances of optimized graphs () when the load is concentrated at a single, moving, point. (b) Optimized networks, robustness to damage (bond model). Instances of optimized graphs () when robustness is required under the presence of random damage. (c) Asymmetry of sink model. (d) Asymmetry of bond model. The average asymmetry is plotted as a function of the normalized subtree degree . Red line: . Green line: . Blue line: . Black dashed line: random links model. The colored area represents the standard error after averaging over 20 realizations of each model. (e) Adjusted cumulative size distribution, sink models. The gray line overlayed on the blue, line is the random links model. (f) Adjusted cumulative size distribution, bond models. The adjusted cumulative size distribution is plotted for (red, green, blue respectively) The adjusted cumulative size distribution is averaged over 20 realizations for the bond, sink and random edges model. The colored area represents the standard error after averaging over 20 realizations of each model.

Mentions: Modeled as electrical (or equivalently water distribution) grids, the networks transport load from the root (bottom center vertex in the networks of Fig. 7(a)) to other nodes in the network. In the “bond” model, the root has to distribute the load evenly to all the vertices, even if a random single bond is removed (robustness to damage). In the fluctuating sink model, instead of a uniform distribution of sinks there is a single sink, the position of which moves across the network. The cost to build the network is determined by a function and is set to a constant in each case. The parameter quantifies the “economy of scale”, i.e. how relatively expensive is a high conductivity edge compared to a smaller edge. The link thickness of the graphs shown in Fig. 7(a) represents the bond conductivities, which are determined by optimizing for the total network power dissipation (results are shown for and 0.7).


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Asymmetry and cumulative size distribution of optimized graphs.(a) Optimized networks, fluctuations in the load (sink model). Instances of optimized graphs () when the load is concentrated at a single, moving, point. (b) Optimized networks, robustness to damage (bond model). Instances of optimized graphs () when robustness is required under the presence of random damage. (c) Asymmetry of sink model. (d) Asymmetry of bond model. The average asymmetry  is plotted as a function of the normalized subtree degree . Red line: . Green line: . Blue line: . Black dashed line: random links model. The colored area represents the standard error after averaging over 20 realizations of each model. (e) Adjusted cumulative size distribution, sink models. The gray line overlayed on the blue,  line is the random links model. (f) Adjusted cumulative size distribution, bond models. The adjusted cumulative size distribution  is plotted for  (red, green, blue respectively) The adjusted cumulative size distribution is averaged over 20 realizations for the bond, sink and random edges model. The colored area represents the standard error after averaging over 20 realizations of each model.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037994-g007: Asymmetry and cumulative size distribution of optimized graphs.(a) Optimized networks, fluctuations in the load (sink model). Instances of optimized graphs () when the load is concentrated at a single, moving, point. (b) Optimized networks, robustness to damage (bond model). Instances of optimized graphs () when robustness is required under the presence of random damage. (c) Asymmetry of sink model. (d) Asymmetry of bond model. The average asymmetry is plotted as a function of the normalized subtree degree . Red line: . Green line: . Blue line: . Black dashed line: random links model. The colored area represents the standard error after averaging over 20 realizations of each model. (e) Adjusted cumulative size distribution, sink models. The gray line overlayed on the blue, line is the random links model. (f) Adjusted cumulative size distribution, bond models. The adjusted cumulative size distribution is plotted for (red, green, blue respectively) The adjusted cumulative size distribution is averaged over 20 realizations for the bond, sink and random edges model. The colored area represents the standard error after averaging over 20 realizations of each model.
Mentions: Modeled as electrical (or equivalently water distribution) grids, the networks transport load from the root (bottom center vertex in the networks of Fig. 7(a)) to other nodes in the network. In the “bond” model, the root has to distribute the load evenly to all the vertices, even if a random single bond is removed (robustness to damage). In the fluctuating sink model, instead of a uniform distribution of sinks there is a single sink, the position of which moves across the network. The cost to build the network is determined by a function and is set to a constant in each case. The parameter quantifies the “economy of scale”, i.e. how relatively expensive is a high conductivity edge compared to a smaller edge. The link thickness of the graphs shown in Fig. 7(a) represents the bond conductivities, which are determined by optimizing for the total network power dissipation (results are shown for and 0.7).

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