elimination). We show that such rates optimize the efficiency and robustness of distrib-
uted routing networks under several models. We also present an application of this strat-
egy to improve the design of airline networks.
Introduction
Neural networks in the brain are formed during development using a pruning process that
includes expansive growth of synapses followed by activity-dependent elimination. In humans,
synaptic density peaks around age 2 and subsequently declines by 50–60% in adulthood [1–4].
It has been hypothesized that synaptic pruning is important for experience-dependent selection
of the most appropriat e subset of connections [1, 5], and it occurs in many brain regions and
species [6–9]. This strategy substantially reduces the amount of genetic information required
to code for the trillions of connections made in the human brain [10]. Instead of instructing
precise connections, more general rules can be applied, which are then fine-tuned by activity-
dependent selection. Although the molecular and cellular mechanisms driving activity-depen-
dent pruning have been extensively investigated [1, 3, 4], global aspects of this highly-distrib-
uted process, including the rate at which synapses are pruned, the impact of these rates on
network function, and the contrast of pruning-versus growth-based strategies commonly used
in engineering to construct networks, has not been studied.
While the specific computations performed within neural and engineered networks may be
very different, at a broad level, both types of networks share many goals and constraints [11].
First, networks must propagate signals efficiently while also being robust to malfunctions (e.g.
spike propagation failures in neural networks [12–14]; computer or link failures in communi-
cation networks [15]). Second, both types of networks must adapt connections based on pat-
terns of input activity [16]. Third, these factors must be optimized under the constraint of
distributed processing (without a centralized coordinator) [17, 18], and using low-cost solu-
tions that conserve important metabolic or physical resources (e.g. number of synapses or wir-
ing length in biological networks; energy consumption or battery-life in engineered networks)
[19–21]. For example, on the Internet or power grid, requests can be highly dynamic and vari-
able over many time-scales and can lead to network congestion and failures if networks are
unable to adapt to such conditions [22, 23]. In wireless or mobile networks, broadcast ranges
(which determine network topology) need to be inferred in real-time based on the physical dis-
tribution of devices in order to optimize energy efficiency [24]. Although optimizing network
design is critical for such engineered systems across a wide range of applications, existing algo-
rithms used for this problem are not, to our knowledge, based on experience-based pruning, in
part because adding connections that will soon be eliminated is considered wasteful.
Here, we develop a computational approach informed by experimental data to show that
pruning-inspired algorithms can enhance the design of distrib uted routing networks. First, we
experimentally examined developmental pruning rates in the mouse somatosensory cortex, a
well-characterized anatomical structure in the mouse brain [25]. Using electron microscopy
imaging across 41 animals and 16 developmental time-points, coupled with unbiased and
high-throughput image analysis [26], we counted over 20,000 synapses and determined that
pruning rates are decreasing over time (i.e. early, rapid synapse elimination is followed by a
period of slower, gradual elimination). Next, to translate these observations to the computa-
tional domain, we developed a simulated environment for comparing algorithms for distrib-
uted network construction. We find that over-connection followed by pruning leads to
significant improvements in efficiency (routing distance in the network) and robustness
Pruning Optimizes Construction of Efficient and Robust Networks
PLOS Computational Biology | DOI:10.1371/journal.pcbi.1004347 July 28, 2015 2 / 23
Foundation award nos. DBI-0965316 and DBI-
1356505 to ZBJ. The funders had no role in study
design, data collection and analysis, decision to
publish, or preparation of the manuscript.
Competing Interests: The authors have declared
that no competing interests exist.