Extracting Hidden Hierarchies in 3D Distribution Networks

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.

Popular Summary

Natural transport webs—for example, load-bearing structures and connections within mammalian brains—are frequently dominated by dense sets of nested cycles. The architecture of these networks determines how efficiently and how robustly the networks perform their function; however, the set of tools that can model or characterize such weighted, cycle-rich architecture remains sparse. Here, we imagine a complex, three-dimensional distribution network as a simpler, effective tiling of an abstract surface and, in so doing, construct just such a tool. Furthermore, we demonstrate the effectiveness of our classification scheme by distinguishing closely related families of networks.

We focus on networks that are too complex to be characterized solely using a two-dimensional plane. Our trial computer-generated networks fall into one of two types of topologies: a network on a two-holed torus with lattice defects and an ensemble of nodes randomly falling within a three-dimensional sphere. We furthermore consider four different classes of relevant weight distributions. Using our statistically robust algorithm, we characterize the topology of weighted networks in three dimensions. We test our findings using public transportation data collected in Great Britain, but we note that our new algorithm can be used for automated phenotypic characterization of many networks spanning a range of fields: mammalian organ vasculature, root networks of quaking aspen, and force networks in granular matter like sand.

We expect that our findings will inform future studies of the highly complex networks that are increasingly becoming a mainstay in our society.

Figure 1

Some simple examples of graph embeddability, both planar and otherwise. (a) The complete graph on four vertices, $K_4$, is not embedded in the plane in its most traditional representation (left) but is planar nonetheless (right). (b) The complete graph on five vertices, $K_5$, is not planar (left). However, this graph can be represented without edge crossings on a torus (right).

Figure 2

Tiles and topological cycles of a square lattice on a toroidal topology ($g=1$). Opposite sides of the lattice are identified as shown.

Figure 3

A graph embedded on a toroidal surface. Highlighted are example basis vectors from (a) a fundamental cycle basis and (b) a minimum weight basis. Red: Some representative tiling basis vectors. Blue and green: Basis vectors that correspond to the $2g=2$ generators of the fundamental group of the torus.

Figure 4

(a) Graph embedded on a two-holed torus, schematic. Periodic boundary conditions connect opposite sides of the octagon. Highlighted are some example tiling basis vectors from a fundamental cycle basis (magenta) and from the minimum weight basis (red). The blue curve highlights one of the $2g=4$ vectors in the minimal basis corresponding to the generators of the fundamental group of the two-holed torus. (b) A 3D graph with an unknown embedding. Identification of tiling versus generator basis vectors is not straightforward anymore. Highlighted with red and orange are two vectors in the minimum weight basis that share an edge.

Figure 5

(a) Schematic of the cycle-coalescence algorithm applied to a simple 3D graph. The cycle coalescence proceeds from top to bottom. At each step, the next weakest link is cut, and the two cycles that bordered that link coalesce into one. On the right, we show the characteristic tree being progressively built, with each node representing a cycle in the network. To aid the eye, some cycles that participate at that stage of the algorithm are highlighted in color, and the corresponding nodes of the characteristic tree are correspondingly color-coded. (b) Schematic of degenerate graphs that produce the same characteristic tree. The cycle coalescence is blind to geometry and exact weights of links.

Figure 6

(a) Honeycomb lattice on a toroidal topology. Opposite sides are identified as shown. (b) T1 topological rearrangement on a honeycomb lattice. (c) One-holed torus with a thin handle. (d) A tile with a large number of sides as a result of condensation of disclination charges. (e) Varicosity as a result of a condensation of like-charged dislocation defects. Opposite sides are identified as shown, resulting in the topology of a one-handle torus.

Figure 7

Average vein length versus topological asymmetry for toy graphs in (a) 2D and (b) 3D.

Figure 8

Examples of different edge-weight assignment functions on a two-holed torus. (a) Random. (b) Lines, no self-avoidance. (c) Lines with SA. Note the high similarity between (b) and (c).

Figure 9

Raw, untransformed basis vector length counts (left column, green histograms) and the result of rotating these vectors onto the minimal weight basis (right column, orange histograms). Histograms are shown for a network on a torus $(a_i)$, a network on a 2-torus $(b_i)$, a network randomly embedded into space $(c_i)$, and a real transport network $(d_i)$.

Figure 10

A comparison of $p_m$, the observed average number of links per cycle upon removing the $N_t$ largest cycles from the set, and $p_{th}$, the theoretically predicted value for the given network with genus $g=N_t/2$. When $|p_m-p_{th}|$ is identically zero, there is an exact match between the removed cycles and the “true” topological cycles. In cases where zero is not achieved, there is some mixing of tiles and topological cycles somewhere in the $N_t$-removed cycles. This mixing occurs statistically among the smallest of the removed cycles. Even so, the minimum of this value indicates that many of the cycles are identified correctly.

Figure 11

Average vein length versus topological asymmetry for various edge-weight assignment models on random 3-regular graph topologies. The number of nodes on each graph was approximately $N\simeq 500$. Blue: SA lines; red: lines; green: random; orange: adapted 0.8; and purple: adapted 0.5.

Figure 12

Average vein length $L$ versus topological asymmetry $A$ for various edge-weight assignment models on random 3-regular graph topologies. The number of nodes on each graph was approximately $N\simeq 500$ or $N\simeq 800$. Blue: SA lines 500; light blue: SA lines 800; red: lines 500; pink: lines 800; green: random 500; and light green: random 800. $L$ and $A$ are not sensitive to the graph size.

Figure 13

Average vein length $L$ versus topological asymmetry $A$ for various edge-weight assignment models on genus-2 toroidal topologies. The number of nodes on each graph was approximately $N\simeq 500$ or $N\simeq 800$. Blue: SA lines 500; light blue: SA Lines 800; red: lines 500; pink: lines 800; green: random 500; light green: and random 800. $L$ and $A$ are not sensitive to the graph size.

Figure 14

(a) Average vein length $L$ versus topological asymmetry $A$ for initial, intermediate, and final states of an initially random-weighted network evolving under our adaptive model. (b) Distribution of the edge weights in the final adapted states for two different sigmoidal-feedback control exponents, $\gamma$. (c) Structural correlations in the adapted weights from identical starting configurations for two different sigmoidal-feedback control exponents, $\gamma$.

Figure 15

(a) Average vein length $L$ versus topological asymmetry $A$ for the coach network (large green square), and the low- and high-threshold train one (large blue diamond and red circle, respectively). The small symbols represent networks with the same underlying topology as the coach network (small green squares), and the low- and high-threshold train one (small blue diamond and small red circle, respectively), but randomized edge weights. (b) Degree distribution of the topologies of the coach and train networks. The numbers of nodes $P_k$ of degree $k$ can be approximated by a power law.