## Abstract

Transport networks are ubiquitous in both social and biological systems. Robust network performance involves a complex trade-off involving cost, transport efficiency, and fault tolerance. Biological networks have been honed by many cycles of evolutionary selection pressure and are likely to yield reasonable solutions to such combinatorial optimization problems. Furthermore, they develop without centralized control and may represent a readily scalable solution for growing networks in general. We show that the slime mold *Physarum polycephalum* forms networks with comparable efficiency, fault tolerance, and cost to those of real-world infrastructure networks—in this case, the Tokyo rail system. The core mechanisms needed for adaptive network formation can be captured in a biologically inspired mathematical model that may be useful to guide network construction in other domains.

Transport networks are a critical part of the infrastructure needed to operate a modern industrial society and facilitate efficient movement of people, resources, energy, and information. Despite their importance, most networks have emerged without clear global design principles and are constrained by the priorities imposed at their initiation. Thus, the main motivation historically was to achieve high transport efficiency at reasonable cost, but with correspondingly less emphasis on making systems tolerant to interruption or failure. Introducing robustness inevitably requires additional redundant pathways that are not cost-effective in the short term. In recent years, the spectacular failure of key infrastructure such as power grids (*1*, *2*), financial systems (*3*, *4*), airline baggage-handling systems (*5*), and railway networks (*6*), as well as the predicted vulnerability of systems such as information networks (*7*) or supply networks (*8*) to attack, have highlighted the need to develop networks with greater intrinsic resilience.

Some organisms grow in the form of an interconnected network as part of their normal foraging strategy to discover and exploit new resources (*9*–*12*). Such systems continuously adapt to their environment and must balance the cost of producing an efficient network with the consequences of even limited failure in a competitive world. Unlike anthropogenic infrastructure systems, these biological networks have been subjected to successive rounds of evolutionary selection and are likely to have reached a point at which cost, efficiency, and resilience are appropriately balanced. Drawing inspiration from biology has led to useful approaches to problem-solving such as neural networks, genetic algorithms, and efficient search routines developed from ant colony optimization algorithms (*13*). We exploited the slime mold *Physarum polycephalum* to develop a biologically inspired model for adaptive network development.

*Physarum* is a large, single-celled amoeboid organism that forages for patchily distributed food sources. The individual plasmodium initially explores with a relatively contiguous foraging margin to maximize the area searched. However, behind the margin, this is resolved into a tubular network linking the discovered food sources through direct connections, additional intermediate junctions (Steiner points) that reduce the overall length of the connecting network, and the formation of occasional cross-links that improve overall transport efficiency and resilience (*11*, *12*). The growth of the plasmodium is influenced by the characteristics of the substrate (*14*) and can be constrained by physical barriers (*15*) or influenced by the light regime (*16*), facilitating experimental investigation of the rules underlying network formation. Thus, for example, *Physarum* can find the shortest path through a maze (*15*–*17*) or connect different arrays of food sources in an efficient manner with low total length (TL) yet short average minimum distance (MD) between pairs of food sources (FSs), with a high degree of fault tolerance (FT) to accidental disconnection (*11*, *18*, *19*). Capturing the essence of this system in simple rules might be useful in guiding the development of decentralized networks in other domains.

We observed *Physarum* connecting a template of 36 FSs that represented geographical locations of cities in the Tokyo area, and compared the result with the actual rail network in Japan. The *Physarum* plasmodium was allowed to grow from Tokyo and initially filled much of the available land space, but then concentrated on FSs by thinning out the network to leave a subset of larger, interconnecting tubes (Fig. 1). An alternative protocol, in which the plasmodium was allowed to extend fully in the available space and the FSs were then presented simultaneously, yielded similar results. To complete the network formation, we allowed any excess volume of plasmodium to accumulate on a large FS outside the arena (LFS in Fig. 2A).

A range of network solutions were apparent in replicate experiments (compare Fig. 2A with Fig. 1F); nonetheless, the topology of many *Physarum* networks bore similarity to the real rail network (Fig. 2D). Some of the differences may relate to geographical features that constrain the rail network, such as mountainous terrain or lakes. These constraints were imposed on the *Physarum* network by varying the intensity of illumination, as the plasmodium avoids bright light (*16*). This yielded networks (Fig. 2, B and C) with greater visual congruence to the real rail network (Fig. 2D). Networks were also compared with the minimal spanning tree (MST, Fig. 2E), which is the shortest possible network connecting all the city positions, and various derivatives with increasing numbers of cross-links added (e.g., Fig. 2F), culminating in a fully connected Delaunay triangulation, which represents the maximally connected network linking all the cities.

The performance of each network was characterized by the cost (TL), transport efficiency (MD), and robustness (FT), normalized to the corresponding value for the MST to give TL_{MST}, MD_{MST}, and FT_{MST}. The TL of the Tokyo rail network was greater than the MST by a factor of ~1.8 (i.e., TL_{MST} ≈ 1.8), whereas the average TL_{MST} for *Physarum* was 1.75 ± 0.30 (*n* = 21). Illuminated networks gave slightly better clustering around the value for the rail network (Fig. 3A). For comparison, the Delaunay triangulation was longer than the MST by a factor of ~4.6. Thus, the cost of the solutions found by *Physarum* closely matched that of the rail network, with about 30% of the maximum possible number of links in place. The transport performance of the two networks was also similar, with MD_{MST} of 0.85 and 0.85 ± 0.04 for the rail network and the *Physarum* networks, respectively. However, the *Physarum* networks achieved this with marginally lower overall cost (Fig. 3A).

The converse was true for the fault tolerance (FT_{MST}) in which the real rail network showed marginally better resilience, close to the lowest level needed to give maximum tolerance to a single random failure. Thus, only 4% of faults in the rail network would lead to isolation of any part, whereas 14 ± 4% would disconnect the illuminated *Physarum* networks, and 20 ± 13% would disconnect the unconstrained *Physarum* networks. In contrast, simply adding additional links to the MST to improve network performance resulted in networks with poor fault tolerance (Fig. 3B).

The trade-off between fault tolerance and cost was captured in a single benefit-cost measure, expressed as the ratio of FT/TL_{MST} = α. In general, the *Physarum* networks and the rail network had a benefit/cost ratio of ~0.5 for any given TL_{MST} (Fig. 3B). The relationship between different α values and transport efficiency (Fig. 3C) highlighted the similarity in aggregate behavior of the *Physarum* network when considering all three performance measures (MD_{MST}, TL_{MST}, and FT_{MST}). The rail network was embedded in the cluster of results for the *Physarum* networks with a marginally higher α value for the same transport efficiency (Fig. 3C).

Overall, we conclude that the *Physarum* networks showed characteristics similar to those of the rail network in terms of cost, transport efficiency, and fault tolerance. However, the *Physarum* networks self-organized without centralized control or explicit global information by a process of selective reinforcement of preferred routes and simultaneous removal of redundant connections.

We developed a mathematical model for adaptive network construction to emulate this behavior, based on feedback loops between the thickness of each tube and internal protoplasmic flow (*18*–*22*) in which high rates of streaming stimulate an increase in tube diameter, whereas tubes tend to decline at low flow rates (*23*). The initial shape of a plasmodium is represented by a randomly meshed lattice with a relatively fine spacing, as shown in Fig. 4 (*t* = 0). The edges represent plasmodial tubes in which protoplasm flows, and nodes are junctions between tubes. Suppose that the pressures at nodes *i* and *j* are *p _{i}* and

*p*, respectively, and that the two nodes are connected by a cylinder of length

_{j}*L*and radius

_{ij}*r*. Assuming that flow is laminar and follows the Hagen-Poiseuille equation, the flux through the tube is

_{ij}*D*= π

_{ij}*r*

^{4}/8η is a measure of the conductivity of the tube. As the length

*L*is a constant, the behavior of the network is described by the conductivities,

_{ij}*D*, of the edges.

_{ij}At each time step, a random FS (node 1) is selected to drive flow through the network, so the flux includes a source term Σ_{j}Q_{1}* _{j}* =

*I*

_{0}. A second random FS is chosen as a sink (node 2) with a corresponding withdrawal of

*I*

_{0}such that Σ

_{j}Q_{2}

*= –*

_{j}*I*

_{0}. As the amount of fluid must be conserved, the inflow and outflow at each internal node must balance so that

*i*(

*i*≠ 1, 2), Σ

*= 0. Thus, for a given set of conductivities and selected source and sink nodes, the flux through each of the network edges can be computed.*

_{j}Q_{ij}To accommodate the adaptive behavior of the plasmodium, the conductivity of each tube evolves according to *dD _{ij}*/

*dt*=

*f*(|

*Q*|) –

_{ij}*D*. The first term on the right side describes the expansion of tubes in response to the flux. The second term represents the rate of tube constriction, so that in the absence of flow the tubes will gradually disappear. The functional form

_{ij}*f*(|

*Q*|) is given by

*f*(|

*Q*|) = |

*Q*|

^{γ}/(1 + |

*Q*|

^{γ}), which describes a sigmoidal response where γ is a parameter that controls the nonlinearity of feedback (γ > 0). A typical simulation result with

*I*

_{0}= 2 and γ = 1.8 (Fig. 4) gave a network with features similar to those of both the

*Physarum*system and the rail network (Fig. 2, C and D, respectively).

In general, increasing *I*_{0} promoted the formation of alternative routes that improved performance by reducing MD_{MST} and made the network more fault-tolerant, but with increased cost (Fig. 3, A to C, and fig. S1I). Low values of γ also gave a greater degree of cross-linking with an increased number of Steiner points (fig. S2, A and B). Conversely, decreasing *I*_{0} (fig. S1A) or increasing γ (fig. S2I) drove the system toward a low-cost MST (Fig. 2E), but with an inevitable decrease in resilience (Fig. 3B). The final network solution also depended slightly on the stochastic variation assigned to the starting values of *D _{ij}*. Judicious selection of specific parameter combinations (

*I*

_{0}= 0.20, γ = 1.15) yielded networks with remarkably similar topology and metrics to the Tokyo rail network (fig. S2B). However, by increasing

*I*

_{0}to 2 and γ to 1.8, the simulation model also achieved a benefit/cost ratio (α = FT/TL

_{MST}) that was better than those of the rail or

*Physarum*networks, reaching a value of 0.7 with an almost identical transport efficiency of 0.85 (Fig. 3C). Conversely, the consequence of the increased TL

_{MST}observed in the rail or

*Physarum*networks would be to confer greater resilience to multiple simultaneous failures at the expense of increased cost, rather than tolerance to a single disconnection that is evaluated by FT

_{MST}.

Our biologically inspired mathematical model can capture the basic dynamics of network adaptability through iteration of local rules and produces solutions with properties comparable to or better than those of real-world infrastructure networks. Furthermore, the model has a number of tunable parameters that allow adjustment of the benefit/cost ratio to increase specific features, such as fault tolerance or transport efficiency, while keeping costs low. Such a model may provide a useful starting point to improve routing protocols and topology control for self-organized networks such as remote sensor arrays, mobile ad hoc networks, or wireless mesh networks (*24*).