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.(a) Deletion of an edge in a loopy graph. (i) The deletion of the edge joins two adjacent loops. (ii) The deletion of the edge disconnects the graph. (b) Hierarchical decomposition of a planar graph. Boundary loops sequentially join the outside space, marked as . Left: Nesting tree of the hierarchical decomposition. Right, top to bottom: hierarchically decomposed graph. The bottom right panel corresponds to the full graph, the rest represents the network at different levels of decomposition (the corresponding cutoff level of the tree representation is marked with a gray dashed arrow). As edges of the graph are hierarchically deleted, based on their thickness, the original loops (A–E) are joined to form derived loops (–). (c) Hierarchical decomposition of a planar graph. Phantom boundary loops surround the graph perimeter. Loops contiguous to the perimeter of the graph join a ring of phantom boundary loops. The decomposition proceeds as in (b), but the phantom loops – appear among the loops of the original graph in the tree representation. (d) Building blocks of a loopy architecture. The two basic building blocks of the loopy architecture can be identified using the tree representation of the graph. (i1),(i2): multiplicative nestedness. Nested loops merge hierarchically. (i3): This architecture is represented by “tall” trees. (ii1),(ii2): additive nestedness. Ordered loops join consecutively. (ii3): The tree representation is that of “short” trees. Graphs (i1) and (i2) map equivalently to (i3), similarly graphs (ii1) and (ii2) map equivalently to (ii3). (e) Cumulative size distributions of additive and multiplicative models of nestedness. (i1) Nesting tree for additive nestedness. The degree of each node is is shown. (i2) Degree (size) distribution for additive nestedness. (i3) Cumulatize size distribution for additive nestedness. (ii1) Nesting tree, (ii2) Degree (size) distribution and (ii3) Cumulatize size distribution for multiplicative nestedness.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g003: Hierarchical decomposition and nesting trees.(a) Deletion of an edge in a loopy graph. (i) The deletion of the edge joins two adjacent loops. (ii) The deletion of the edge disconnects the graph. (b) Hierarchical decomposition of a planar graph. Boundary loops sequentially join the outside space, marked as . Left: Nesting tree of the hierarchical decomposition. Right, top to bottom: hierarchically decomposed graph. The bottom right panel corresponds to the full graph, the rest represents the network at different levels of decomposition (the corresponding cutoff level of the tree representation is marked with a gray dashed arrow). As edges of the graph are hierarchically deleted, based on their thickness, the original loops (A–E) are joined to form derived loops (–). (c) Hierarchical decomposition of a planar graph. Phantom boundary loops surround the graph perimeter. Loops contiguous to the perimeter of the graph join a ring of phantom boundary loops. The decomposition proceeds as in (b), but the phantom loops – appear among the loops of the original graph in the tree representation. (d) Building blocks of a loopy architecture. The two basic building blocks of the loopy architecture can be identified using the tree representation of the graph. (i1),(i2): multiplicative nestedness. Nested loops merge hierarchically. (i3): This architecture is represented by “tall” trees. (ii1),(ii2): additive nestedness. Ordered loops join consecutively. (ii3): The tree representation is that of “short” trees. Graphs (i1) and (i2) map equivalently to (i3), similarly graphs (ii1) and (ii2) map equivalently to (ii3). (e) Cumulative size distributions of additive and multiplicative models of nestedness. (i1) Nesting tree for additive nestedness. The degree of each node is is shown. (i2) Degree (size) distribution for additive nestedness. (i3) Cumulatize size distribution for additive nestedness. (ii1) Nesting tree, (ii2) Degree (size) distribution and (ii3) Cumulatize size distribution for multiplicative nestedness.

