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
Hierarchical decomposition and nesting trees: Algorithm.The first step consists of pruning all tree-like components of the graph. In the second step we order the list of graph edges based on their width. Here we mark the 5 thinnest edges, ordered based on their weight. In the third step, we remove the weakest edge from the graph. Here this step will result in joining the green with the red loop, to form the yellow facet. The loops are represented as color coded nodes in the nesting tree. We then repeat steps 2 and 3 iteratively, to sequentially remove every edge, and as a consequence, gradually join every loop.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g002: Hierarchical decomposition and nesting trees: Algorithm.The first step consists of pruning all tree-like components of the graph. In the second step we order the list of graph edges based on their width. Here we mark the 5 thinnest edges, ordered based on their weight. In the third step, we remove the weakest edge from the graph. Here this step will result in joining the green with the red loop, to form the yellow facet. The loops are represented as color coded nodes in the nesting tree. We then repeat steps 2 and 3 iteratively, to sequentially remove every edge, and as a consequence, gradually join every loop.

Mentions: In what follows, the term link will refer to a graph element that connects two nodes, and the term edge will refer to a chain of links, connecting nodes. Each node in an edge is connected to exactly two other nodes, except the nodes at the boundaries of the edge, which can be connected to only one other node (when that edge is the “leaf” of a tree), or three or more other nodes (see inset of Fig. 2). The “edge strength” is a quantity that parametrizes the weight of the edge J. If an edge J is composed of a chain of links, then can be set to be the edge strength of the weakest of the chain links, the median value, or any other quantity that is of interest. The term loop is used to refer to the graph cycles, and the terminal or ultimate loops are the cycles that do not contain other loops.


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Hierarchical decomposition and nesting trees: Algorithm.The first step consists of pruning all tree-like components of the graph. In the second step we order the list of graph edges based on their width. Here we mark the 5 thinnest edges, ordered based on their weight. In the third step, we remove the weakest edge from the graph. Here this step will result in joining the green with the red loop, to form the yellow facet. The loops are represented as color coded nodes in the nesting tree. We then repeat steps 2 and 3 iteratively, to sequentially remove every edge, and as a consequence, gradually join every loop.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037994-g002: Hierarchical decomposition and nesting trees: Algorithm.The first step consists of pruning all tree-like components of the graph. In the second step we order the list of graph edges based on their width. Here we mark the 5 thinnest edges, ordered based on their weight. In the third step, we remove the weakest edge from the graph. Here this step will result in joining the green with the red loop, to form the yellow facet. The loops are represented as color coded nodes in the nesting tree. We then repeat steps 2 and 3 iteratively, to sequentially remove every edge, and as a consequence, gradually join every loop.
Mentions: In what follows, the term link will refer to a graph element that connects two nodes, and the term edge will refer to a chain of links, connecting nodes. Each node in an edge is connected to exactly two other nodes, except the nodes at the boundaries of the edge, which can be connected to only one other node (when that edge is the “leaf” of a tree), or three or more other nodes (see inset of Fig. 2). The “edge strength” is a quantity that parametrizes the weight of the edge J. If an edge J is composed of a chain of links, then can be set to be the edge strength of the weakest of the chain links, the median value, or any other quantity that is of interest. The term loop is used to refer to the graph cycles, and the terminal or ultimate loops are the cycles that do not contain other loops.

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