Weitz Group @ Georgia Tech Theoretical Ecology and Quantitative Biology



Extending the classic Horton-Strahler ordering of hierarchical networks to the ordering of loopy networks, in PLoS One

Posted by jsweitz

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:

  • Quantifying loopy network architectures by: Dr. Eleni Katifori (Max Planck Institute for Dynamics and Selforganization, Germany) & Prof. Marcelo Magnasco (Rockeller University)
  • Hierarchical ordering of reticular networks by: 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 discovery extends the classic results of Robert Horton and Arthur Strahler, who over 50 years ago 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 relative significance of a stream segment within a river network. 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.