Mentions: The hierarchical decomposition framework if graphically represented in Fig. 2. The algorithm begins with a pruning step, where all tree-like components rooted on the loopy graph backbone, if present, are removed from the graph. This step eliminates all vertices that belong only to one edge, and produces a graph where each edge either separates or connects two loops (Fig. 3(a)).


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Hierarchical decomposition and nesting trees.(a) Deletion of an edge in a loopy graph. (i) The deletion of the edge joins two adjacent loops. (ii) The deletion of the edge disconnects the graph. (b) Hierarchical decomposition of a planar graph. Boundary loops sequentially join the outside space, marked as . Left: Nesting tree of the hierarchical decomposition. Right, top to bottom: hierarchically decomposed graph. The bottom right panel corresponds to the full graph, the rest represents the network at different levels of decomposition (the corresponding cutoff level of the tree representation is marked with a gray dashed arrow). As edges of the graph are hierarchically deleted, based on their thickness, the original loops (A–E) are joined to form derived loops (–). (c) Hierarchical decomposition of a planar graph. Phantom boundary loops surround the graph perimeter. Loops contiguous to the perimeter of the graph join a ring of phantom boundary loops. The decomposition proceeds as in (b), but the phantom loops – appear among the loops of the original graph in the tree representation. (d) Building blocks of a loopy architecture. The two basic building blocks of the loopy architecture can be identified using the tree representation of the graph. (i1),(i2): multiplicative nestedness. Nested loops merge hierarchically. (i3): This architecture is represented by “tall” trees. (ii1),(ii2): additive nestedness. Ordered loops join consecutively. (ii3): The tree representation is that of “short” trees. Graphs (i1) and (i2) map equivalently to (i3), similarly graphs (ii1) and (ii2) map equivalently to (ii3). (e) Cumulative size distributions of additive and multiplicative models of nestedness. (i1) Nesting tree for additive nestedness. The degree of each node is is shown. (i2) Degree (size) distribution for additive nestedness. (i3) Cumulatize size distribution for additive nestedness. (ii1) Nesting tree, (ii2) Degree (size) distribution and (ii3) Cumulatize size distribution for multiplicative nestedness.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037994-g003: Hierarchical decomposition and nesting trees.(a) Deletion of an edge in a loopy graph. (i) The deletion of the edge joins two adjacent loops. (ii) The deletion of the edge disconnects the graph. (b) Hierarchical decomposition of a planar graph. Boundary loops sequentially join the outside space, marked as . Left: Nesting tree of the hierarchical decomposition. Right, top to bottom: hierarchically decomposed graph. The bottom right panel corresponds to the full graph, the rest represents the network at different levels of decomposition (the corresponding cutoff level of the tree representation is marked with a gray dashed arrow). As edges of the graph are hierarchically deleted, based on their thickness, the original loops (A–E) are joined to form derived loops (–). (c) Hierarchical decomposition of a planar graph. Phantom boundary loops surround the graph perimeter. Loops contiguous to the perimeter of the graph join a ring of phantom boundary loops. The decomposition proceeds as in (b), but the phantom loops – appear among the loops of the original graph in the tree representation. (d) Building blocks of a loopy architecture. The two basic building blocks of the loopy architecture can be identified using the tree representation of the graph. (i1),(i2): multiplicative nestedness. Nested loops merge hierarchically. (i3): This architecture is represented by “tall” trees. (ii1),(ii2): additive nestedness. Ordered loops join consecutively. (ii3): The tree representation is that of “short” trees. Graphs (i1) and (i2) map equivalently to (i3), similarly graphs (ii1) and (ii2) map equivalently to (ii3). (e) Cumulative size distributions of additive and multiplicative models of nestedness. (i1) Nesting tree for additive nestedness. The degree of each node is is shown. (i2) Degree (size) distribution for additive nestedness. (i3) Cumulatize size distribution for additive nestedness. (ii1) Nesting tree, (ii2) Degree (size) distribution and (ii3) Cumulatize size distribution for multiplicative nestedness.
Mentions: The hierarchical decomposition framework if graphically represented in Fig. 2. The algorithm begins with a pruning step, where all tree-like components rooted on the loopy graph backbone, if present, are removed from the graph. This step eliminates all vertices that belong only to one edge, and produces a graph where each edge either separates or connects two loops (Fig. 3(a)).

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