Evolutionary selection of network structure and function

Evolutionary Selection of Network Structure and Function Larry Yaeger1 , Olaf Sporns2 , Steven Williams1, Xin Shuai1 and Sean Dougherty3 1 School of Informatics and Computing and 2 Department of Psychological and Brain Sciences Indiana University, Bloomington, IN 47408 3 Open source contributor [email protected] Abstract It has been argued that physical constraints—evolutionary pressures to reduce overall wiring length (Mitchison, 1991; We explore the relationship between evolved neural network structure and function, by applying graph theoretical tools Cherniak, 1995) and to maximize connectivity while min- to the analysis of the topology of artificial neural networks imizing volume (Murre and Engelhardt, 1995)—might ex- known to exhibit evolutionary increases in dynamical neu- plain key aspects of biological brain connectivity. But it ral complexity. Our results suggest a synergistic convergence is unlikely that evolutionary pressure on wiring alone is re- between network structures emerging due to physical con- sponsible for the detailed patterns of connectivity seen in straints, such as wiring length and brain volume, and optimal network topologies evolved purely for function in the absence biological brains (Sporns et al., 2000). Thus one is led to of physical constraints. We observe increases in clustering ask how natural selection would act upon the topological coefficients in concert with decreases in path lengths that characteristics of nervous systems in the absence of phys- together produce a driven evolutionary bias towards small- ical constraints, and whether such functional evolutionary world networks relative to comparable networks in a passive pressures are opposed to, independent of, or aligned with null model. These small-world biases are exhibited during the same periods that evolution actively selects for increasing physical evolutionary pressures. neural complexity (also during which the model’s agents are behaviorally adapting to their environment), thus strengthen- ing the association between small-world network structures In previous work using the Polyworld artificial life sys- and complex neural dynamics. We also introduce a new mea- sure of path length in graphs, “normalized path length”, that is tem (Yaeger, 1994) we have shown that when agents whose better behaved than existing metrics for networks comprised behaviors are controlled by a genetically prescribed artifi- of disjoint subgraphs and disconnected nodes, and a novel cial neural network are subject to natural selection, the net- method of quantifying the degree of evolutionary selection works’ dynamical neural complexity increases over evolu- for small world networks, “small-world bias”. tionary time (Yaeger and Sporns, 2006), the networks’ com- plexity will be actively selected for by evolution (Yaeger Introduction et al., 2008), and periods of neural complexity growth cor- Dynamical processes in networks are unavoidably influ- respond to periods of behavioral adaptation of the agents to enced by the networks’ underlying topologies. As the study their environment (Yaeger, 2009). of networks has come to pervade all of science, a need has arisen to understand this relationship between the anatomi- cal structure of networks and the dynamical functions they We now seek to understand the underlying network carry out (Strogatz, 2001). topologies that give rise to this evolved functional complex- Small-world properties have been shown (Watts and ity. Preliminary results for several graph theoretical met- Strogatz, 1998) to characterize many networks of interest, rics from one simulation suggested (Lizier et al., 2009) that including biological nervous systems. Small-world net- evolutionary trends in Polyworld mirrored those in biolog- works of Hodgkin-Huxley neurons have been shown (Lago- ical neural networks (and successfully related anatomical Fernández et al., 2000) to provide the best features of both networks to inferred functional networks). We will more random networks (fast system response) and regular net- fully characterize those evolutionary trends, determine their works (coherent oscillations). Small-world-ness has also robustness and statistical significance, quantify the small- been shown (Sporns et al., 2000) to be highly correlated with world-ness of those trends, and confirm the role of natural dynamical complexity in artificial neural networks evolved selection (as opposed to random drift, in a “driven” vs. “pas- specifically for complexity. In the biological realm, cortical sive” sense (McShea, 1996)) in the shaping of those trends. connection matrices for macaque visual cortex and rat cortex This allows us to characterize the relationship between evo- have been shown (Sporns et al., 2000) to exhibit both small lutionary pressures on brain structure due to functional opti- world anatomical properties and high dynamical complexity. mization vs. physical constraints.  Tools and Techniques Complexity Polyworld Our primary tool for analyzing neural dynamics is an infor- mation theoretic measure of neural complexity proposed by Polyworld is an ecosystem model in which the agents are Tononi et al. (1994) and introduced in a simplified and more controlled by artificial neural networks using a firing rate computationally tractable form in (Tononi et al., 1998). Re- neuron model performing Hebbian learning at the synapses. ferred to throughout as “complexity” (aka “TSE complex- The wiring diagrams of these networks are the primary sub- ity”, for the initials of its inventors), the measure captures a ject of evolution in the system, through a genetic encoding trade-off between integration (cooperation) and segregation of a generative model of network architectures. This ge- (specialization) in any system of random variables, such as netic encoding describes the network topology in terms of a the temporal traces of our agents’ neural activations. Max- number of neural groups, containing a number of excitatory imally complex networks exhibit a high degree of both in- and inhibitory neurons, wired together with genetically de- tegration and segregation at multiple scales. Though not termined connection densities, ordered-ness of connections, presented here, we have previously demonstrated (Yaeger, and learning rates. By eschewing any particular model of 2009) that complexity is actively selected for, in a driven, ontogenetic development, Polyworld avoids the biases in- biased fashion, during periods of behavioral adaptation of herent in such a model choice. Further, instead of evolving the agents to their environment, which corresponds to ap- specific network topologies, Polyworld forces evolution to proximately the first 7,000 time steps in these experiments. select for useful statistics of neural connectivity. During this period complexity increases much more rapidly Vision, current energy level, and a randomly firing neuron in the driven runs than in the passive runs, but once a “good are the inputs to the network. A suite of primitive behaviors enough” solution emerges and begins to propogate through- (move, turn, eat, mate, attack, light, focus) are the outputs. out the population, driven complexity plateaus, while pas- All agent actions consume energy, which must be replen- sive complexity continues its random walk to higher values. ished by consuming food from the environment, or by killing and eating other agents. Normally there are per-neuron and Graph Theoretical Metrics per-synapse energy costs, but these have been eliminated For current purposes we are interested primarily in three for this study so as not to impose any pseudo-physical con- graph theoretical metrics. Two of them—clustering coef- straints on network topology. Survival and reproduction, ficient and characteristic path length—were used by Watts variation and selection, are the only driving forces, so Poly- and Strogatz (1998) to define and characterize small-world world acts as a model of natural selection, with no fitness networks. The third is a quantitative means of characterizing function, rather than in the manner of a genetic algorithm the degree of small-world-ness exhibited by a network intro- (though that is possible, if desired). duced by Humphries et al. (2006). Throughout we will talk In these experiments Polyworld is used to produce paired about our neural networks as graphs, which can be described runs in which an initial, normal “driven” run is followed by by the number of nodes (aka vertices or neurons) and the a “passive”, null-model run. (The terms driven and passive number of edges (aka links or synapses) that connect them. are used in the sense proposed by McShea (1996).) In the Clustering coefficient (CC) is a local measure of cliquish- passive run, agents cannot reproduce or die on their own; ness in a graph, and characterizes the degree to which a rather, pairs are chosen for reproduction at random and in- node’s neighbors are likely to be neighbors of each other dividuals are killed at random to match the birth and death (where “neighbor” means a link exists between the nodes). events of the original driven run, thus removing the effects In social networks this would be the degree to which friends of selection, while retaining population statistics and levels of a common friend are likely to be friends of each other. It of genetic variation that are equivalent to those in the driven is defined at each node as the fraction of possible links be- run. This allows the direct comparison of driven vs. passive, tween neighbors that are actually present in the graph, and natural-selection vs. random-walk evolutionary trajectories. defined for the entire network as the average of this fraction See (Yaeger et al., 2008; Yaeger, 2009) for more details. over all nodes in the graph. The activation of every neuron at every time step for every Characteristic path length (CPL), also called average agent is recorded to disk as simulations progress, as is the shortest path length, is a global measure of the average sep- neural architecture of every agent. Thus we are able to study aration between all node pairs in a graph—an estimate of both the structure and the function of the evolved neural net- how far it is from any one node to another. The average dis- works, under conditions in which either natural selection or tance to all other nodes is calculated for each node, and then increasing variance due to a random walk are holding sway. averaged over all nodes. The Polyworld source code and data analysis tools are Watts and Strogatz (1998) identified small-world net- available at http://sourceforge.net/projects/polyworld/ and works by their combination of high clustering and low path instructions for installing and building Polyworld are at length. By contrast, though regular lattice networks also ex- http://beanblossom.in.us/larryy/BuildingPolyworld.html. hibit high clustering, they typically have high path lengths, since moving from one node to another requires the traversal are seen as close neighbors, while nodes that only weakly in- of all intervening nodes and links. And while random graphs fluence each other are seen as distant neighbors, and nodes tend to have low path lengths, since any given node is only a that do not directly affect each other at all (have zero weight) few random hops away, they usually exhibit low clustering. are infinitely far apart (though they may be reachable indi- Small-world index (SWI) is a quantitative measure of rectly, through other nodes and links). For our other fun- small-world-ness introduced by Humphries et al. (2006). To damental metric, clustering coefficient, we use the original calculate SWI one computes CC and CPL for the actual neural network weights on the edges. graph, CC and CPL for a corresponding random graph (or A question also arises as to which neural network nodes ensemble of random graphs as done here), and compares the to include in the graph being analyzed. One obvious answer ratios of actual to random measurements as follows: is all of them. However, the sensory nodes have an unusual constraint—zero in-degree (no incoming connections)—and γ = CC/ hCCr i (1) their activations are purely determined by what the agent senses in its environment rather than what happens within λ = CP L/ hCP Lr i (2) the neural network. Another answer, then, is the non- s = γ/λ (3) sensory neurons; i.e., all internal and output/behavioral neu- where hCCr i and hCP Lr i are the ensemble averages of CC rons. In our complexity work we have referred to this set and CP L over some number of random graphs having the of non-sensory neurons as the “processing” neurons. Ac- same number of nodes and edges as the original graph, and s cordingly, we have carried out our graph theoretical analy- is the desired SWI.1 SWI captures the degree to which clus- ses looking at both cases: all (A) neurons and processing (P) tering and path length in the actual, original graph vary, in neurons. the appropriate directions, from the values seen in compara- Finally, especially early on in our simulations, some of ble random graphs. The more small-world a network is, the the graphs are quite small and consist of multiple compo- greater its SWI will be above 1.0. nents (disconnected sub-graphs) and even contain discon- These metrics are most frequently applied to undirected nected neurons. It turns out that CPL behaves poorly and er- graphs (a given edge connects in both directions), often with ratically in this situation. This is due to its treatment of inter- binary edges (either present or not). However, neural net- node distances between disconnected nodes as infinite. Thus works importantly have both weighted and directed edges. path lengths are computed only within each disconnected Fortunately these metrics extend straightforwardly to sup- subgraph and the metric can exhibit sudden large changes as port the analysis of weighted, directed (WD) graphs, but subgraphs become connected or disconnected and shortest their application to such networks has been less well char- paths span much larger or smaller subsets of nodes. acterized than for binary, undirected (BU) graphs and, in- A length metric proposed by Marchiori and Latora (2000), deed, there turn out to be some issues applying them to WD connectivity length (CL), uses inverted lengths to calculate graphs. (Such as a greater prevalence of disconnected nodes the harmonic (rather than arithmetic) mean of average short- in WD graphs.) Accordingly, we analyzed our networks est path length, and better handles multiple components and treating them both as BU and WD graphs. disconnected nodes. However, by effectively including all Neural network edge weights are also signed—positive those infinities (as zeroes), it can compress the distinctions for excitatory connections, negative for inhibitory connec- between sparsely connected and disconnected graphs. tions. Unfortunately, few graph theoretical metrics extend We therefore devised, and introduce here, a new length well to signed graphs. So for these analyses we have made metric, normalized path length (NPL), that appears to be bet- the less than desirable, but simple and common, approxima- ter behaved than either CPL or CL for the class of graphs we tion of using the absolute values of the network weights on are analyzing, though it too has some quirks (a sensitivity to the graph edges. edge weights that makes it somewhat noisy in its WD form). The fact that one of our key metrics, path length, is based To calculate NPL, node pairs that have no path between on distances between nodes, yet our neural networks have them are assigned a maximum path length lmax defined weights, not distances, associated with their connections, as N/wmax , rather than infinity, where N is the number presents another small conundrum. We again take the sim- of nodes in the graph and wmax is the maximum possible plest, most common approach, and invert the weights to synaptic weight in our neural networks. (For binary net- provide a distance measure. Thus a strong weight, which works the greatest possible path length is N − 1, hence this produces a strong influence, after inversion corresponds to a value of N is one that cannot occur by any means other short distance. So nodes that strongly influence each other than disconnection.) Inverting to convert weight to distance, 1 we also define a minimum path length lmin , which is just Humphries used a single random graph corresponding to each original graph, but there is sufficient variance in CC and CPL 1/wmax . We then proceed to compute CPL normally, limit- amongst graphs with the same numbers of nodes and links that we ing path length to the defined maximum, and normalize first have chosen to use ensemble averages instead. by subtracting the minimum path length and then dividing by the difference between the maximimum and minimum anatomies were recorded for all agents. Agents were as- path lengths. Thus, in terms of CPL, NPL may be written as signed to temporal bins corresponding to 1,000 time steps, follows: according to the time of their death. This type of binning was necessary for our complexity N P L = (CP L∗ − lmin )/(lmax − lmin ) (4) studies, since an agent’s neural complexity can only be ac- curately computed after the completion of its neural activa- where CP L∗ is a normally calculated CPL using lmax as the tion time series—its death. We have retained this binning maximum possible distance between nodes. Or expressed in in our graph theoretical analysis so we can directly compare terms of path lengths: structural and functional results. Complexity and graph theoretical metrics were calcu- X N lated for each agent and averaged to produce a population min(lij , lmax ) mean (and standard deviation) in each temporal bin, for each i, j = 1 driven and passive run. In addition, for each agent’s actual j 6= i neural network, 10 graphs with an identical node count, edge N (N −1) − lmin NPL = (5) count, and distribution of weights were generated randomly, lmax − lmin and the means of the graph theoretical measures for these where lij is the shortest path from node j to node i. NPL is networks were used to characterize the structure of a ran- guaranteed to lie between 0.0, for a fully connected graph, dom graph corresponding to each actual graph. and 1.0, for a fully disconnected graph (a collection of nodes As configured for these runs, a maximum of 217 neurons with no links between them), and has proven to be well and 45,584 edges were possible. Evolved neuron counts behaved for graphs with multiple components and discon- ranged from 12 to 187, with a mean of 56. Evolved edge nected nodes (as well as for the more commonly analyzed counts ranged from 33 to 13,081, with a mean of 1,077. In strongly connected graphs). all, over half a million evolved graphs were analyzed using Since none of our three length metrics is “perfect” and 42 different metrics (counting metrics for different neuron NPL is entirely new, wherever a length metric is calcu- sets and graph types as distinct), and in excess of five mil- lated or used, we examine all three, and refer in general lion random graphs were analyzed using 24 of those metrics. to simply path length. Thus for each metric we treat the graph as consisting of either the A neurons or the P neu- Results and Discussion rons and we treat the graph edges as being either BU or Given that we know complexity increases over evolution- WD, and for length metrics we look at each of CPL, CL, ary time in Polyworld and is, in fact, actively selected for and NPL. Different neuron sets, graph types, and length by evolution under certain conditions, our intention is to de- metrics usually agree on common trends, but do sometimes velop a better understanding of the structural characteristics provide different insights into the algorithms and architec- that give rise to these complex network dynamics. To this tures. Unfortunately, due to space constraints we cannot end we start by examining clustering coefficient. show all variations of all metrics. A complete set of plots The various neuron sets and graph types tell much the of these metrics may be obtained as supplementary material same story for clustering coefficient, as represented by the here: http://informatics.indiana.edu/larryy/alife12 sup.zip. P,WD results in Figure 1. Initially CC is actively selected The abbreviations defined here (CC, CPL, CL, NPL, SWI, for by evolution, as evidenced by the more rapid rate of in- A, P, BU, WD) and another new metric (SWB) defined later crease in the driven runs than in the passive runs. But once a are consistently applied in these plots as well as this paper. “good enough” solution emerges and spreads throughout the All graph theoretical metrics were calculated using our population, CC in the passive populations surpasses that in new C++ implementation (bct-cpp) of the Brain Connectiv- the driven populations. The period during which there exists ity Toolbox (BCT) MATLAB module (Rubinov and Sporns, a statistically significant bias for high CC in the driven runs 2010). The original BCT may be found at http://www.brain- is from about t=1000 to t=11000. This mimics but extends connectivity-toolbox.net/ and bct-cpp may be found at the trend previously observed in neural complexity (Yaeger http://code.google.com/p/bct-cpp/. et al., 2008), as complexity’s period of statistically signif- icant differences lasted only from about t=1000 to t=4000, Simulations and Data Acquisition and passive complexity caught up to driven complexity by A set of 10 paired simulations, differing only in initial ran- about t=7000. The period of behavioral adaptation is ap- dom number seeds, were run in driven and passive modes; proximately t=1000 to t=7000 (Yaeger, 2009). i.e., 20 simulations in all. Each simulation ran for 30,000 A traditional means of looking for meaningful graph time steps (approximately 400 generations) with a popu- structure is to compare suitable graph theoretical metrics lation varying from 90 to 300 agents. Temporal traces computed for one’s actual graphs to the same metrics calcu- of neural activations and structural descriptions of neural lated for comparable random graphs. We examined driven  Driven vs. Passive -- Clustering Coefficient (p,wd) 0.16 0.14 0.12 (1 - p-value) Dependent Student’s T-test Clustering Coefficient (p,wd) 0.1 0.08 0.06 0.04 1.0 0.02 0.95 0 0.8 0 5000 10000 15000 20000 25000 30000 Timestep Driven Passive Figure 1: Driven vs. passive clustering coefficient as a function of time. Light solid lines show mean population CC for each driven run. Light dashed lines show mean population CC for each passive run. Heavy lines show meta-means of all ten runs for the corresponding line style. Light dotted line at bottom shows dependent 1−p-value for a Student’s T-test with typical p > 0.05 statistical significance indicated by the horizontal line at p = 0.95. vs. random and passive vs. random CC, but do not include than it does in the passive runs, but as that “good enough” the results here due to space considerations. CC was sub- solution becomes weakly stabilized in the driven runs, path stantially and statistically significantly greater in the actual length in the passive runs drops below that in the driven runs. evolved graphs than in the corresponding random graphs. In fact, path length in the passive runs drops nearly to the Curiously, this difference was observed in passive vs. ran- level seen in random graphs (not shown). The initial period dom as well as driven vs. random graphs, which we take of driven vs. passive statistical significance is from about as a warning that there is a bias present in our genetic en- t=1000 to t=7000, again corresponding well to the period of coding mechanism towards at least some degree of clus- complexity growth and behavioral adaptation. tering. Given that the encoding expresses connectivity be- Thus we have seen that during the period of growth in the tween groups of neurons, this seems reasonable. This re- complexity of the agents’ neural dynamics there is a corre- sult suggests that the differences we observe between driven sponding, statistically significant growth in clustering coef- and passive results may be lower than one might find with ficient and reduction in path length. High clustering coeffi- a completely unbiased encoding scheme. It also means we cient and low path length are the defining characteristics of are probably better off focusing on driven vs. passive results a small-world network. So our results are suggestive of a se- than driven vs. random results, since the passive runs repre- lective pressure towards small-world networks, and provide sent a more appropriate and tightly constrained null model support for a correlation between small-world structure and than do the random graphs. complex function. Turning to path length, the stories told by NPL and CL To investigate this trend towards small-world-ness, we are very similar to each other and to that told by CC and turned to the small world index proposed by Humphries complexity. CPL is less consistent, due to its previously et al. (2006). As it was originally formulated, SWI is based discussed shortcomings, showing generally the same trends, on comparing CC and CPL in actual graphs vs. random but without much statistical significance in both WD analy- graphs. However, given the problems previously discussed ses, large and greatly extended statistical significance in the in applying CPL to our small, sparse, multi-component P,BU analysis, and a result much like the other length met- graphs with disconnected nodes, the standard version of rics in the A,BU analysis. Figure 2, though somewhat noisy, SWI proved to be uninformative, displaying little consis- shows the typical trends in path length, using NPL. Path tency amongst the different neuron sets and graph types we length initially drops much more rapidly in the driven runs analyzed and with sufficient noise to render some results un-  Driven vs. Passive -- Normalized Path Length (p,wd) 1 0.9 0.8 (1 - p-value) Dependent Student’s T-test Normalized Path Length (p,wd) 0.7 0.6 0.5 0.4 0.3 1.0 0.2 0.95 0.1 0.8 0 5000 10000 15000 20000 25000 30000 Timestep Driven Passive Figure 2: Driven vs. passive normalized path length as a function of time. Light solid lines show mean population NPL for each driven run. Light dashed lines show mean population NPL for each passive run. Heavy lines show meta-means of all ten runs for the corresponding line style. Light dotted line at bottom shows dependent 1−p-value for a Student’s T-test with typical p > 0.05 statistical significance indicated by the horizontal line at p = 0.95. interpretable. So we developed alternative formulations of sought to define a metric that would more directly cap- SWI, using our better behaved length metrics, CL and NPL. ture and quantify the apparent bias towards high clustering Curiously, some of the inconsistencies were present in these and short path lengths evidenced in all of the raw cluster- formulations as well. ing and path length data. To this end we have defined a We could have cherry-picked an SWI result based on NPL new “small-world bias” (SWB) metric that takes its form for the A neuron set and BU graph type that looks very much from Humphries et al’s SWI, but directly compares driven to like we expected, with a statistically significantly higher passive—instead of actual to random—clustering and length growth rate in SWI for the driven runs compared to the pas- metrics: sive runs. However, the P,WD version of this metric, even γ = hCCdriven i / hCCpassive i (6) using NPL, actually reverses the roles of driven and passive λ = hLdriven i / hLpassive i (7) (in a clear, although not significant fashion). We believe that the small and weakly connected character of our early nets SW B = γ/λ (8) are contributing to these difficulties, which explains why the where L can be any suitable length metric (such as CPL, CL, problems are most exacerbated in the nets with the most lim- or NPL). The ensemble averages are taken over the usual ited set of connections (P,WD), but are not entirely satisfied population of agents expiring during a given temporal epoch. with any of the explanations we have devised so far and feel The numerator captures the degree to which a driven run fa- this needs further investigation, which is why none of these vors high clustering relative to a passive run. The denomina- results are included here (though they are all present in the tor captures the degree to which a driven run favors low path supplemental materials). length relative to a passive run. Accordingly, when SWB The actual numerical values of all these different versions exceeds 1.0, the driven run is at least slightly biased towards of SWI are greater than 1.0 for the driven runs, ranging small world network characteristics relative to a passive run. from 1.5 to as much as 32.0, depending on the specific data It is not actually possible (because driven and passive graph and specific form of the metric, and the values are generally sizes are different), but if one could calculate Humphries (though not always) greater for the driven runs than they are et al. (2006)’s SWI using the same random-graph basis for for the passive runs. So all we can really take away from the corresponding terms in SW Idriven and SW Ipassive , then SWI analysis is that the evolved nets are small-world nets. take their ratio, all the random-graph terms would cancel Given the difficulties and inconsistencies with SWI, we out and what one would be left with is SWB.  Small World Bias (p,wd,cl) 4 3.5 Small World Bias (p,wd,cl) 3 2.5 2 1.5 1 0.5 0 0 5000 10000 15000 20000 25000 30000 Timestep Driven Figure 3: Small-world bias as a function of time. Where SWB is > 1.0, the driven run is exhibiting a bias towards small-world networks relative to the passive run. Precise numerical values and periods of bias vary, but the ity (Tononi et al., 1994). resultant trends in SWB are remarkably consistent for both Our work demonstrates that even in the absence of physi- sets of neurons (A and P), both graph types (BU and WD), cal constraints on wiring length and brain volume, evolution and all length metrics (CPL, CL, and NPL). Figure 3 shows selects for small-world networks in order to enhance brain SWB based on connectivity length for the processing neu- function. The resulting networks thus combine the predom- rons treated as weighted, directed graphs. There is a strong inantly local connectivity imposed by physical volume con- (> 1.5) bias towards small-world-ness from about t=2000 straints (Murre and Engelhardt, 1995) with the short path to t=7000, corresponding to the previously observed period lengths necessary to satisfy fast response time requirements of growth in neural complexity and behavioral adaptation to (Lago-Fernández et al., 2000), despite a lack of physical the environment. Once the agents have adapted to their en- constraints in their evolution. We suggest that humans (and vironment evolutionary pressure on complexity diminishes, all biological organisms with even modestly complex ner- leading to the reduction in SWB at later times. vous systems) are the fortunate beneficiaries of these con- vergent and synergistic physical and functional constraints. Conclusions Rather than physical constraints acting to limit brain func- We have shown strong, reproducible evolutionary biases to- tion, our evidence suggests that physical constraints work in wards high clustering coefficients, short path lengths, and concert with evolutionary pressures to select neural topolo- small-world-ness in driven runs subject to natural selection gies that foster more complex, adaptive behaviors. relative to passive runs in which natural selection is dis- abled. These structural, graph theoretical trends correspond Future Directions to previously observed evolutionary trends in the dynamical There is one instance in which increases in clustering coef- complexity of neural function and behavioral adaptation of ficient are not correlated with increasing neural segregation agents to their environment, thus strengthening the associa- and complexity, which is progression towards a single large tion between small-world-ness and complexity. cluster. Since we do see correlated increases in neural com- Short path lengths contribute to increased “integration” plexity our clustering increases cannot be the result of net- of neural function throughout the brain. Clustering can con- work topologies approaching a single large cluster, however tribute to and is often evidence of increased “segregation” in the future we intend to look into modularity metrics that of specialized neural functions in the brain. It is this com- more directly address community structure. Our expecta- bination of increasing integration and segregation that pro- tions are that structural modularity and functional complex- duces the measured increases in dynamical neural complex- ity will be positively correlated. However, preliminary in- consistent and contradictory results have led to the realiza- lations in Small-World Networks. Phys. Rev. Lett., 84:2758– tion that standard measures of modularity, such as those due 2761. to Newman (2006) and Blondel et al. (2008), are not well Lizier, J. T., Piraveenan, M., Dany, P., Prokopenko, M., and Yaeger, suited to the types of networks generated early in our simu- L. S. (2009). Functional and Structural Topologies in Evolved Neural Networks. In Kampis, G. e. a., editor, Proceedings of lations and we believe values of these metrics are artificially the Tenth European Conference on Artificial Life. Springer elevated for such graphs. Further research is required to ei- Verlag, Heidelberg. ther develop better ways to characterize community struc- Marchiori, M. and Latora, V. (2000). Harmony in the Small-World. ture in these networks or determine suitable subsets of these Physica A, 285(3-4):539–546. graphs to which the standard modularity metrics may rea- McShea, D. W. (1996). Metazoan complexity and evolution: Is sonably be applied, perhaps only after having evolved be- there a trend? Evolution, 50:477–492. yond certain minimum size and connectivity constraints. Milo, R., Itzkovitz, S., Kashtan, N., Levitt, R., Shen-Orr, S., Ayzen- We further hope to identify more discriminating struc- shtat, I., Sheffer, M., and Alon, U. (2004). Superfamilies of tural metrics, that will be reliably predictive of functional Evolved and Designed Networks. Science, 303:1538–1542. complexity. We also seek to improve upon our current tech- Mitchison, G. (1991). Neuronal branching patterns and the econ- nique of ignoring (by taking absolute values) what is likely omy of cortical wiring. Proceedings of the Royal Society of London. Series B: Biological Sciences, 245(1313):151–158. to be a crucial distinction between the positive and nega- tive weights associated with excitatory and inhibitory con- Murre, J. M. J. and Engelhardt, D. P. F. (1995). The connectiv- ity of the brain: multi-level quantitative analysis. Biological nections. One particular direction we intend to explore may Cybernetics, 73:529–545. address both aims at once, which is distributions of signed Newman, M. E. J. (2006). Modularity and community structure in motifs. Network motifs, such as those advanced by Milo networks. Proc. Natl. Acad. Sci. U. S. A., 103:8577–8582. et al. (2004) and related to small-world properties and com- Rubinov, M. and Sporns, O. (2010). Complex network measures plexity by Sporns and Kötter (2004), are typically treated as of brain connectivity: Uses and interpretations. NeuroImage, unsigned, though there has been some discussion of small In Press, Corrected Proof:–. subsets of signed motifs in genetic transcription and other bi- Sporns, O. and Kötter, R. (2004). Motifs in brain networks. PLoS ological networks (Alon, 2007). Work by Kashtan and Alon Biol, 2(11):e369. (2005) demonstrates that modularity and motif distributions Sporns, O., Tononi, G., and Edelman, G. (2000). Theoretical Neu- are sometimes correlated, but not uniquely so. We speculate roanatomy: Relating Anatomical and Functional Connectiv- that motif distributions may be more discriminating and pre- ity in Graphs and Cortical Connection Matrices. Cerebral Cortex, 10:127–141. dictive of functional complexity than modularity or the other Strogatz, S. H. (2001). Exploring complex networks. Nature, metrics we have examined to date. We also expect that ex- 410:268–276. tending the standard 13 unsigned motifs to a corresponding Tononi, G., Edelman, G., and Sporns, O. (1998). Complexity and 204 signed motifs will provide much greater discrimination, coherency: integrating information in the brain. Trends in as well as greater relevance to neural networks. Cognitive Sciences, 2(12):474–484. Tononi, G., Sporns, O., and Edelman, G. (1994). A measure Acknowledgements for brain complexity: Relating functional segregation and integration in the nervous system. Proc. Nat. Acad. Sci., Thanks to Mikail Rubinov for discussions on graph theory 91:5033–5037. algorithms. Thanks to Santosh Manicka for coding efforts Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of on bct-cpp. Support provided by the National Academies / ‘small-world’ networks. Nature, 393(6684):440–442. Keck Futures Initiative grant number NAKFI CS22. Yaeger, L. S. (1994). Computational Genetics, Physiology, Meta- bolism, Neural Systems, Learning, Vision, and Behavior or References Polyworld: Life in a New Context. In Langton, C. G., editor, Alon, U. (2007). Network motifs: theory and experimental ap- Proceedings of the Artificial Life III Conference, pages 263– proaches. Nat Rev Genet, 8:450–461. 298. Addison-Wesley, Reading, MA. Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. Yaeger, L. S. (2009). How evolution guides complexity. HFSP, (2008). Fast unfolding of communities in large networks. J. 3(5):328–339. Stat. Mech., page P10008. Yaeger, L. S., Griffith, V., and Sporns, O. (2008). Passive and Cherniak, C. (1995). Neural component placement. Trends in Neu- Driven Trends in the Evolution of Complexity. In Bullock, S. rosciences, 18:522–527. e. a., editor, Proceedings of the Artificial Life XI Conference, pages 725–732. MIT Press, Cambridge, MA. Humphries, M. D., Gurney, K., and Prescott, T. J. (2006). The brainstem reticular formation is a small-world, not scale-free, Yaeger, L. S. and Sporns, O. (2006). Evolution of Neural Structure network. Proc. R. Soc. B, 273:503–511. and Complexity in a Computational Ecology. In Rocha, L. e. a., editor, Proceedings of the Artificial Life X Conference, Kashtan, N. and Alon, U. (2005). Spontaneous evolution of modu- pages 330–336. MIT Press (Bradford Books), Cambridge, larity and network motifs. Proc. Natl. Acad. Sci. U. S. A. MA. Lago-Fernández, L. F., Huerta, R., Corbacho, F., and Sigüenza, J. A. (2000). Fast Response and Temporal Coherent Oscil-