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
Cumulative size distribution of generated graphs.These graphs were constructed to share identical underlying topology (N = 817 vertices, triangular lattice) and edge width distribution. (a) The asymmetry  of the random lines model (red) and random links model (cyan). The x-axis is the logarithm of the degree of the vertex or the nesting tree. Red line: averaged asymmetry of subgraphs of degree , random lines model. Cyan line: averaged asymmetry of subgraphs of degree , random links model. Inset: Density plots: The overlap of the two distributions is plotted in white. (b) The averaged asymmetry  of the nested (blue), nested5 (orange), nested10 (light blue), random lines (red) and random links model (cyan) as a function of the base 2 logarithm of the degree d. (c) Cumulative size distribution  of generated models. Random links model (green), nested (blue), gradient (magenta), peaks (green). The total area of the graphs has been normalized to 1. Discontinuities or near discontinuities in the slope of cumulative size distribution indicate lengthscales where potentially the architectural organization changes qualitatively. (f1). Adjusted cumulative size distribution, random links model. (f2) The Adjusted cumulative size distribution  is plotted for the nested (blue), nested5 (orange), nested10 (light blue) and random lines model (red).The Adjusted cumulative size distribution of the self-similar networks (nested, nested5, and random lines) can be approximated by a straight line of slope zero. Notice the periodicity in the nested lines model. The colored area indicates the standard error of 20 realizations.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g006: Cumulative size distribution of generated graphs.These graphs were constructed to share identical underlying topology (N = 817 vertices, triangular lattice) and edge width distribution. (a) The asymmetry of the random lines model (red) and random links model (cyan). The x-axis is the logarithm of the degree of the vertex or the nesting tree. Red line: averaged asymmetry of subgraphs of degree , random lines model. Cyan line: averaged asymmetry of subgraphs of degree , random links model. Inset: Density plots: The overlap of the two distributions is plotted in white. (b) The averaged asymmetry of the nested (blue), nested5 (orange), nested10 (light blue), random lines (red) and random links model (cyan) as a function of the base 2 logarithm of the degree d. (c) Cumulative size distribution of generated models. Random links model (green), nested (blue), gradient (magenta), peaks (green). The total area of the graphs has been normalized to 1. Discontinuities or near discontinuities in the slope of cumulative size distribution indicate lengthscales where potentially the architectural organization changes qualitatively. (f1). Adjusted cumulative size distribution, random links model. (f2) The Adjusted cumulative size distribution is plotted for the nested (blue), nested5 (orange), nested10 (light blue) and random lines model (red).The Adjusted cumulative size distribution of the self-similar networks (nested, nested5, and random lines) can be approximated by a straight line of slope zero. Notice the periodicity in the nested lines model. The colored area indicates the standard error of 20 realizations.

Mentions: In this section we will consider various classes of architectural models. These computer generated networks were produced according to various predetermined rules. The gradient, random links, nested and random lines models are shown in Fig. 4, and are discussed in the previous section. The nested5 model is produced by the nested model, choosing five lines at random and randomly permuting their order. Similarly, the model nested10, is derived from the nested model by swapping 10 lines at random. Finally, in the peaks model, the thick links are concentrated around seven equidistant peaks. These models are shown at the insets of Fig. 5 and 6.


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Cumulative size distribution of generated graphs.These graphs were constructed to share identical underlying topology (N = 817 vertices, triangular lattice) and edge width distribution. (a) The asymmetry  of the random lines model (red) and random links model (cyan). The x-axis is the logarithm of the degree of the vertex or the nesting tree. Red line: averaged asymmetry of subgraphs of degree , random lines model. Cyan line: averaged asymmetry of subgraphs of degree , random links model. Inset: Density plots: The overlap of the two distributions is plotted in white. (b) The averaged asymmetry  of the nested (blue), nested5 (orange), nested10 (light blue), random lines (red) and random links model (cyan) as a function of the base 2 logarithm of the degree d. (c) Cumulative size distribution  of generated models. Random links model (green), nested (blue), gradient (magenta), peaks (green). The total area of the graphs has been normalized to 1. Discontinuities or near discontinuities in the slope of cumulative size distribution indicate lengthscales where potentially the architectural organization changes qualitatively. (f1). Adjusted cumulative size distribution, random links model. (f2) The Adjusted cumulative size distribution  is plotted for the nested (blue), nested5 (orange), nested10 (light blue) and random lines model (red).The Adjusted cumulative size distribution of the self-similar networks (nested, nested5, and random lines) can be approximated by a straight line of slope zero. Notice the periodicity in the nested lines model. The colored area indicates the standard error of 20 realizations.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037994-g006: Cumulative size distribution of generated graphs.These graphs were constructed to share identical underlying topology (N = 817 vertices, triangular lattice) and edge width distribution. (a) The asymmetry of the random lines model (red) and random links model (cyan). The x-axis is the logarithm of the degree of the vertex or the nesting tree. Red line: averaged asymmetry of subgraphs of degree , random lines model. Cyan line: averaged asymmetry of subgraphs of degree , random links model. Inset: Density plots: The overlap of the two distributions is plotted in white. (b) The averaged asymmetry of the nested (blue), nested5 (orange), nested10 (light blue), random lines (red) and random links model (cyan) as a function of the base 2 logarithm of the degree d. (c) Cumulative size distribution of generated models. Random links model (green), nested (blue), gradient (magenta), peaks (green). The total area of the graphs has been normalized to 1. Discontinuities or near discontinuities in the slope of cumulative size distribution indicate lengthscales where potentially the architectural organization changes qualitatively. (f1). Adjusted cumulative size distribution, random links model. (f2) The Adjusted cumulative size distribution is plotted for the nested (blue), nested5 (orange), nested10 (light blue) and random lines model (red).The Adjusted cumulative size distribution of the self-similar networks (nested, nested5, and random lines) can be approximated by a straight line of slope zero. Notice the periodicity in the nested lines model. The colored area indicates the standard error of 20 realizations.
Mentions: In this section we will consider various classes of architectural models. These computer generated networks were produced according to various predetermined rules. The gradient, random links, nested and random lines models are shown in Fig. 4, and are discussed in the previous section. The nested5 model is produced by the nested model, choosing five lines at random and randomly permuting their order. Similarly, the model nested10, is derived from the nested model by swapping 10 lines at random. Finally, in the peaks model, the thick links are concentrated around seven equidistant peaks. These models are shown at the insets of Fig. 5 and 6.

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