I seem to have developed a reputation for hating networks, but really, it's just tough love. Complex, adaptive, self-organizing networks are fascinating (and inspired the title of this blog), and they deserve a rigorous scientific treatment. Decentralized control mechanisms are incredible, and, although they're all around us, they go completely against our instincts for good, hierarchical design for control systems. How does a cell adapt to environmental signals, in the absence of a brain or CPU? And how do we make our own, human-built networks as self-adaptive and robust as biological ones? In other words (for those of you who've endured lengthy lectures on the subject in physiology class), how do you effectively engineer homeostasis?

In a recent paper in Science, a group of Japanese researchers from Hokkaido University studied the network-building prowess of the slime mold Physarum polycephalum. Physarum is basically a giant ameboid rat, a single-celled organism that can find the quickest way through a laboratory maze to find food. The scientists describe their reason for studying this creature:

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.

Physarum is essentially one giant, complex cell with multiple nuclei. It sends out projections in search of food, in the process developing a nutrient transport network comprised of tubes that circulate nutrients around the entire organism. That nutrient transport network needs to be both efficient in terms of energy usage, but also robust to breakdowns. 

Physarum's network building ability has been honed over an immense period of evolutionary time. So how does it stack up against human network designers? The researchers wanted to see how an amoeba would design Japan's railway network. They put this critter, a giant yellow blob, onto a map of Japan, right on top of Tokyo. (The potential for a great Godzilla sequel is in here somewhere.) The scientists then placed food sources on various cities on the map, and waited to see what kind of network the amoeba would build.

Eventually, the amoeba established a network on the map, with nodes at the food sources (placed at city locations), and branches connecting the nodes in various ways. Using a set of network performance metrics that include cost, transport efficiency, and robustness, the scientists compared the Physarum network and the real Japanese rail network to minimal spanning tree, the shortest possible network that connects all of the cities on the map, which can be derived from graph theory.

The results:

Cost: As expected, the Physarum and the Rail networks had higher cost scores than the minimal network, but they were both much less than half the cost of a maximally connected network. If you give the minimal network a cost score of 1, the Physarum network scored a 1.75, the rail network a 1.8, and the maximal network a 4.6. The biological and rail networks come out about even in this matchup.

Transport performance: A minimal network costs the least, but, since it's minimal, it doesn't perform as well as more connected networks. The rail and Physarum networks scored a 0.85 (relative to a 1 for the minimal network) on transport performance. (The authors didn't list the transport performance of the maximal network.) Again, evolution and human design match up evenly.

Fault tolerance: If you break a link in the network, how likely are you to isolate a city? The rail network does quite well here, with only 4% of potential faults isolating a city, compared to 14% for Physarum. This matchup is a little unfair to the amoeba, because it probably has different design goals - the definition of fault tolerance used here is probably not one that Physarum is optimized for.

Overall, evolution and design match up pretty well. But there is is a catch: the Physarum numbers I've noted here are averages, and some individual Physarum networks did better than the rail network. The best amoeba does better than human designers.

To learn how to build these better networks, the scientists modeled the Physarum network construction process to see if they could discover some helpful principles behind Physarum's success. The punchline is that, in their simulations, the researchers could design networks significantly better than the existing rail network.

The Model

The beauty of the scientists' model of Physarum network building derives from the fact that it abstracts away finer biochemical details and captures Physarum behavior by implementing simple, local rules at section of the network. Local rules are a hallmark of self-organizing system; there is no central authority imposing system-wide rules. The researchers set the environmental conditions, and the structure then emerges spontaneously from those conditions.

When you put Physarum down on a map of the Tokyo greater metro area, it covers the entire map with a fine mesh of small, slimy tubes. Then, in a process of selective culling and positive feedback, it reabsorbs some tubes while thickening others. The result is that, instead of a fine, uniform mesh, you have a network of high-traffic tubes.

The researchers' model works the same way. They superimposed a fine mesh of virtual nodes and edges on a map of metro Tokyo. Some of those nodes just happen to fall on food sources, which, in the Physarum experiments were literally pieces of oatmeal placed on top of city (or town or suburb) locations on the map. In the computer simulations, virtual food sources are superimposed on cities.

In other words, you start out with a map which contains food sources, and you cover the map with a fine mesh.

Next, the researchers implemented a simple fluid dynamics model to simulate the process of culling or reinforcing tubes in the network. Why fluid dynamics? Remember, the edges in the network represent cellular tubes that transport nutrient-carrying cytoplasm from one node to another in the organism. So the researchers modeled fluid flow through the tubes.

Fluid flow, in this model, depends on two variables (as well as on several fixed parameters): the radius of the tube, and the proximity to a food source or sink. Nutrients flow from a food source (a point on the map chosen by the researchers) to a food sink (another point chosen by the researchers). Therefore, tubes that connect food sources and sinks experience more flow than tubes far away from sources or sinks.

Now for the local rules so critical for models of self organization: The radius of any tube evolves according to how much flow it experiences. Tubes that experience more flow grow in size, leading to a capacity for even more flow - a positive feedback loop. Tubes that experience no flow shrink, until eventually they just disappear.

By specifying the location of food sources and sinks, and then letting the local rules of radius evolution operate, you eventually end up with a highly efficient transport network superimposed on a map of the Tokyo area. You can choose to optimize whatever outcome you're interested in: cost benefit ratio, transport efficiency, fault tolerance, whatever - you can make decisions about the outcome, and then evolve a network that matches your desires.


The scientists suggest that their model will be useful for real railway design. Obviously that's still a few steps down the road, but they've got a beautifully simple, biologically inspired model that can, in principle anyway, design railway networks that beat the existing Tokyo rail network. I'd put my money on the amoeba.



Read the feed: