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
Loopy graphs and their corresponding nesting trees.In these examples the nesting trees have been truncated for clarity. Note that in the “random links” nesting tree frequently low order nodes connect directly to high order nodes. This feature is absent from the “random lines” nesting trees, which are statistically self-similar.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g004: Loopy graphs and their corresponding nesting trees.In these examples the nesting trees have been truncated for clarity. Note that in the “random links” nesting tree frequently low order nodes connect directly to high order nodes. This feature is absent from the “random lines” nesting trees, which are statistically self-similar.

Mentions: Examples of graphs and their corresponding nesting trees are shown in Fig. 4. The underlying geometry, link connectivity and point-wise link weight distribution are identical in every example shown. The architecture is solely defined by the building rule according to which the link weight values are assigned on the network. In the gradient model in Fig.4, the link weights are distributed according to the link center Euclidean distance from the left-most vertex, creating a smooth gradient of link weight. The model random links is produced by random assignment of the weights to the links and exhibits no log-range order. In the nested model, the straight lines defined by the underlying link connectivity are ordered based on a self similar subdivision scheme: the lines on the boundaries and center are assigned order , the lines bisecting order lines are assigned order etc. The link edges are similarly ordered according to weight, and then distributed to the ordered straight lines so that higher thickness links occupy lower order lines. This produces a hierarchical self-similar pattern, characterized by long range order in the link weights. Finally, the random lines model is produced by a random permutation of all the lines.


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Loopy graphs and their corresponding nesting trees.In these examples the nesting trees have been truncated for clarity. Note that in the “random links” nesting tree frequently low order nodes connect directly to high order nodes. This feature is absent from the “random lines” nesting trees, which are statistically self-similar.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037994-g004: Loopy graphs and their corresponding nesting trees.In these examples the nesting trees have been truncated for clarity. Note that in the “random links” nesting tree frequently low order nodes connect directly to high order nodes. This feature is absent from the “random lines” nesting trees, which are statistically self-similar.
Mentions: Examples of graphs and their corresponding nesting trees are shown in Fig. 4. The underlying geometry, link connectivity and point-wise link weight distribution are identical in every example shown. The architecture is solely defined by the building rule according to which the link weight values are assigned on the network. In the gradient model in Fig.4, the link weights are distributed according to the link center Euclidean distance from the left-most vertex, creating a smooth gradient of link weight. The model random links is produced by random assignment of the weights to the links and exhibits no log-range order. In the nested model, the straight lines defined by the underlying link connectivity are ordered based on a self similar subdivision scheme: the lines on the boundaries and center are assigned order , the lines bisecting order lines are assigned order etc. The link edges are similarly ordered according to weight, and then distributed to the ordered straight lines so that higher thickness links occupy lower order lines. This produces a hierarchical self-similar pattern, characterized by long range order in the link weights. Finally, the random lines model is produced by a random permutation of all the lines.

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