Extracting Hidden Hierarchies in 3D Distribution Networks

Abstract

Natural and man-made transport webs are frequently dominated by dense sets of nested cycles. The architecture of these networks, as defined by the topology and edge weights, determines how efficiently the networks perform their function. Yet, the set of tools that can characterize such a weighted cycle-rich architecture in a physically relevant, mathematically compact way is sparse. In order to fill this void, we have developed a new algorithm that rests on an abstraction of the physical “tiling” in the case of a two-dimensional network to an effective tiling of an abstract surface in 3-space that the network may be thought to sit in. Generically, these abstract surfaces are richer than the flat plane because there are now two families of fundamental units that may aggregate upon cutting weakest links—the plaquettes of the tiling and the longer “topological” cycles associated with the abstract surface itself. Upon sequential removal of the weakest links, as determined by a physically relevant edge weight, such as flow volume or capacity, neighboring plaquettes merge and a new tree graph characterizing this merging process results. The properties of this characteristic tree can provide the physical and topological data required to describe the architecture of the network and to build physical models. The new algorithm can be used for automated phenotypic characterization of any weighted network whose structure is dominated by cycles, such as mammalian vasculature in the organs or the force networks in jammed granular matter.