Global Optimization, Local Adaptation, and the Role of Growth in Distribution Networks

Highly optimized complex transport networks serve crucial functions in many man-made and natural systems such as power grids and plant or animal vasculature. Often, the relevant optimization functional is nonconvex and characterized by many local extrema. In general, finding the global, or nearly global optimum is difficult. In biological systems, it is believed that such an optimal state is slowly achieved through natural selection. However, general coarse grained models for flow networks with local positive feedback rules for the vessel conductivity typically get trapped in low efficiency, local minima. In this work we show how the growth of the underlying tissue, coupled to the dynamical equations for network development, can drive the system to a dramatically improved optimal state. This general model provides a surprisingly simple explanation for the appearance of highly optimized transport networks in biology such as leaf and animal vasculature.

Figure 1

(a) Immunostained mouse pup retina 7 days after birth. The hierarchical vascular network is clearly visible. Reprinted from [32], with permission. (b) Chemically cleared and stained leaf of Protium wanningianum. The first two levels of vascular hierarchy are marked in green. (c) Network representation of vascular flow. Edges (red, with lengths $L_e$) carry flows $F_e$ (arrows). At nodes (orange, representing areas $a_i$), net currents $S_i$ (dark red arrows, only one shown for clarity) are drawn from the network, supplying the surrounding tissue. (d)–(f) Sketch of vascular development. Overlaid in grey is a comoving coarse-graining grid. At the beginning (d), a tightly meshed capillary plexus is formed (capillaries in red). During development, the plexus is pruned and a hierarchical vascular tree is formed either due to (e) increasing perfusion or (f) growth.

Figure 2

The dynamical transients of equation (7) for $\kappa =1$, $\rho =50$ show hierarchical formation of an optimized network. Line width is proportional to $(K_e^{\prime }{)}^{1/4}$, color is the potential $\mathbf{p}$, and time $t$ is measured in units of $(b^{\prime }{)}^{-1}$. (a) The initial $K_e^{\prime }$ are smoothed out and a homogeneous network is formed. (b),(c) The network structure emerges hierarchically, with largest veins first, and successively smaller veins later. (d) After decaying of small vessels, the final network is highly organized, hierarchically ordered, and has a low energy.

Figure 3

The energy landscape shows a stochastic and a deterministic, optimized phase. The parameter space was partitioned into a $50\times 50$ log-spaced grid and for each parameter value, Eq. (7) was solved until convergence to the steady state for 20 different, random initial conditions on a disordered tessellation. (a) The mean dimensionless energy $\mu (E)$ over 20 networks. Large $\kappa$ and $\rho$ roughly correspond to low-energy, optimized networks. We mark three particular example networks that are plotted in Fig. 4. The minimum energy network had $E_{\min }=15.93$, the relative improvement was $(E_{\max }-E_{\min })/E_{\max }=10.3\%$. The arrow in the color bar marks the minimum energy solution obtained from 1000 runs of simulated annealing, $E_{\text{anneal}}=15.98$. (b) The relative standard deviation $\sigma (E)/\mu (E)$ shows a separation of the parameter space into a stochastic phase in which different initial conditions lead to different final networks, and a deterministic phase in which all initial conditions are mapped to the same final state. We mark the same networks as in (a). (c) Topology correlates with optimization. Highly optimized networks tend to have a low mean branch length (mean number of edges between bifurcating nodes). The correlation becomes stronger with increasing $\kappa$. (d) The phase boundary in parameter space is independent of network size. We show the approximate position of the phase boundary by smoothing (b) and plotting the contour where $\sigma (E)/\mu (E)={10}^{-4}$ for three tessellations.

Figure 4

The steady state networks marked on the energy landscape in Fig. 3 exhibit a morphological transition. Line width is proportional to $(K_e^{\prime }{)}^{1/4}$, color is the potential $p_i$. (a) The network is disordered and not hierarchically organized, with many long branches connecting directly to the source. $E_a=17.26$. (b) Hierarchical organization begins to appear, $E_b=16.19$. (c) The network is hierarchically organized and efficient. Few long branches are visible, $E_c=15.95$ [compare with Fig. 1]. (d) Optimal network when the source is at the boundary showing leaflike main and secondary veins [compare with Fig. 1].