Loops within loops: how to parse the hierarchy
Loops all the way down: quantifying hierarchies within reticular networks
Freshly appeared at PLoS ONE: Quantifying Loopy Network Architectures.
Over 50 years ago, Robert Horton and Arthur Strahler developed a method to characterize how streams interconnect within large-scale river networks. This highly influential method, now known as Horton-Strahler ordering, quantifies the significance of a stream segment. There has been a phenomenal amount of work in geomorphology following the pioneering work of Horton and Strahler, including the discovery of fractal river basins.
However, attempts to extend the Horton-Strahler ordering to a wider class of problems have failed for decades, because the ordering scheme only applies to tree-like structures and cannot be applied to networks with loops. Nonetheless, many networks, such as ant colonies, leaf networks, street grids, and neural networks, have loops, and often loops within loops. Moreover, these networks exhibit apparent visual hierarchies in their loop structure that have not, until now, been systematically characterized.
New research published this week in PLoS One, includes two independent discoveries of a novel method to systematically characterize the structure of loopy networks, made by two international team of researchers:
- Dr. Eleni Katifori (Max Planck Institute for Dynamics and Selforganization, Germany) & Prof. Marcelo Magnasco (Rockeller University)
- Dr. Yuriy Mileyko (Duke University), Prof. Charles Price (University of Western Australia), Prof. Herbert Edelsbrunner (Duke University & IST-Austria) & Prof. Joshua Weitz (Georgia Institute of Technology)
The two groups found, independently, an elegant way to analyze the hierarchy of loops within a network, by analyzing the dual graph to the connectivity network.
“The Katifori-Mileyko ordering enables a breakthrough advance in characterizing reticular networks”, said Joshua Weitz. “It will enable the quantitative analysis of networks dominated by cycles, in much the same way that the Horton-Strahler scheme enabled systematic analysis of tree-like networks.”
The ordering scheme proposed for loopy networks applies to weighted planar networks, with weights corresponding to the widths of the network branches. The basic idea is one of hierarchical decomposition in which the network is iteratively pruned of tree-like components, the remaining edges are ordered, and finally, the thinnest edge is removed. This decomposition proceeds until all loops are removed.
Both groups have shown that the hierarchical order of loops in a weighted planar network can be computed by analyzing how the faces of the network are merged as edges are removed in the order of increasing weight. This approach naturally classifies graph edges into reticular edges, which are responsible for loop formation, and tree edges, which constitute a spanning tree of the network. Hence, both the loop and the tree hierarchies can be computed.
In addition to the discovery of the method, Katifori and Magnasco applied the ordering scheme to natural neworks, including leaf vasculature and cortical networks from rat brains. Instead of application to natural networks, Mileyko and colleagues developed a rigorous mathematical analysis of the sensitivity of the hierarchical decomposition to noise that may occur in measurements of edge weights.
Katifori and Magnasco write, “A big part of our extensive understanding of fluvial networks is due to the development of methodology to characterize and quantify tree architectures. Accordingly, progress in understanding loopy networks, which are ubiquitous in both natural and man made structures, is contingent on our ability to measure their hierarchical architecture.”
The hierarchical decomposition method discovered by the two groups provides an invaluable tool in future efforts to decipher the functional significance, origins and evolution of loopy networks.