{'fraction_non_alphanumeric': 0.032694257980393104, 'fraction_numerical': 0.008934176848408752, 'mean_word_length': 4.800560224089636, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Evolve Networks Towards Better Performance: a Compromise between Mutation and Selection

The interaction between natural selection and random mutation is frequently debated in recent years. Does similar dilemma also exist in the evolution of real networks such as biological networks? In this paper, we try to discuss this issue by a simple model system, in which the topological structure of networks is repeatedly modified and selected in order to make them have better performance in dynamical processes. Interestingly, when the networks with optimal performance deviate from the steady state networks under pure mutations, we find the evolution behaves as a balance between mutation and selection. Furthermore, when the timescales of mutations and dynamical processes are comparable with each other, the steady state of evolution is mainly determined by mutation. On the opposite side, when the timescale of mutations is much longer than that of dynamical processes, selection dominates the evolution and the steady-state networks turn to have much improved performance and highly heterogeneous structures. Despite the simplicity of our model system, this finding could give useful indication to detect the underlying mechanisms that rein the evolution of real systems.

networks, the compositional elements could actively change their interaction subjects according to the dynamical states. But for many biological networks, structural mutation happened blindly and randomly, with a timescale much separated from that of dynamical processes [10,11]. Besides, the structural evolution of these systems was mainly driven by preferential selection, in which systems exhibiting better performance during the life circle could pass their structural information to future generations with higher probability [12].
Thus, an important issue emerged: how intensively could the pursuit of specific performance, such as reaching functional states rapidly and robustly [13], reshape the topological structures via preferential selection?
In this paper, we investigate this question by designing a simple model system, in which we evaluate a network by its efficiency of escaping from disordered states in Local-Majority-Rule (LMR) dynamical processes [14] and try to evolve networks of low efficiency towards networks of high efficiency via repeated mutations and selections [15,16]. Although LMR dynamics is too simple to represent most of the dynamical processes running on real systems, it could make the evolution only focus on optimizing the distribution pattern of edges among vertices, which greatly reduces the complexity of our problem. In the model system, we find the steady state of evolution depends strongly on the timescales of mutations and dynamical processes.
When their timescales are comparable to each other, mutation dominates the evolution and the steady-state networks have similar structure as the steady-state networks of pure mutations. On the opposite hand, when the timescale of mutations is much longer than that of dynamical processes, selection dominate the evolution and highly heterogeneous networks with heavily connected hub and much improved efficiency emerge from the evolution. In the extreme situation, networks with optimal efficiency, which also deviate significantly from the steady-state networks of pure mutations in topological structure. At the end of this paper, we also propose a simple model on the evolution of particles. Additionally, we illustrate that this conclusion is still valid even in infinite population limit by a simple mathematical model.
As an extension, this finding calls for a comprehensive understanding of the evolution of real systems, which is consistent with the suggestion that the effect of likelihood should be also incorporated [17].

II. RESULTS
In the evolution with low mutation rate (µ = 0.01), the networks evolve to have highly heterogeneous structures (Fig. 1.[a]), in which a vertex with degree comparable to network size N emerges to act as the communicating hub. Meanwhile, the degree distribution of the other vertices shifts to be power-law-like for small degrees, which is significantly different from the exponential degree distribution of the steady-state networks under pure mutation. Besides, these highly heterogeneous networks exhibit strong degree-degree correlations indicated by two parameters R ≈ −0.495 ± 0.025, which means the global hub prefers intensively to interact with vertices having low degrees, and r ≈ 0.067 ± 0.0083, which means the other vertices prefer to connect with vertices having similar degrees. We notice that such degree-degree correlations are consistent with the spin-spin correlations embedded in the strongly disordered spin configurations of highly heterogeneous networks. In other words, the dynamics-driven evolution is able to detect the correlation between different vertices' states and transfer it to topological clustering, which gives another potential explanation to the community-rich structures of many biological and social networks.
On the opposite side, in the dynamics-driven evolution with high mutation rate (µ = 1) selection fails to achieve further improvement in both efficiency and structure than mutationdriven evolution, and the networks remain similar to the steady-state networks under pure mutations ( Fig. 1.[b]). From extensive simulations, we find there exists a critical mutation rate µ c which classifies the dynamics-driven evolutions with different mutation rate into two distinct regimes (Fig. 2). In the regime µ > µ c , mutations dominate the evolution, and the steady-state networks have similar structure as the steady-state networks under pure mutation. While in the regime µ < µ c , the steady-state networks appear to have highly heterogeneous structures, and their improvement in both efficiency and structure grows monotonically as µ decreased. Importantly, the critical mutation rate µ c decreases rapidly with N, which indicates a growing difficulty for large networks to achieve apparent optimization via dynamics-driven evolution.
Interestingly, for the dynamics-driven evolutions with different sampling number Ω, which determines the accuracy of efficiency sampling, similar transition emerges again ( only in the regime Ω > Ω c , highly heterogeneous networks emerge and their improvement grows monotonically with Ω; besides, the critical sampling number Ω c increases rapidly with N. Thus, we conclude that the dynamics-driven evolution is determined by the balance of two counteracting effects: the promotive effect generated from preferential selection struggles to push the population towards networks with high efficiency, while the degradative effect brought together by random mutation and imprecise sampling of efficiency drives the population back to the steady-state networks under pure mutations. Consequently, the steady state of dynamics-driven evolution should be independent of the original networks, even when they are optimally designed (Fig. 4).
To give a mathematical illustration, we consider a population of M particles with two possible energy states ε 1 = 0 and ε 2 = 1. For a particle with energy ε i (i = 1 or 2), it will be assigned with an random evaluation following normal distribution here the standard deviation coefficient σ i satisfies 1 ≪ σ 2 i ≪ +∞ and Ω ∈ [1, +∞) is the control parameter. Besides, the offspring particle generated from a particle with energy ε i will appear on the opposite energy level with probability p i , otherwise it will have identical energy with its parent. For mutation-driven evolution, every particle is replaced by an offspring generated from it at each generation. Easily seen, the particle composition r g ,

100
1000 Ω which is defined to be the fraction of particles with energy ε 2 at generation g, will finally evolve to a steady state While in evaluation-driven evolution, every particle generates E offsprings (E is positive and finite) at the start of each generation, then only the M particles with the highest evaluation of all (E +1)M particles will survive and pass into next generation. Therefore, in the infinite population limit (M → ∞), the steady-state particle composition r e s will satisfy here φ s is the steady-state threshold that only particles with evaluation higher than it could survive. When Ω → +∞, which means the stochastic fluctuation in particle evaluation will decrease to vanish, we find that +∞ φs N (ε 1 , Oppositely, when Ω is sufficient small so that which implies particles with different energy will survive with approximately equal probability, the steady-state composition will have r e s ≈ p 1 p 1 +p 2 = r m s . On the other hand, in the extreme condition p 1 → 0 and p 2 → 1, which corresponds to the dynamics-driven evolution with high mutation rate, it could be derived from equation (2) and equation (3) that r e s → 0 and r m s → 0. In other words, the steady-state population of evaluation-driven evolutions has similar composition with that of mutation-driven evolution. However, in the extreme condition p 1 ≈ p 2 ≪ 1, which corresponds to the dynamics-driven evolution with small mutation rate, we find that r e s ≈ 1 and r m s ≈ 1 2 . Obviously, this compositional difference indicates an apparent optimization achieved by evaluation-driven evolution. Thus, if we take the dynamics-driven evolution as particles jumping among a series of structural heterogeneity levels, it could be easily derived from above analysis that the optimal structure could be approached only when the timescale of mutations is much longer than that of dynamical processes [18].
Finally we replace the local rewiring scheme by preferential rewiring, and show there also exists a critical strength β c (Fig. 5) to classify dynamics-driven evolutions with different strength of preferential rewiring into mutation-dominating regime (β < β c ) or selectiondominating regime (β > β c ). Interestingly, the critical strength β c is found to increase monotonically with N as well, which reemphasizes the growing difficulty to achieve apparent optimization in large networks and supports that our finding is independent of the way how mutation occurs.

III. DISCUSSION
It has been debated whether the evolution in biological world should be viewed as some hill-climbing process [20], or is mainly determined by the "neutral mutations" [21] like a random walk. But in our simple model system, we find when the optimal networks deviate from the steady state networks under mutations, a flexible combination of these two viewpoints is required. Interestingly, similar deviations are frequently detected in biological and social systems, such as the abundance of certain network motifs [22] or nucleotide types [23]. Therefore, dynamics-driven evolution could be a potential way to explain these structural heterogeneities. However, the evolution of real systems is far more complicated than our simple model system. Meanwhile, the evaluation of them is usually determined by a combination of multiple components such as efficiency, sensitivity, robustness and cost [24]. Therefore, more detailed models are still needed to give a comprehensive understanding to the evolution running in real world.

A. Local-Majority-Rule dynamics
For a undirected network of size N and average connectivity c, we attach to each vertex i a binary spin variable σ i = ±1. At each time step t of the LMR dynamics, all the vertices update their states synchronously according to here ∂i means the vertices which are connected with vertex i directly. As described in [18], we start a LMR dynamical process from a strongly disordered configuration σ(0) ≡ {σ 1 (0), σ 2 (0), . . . , σ N (0)}, which is randomly generated with the constraints k i σ i = 0 (k i is the degree of vertex i). Typically, the LMR dynamics will drive the network to stabilize at a consensus state, in which all the vertices have the same spin state. It has been shown in [14] that in LMR dynamical processes, scale-free networks with degree distribution P (k) ∼ k −γ and γ → 2 can reach consensus more rapidly than Poissonian networks of similar size and average connectivity. In other words, highly heterogeneous networks are more efficient in communicating internal states than homogenous networks.

B. Definition of efficiency
For a given network G, we start a total number of Ω different LMR dynamical processes, and run them for T = 1 time step to reach the corresponding configuration σ α (1). It has been shown in [14] that the characteristic relaxation time of a network in the LMR dynamics is determined by the the escaping velocity of the network's spin configuration from the strongly disordered region. In this paper, we define the efficiency G of network G as the average change of vertex-state in σ(1), which is calculated according to Easily seen, the efficiency sampled in this way is only a random estimation of the true efficiency E * (G) = lim Ω→∞ E(G). According to the Central Limit Theorem, the distribution of E(G) will be approximately Gaussian-distribution-like with the average value equal to E * (G), while the mean square variance will be proportional to 1/Ω (see the Supplementary   Information). That's to say, the efficiency of a network will be evaluated more precisely with large Ω.

C. Evolutionary algorithm
The dynamics-driven evolution starts from a population of P networks, which are uniformly sampled from the ensemble of random Poissonian networks of given size N and average connectivity k . At the beginning of each generation, every network generates E exact copies, which expands the population to a size (E + 1)P. Then every new network undergoes random mutations following local rewiring [25]: (1) For each vertex, mutation occurs with probability µ (mutation rate); (2) if mutation is accepted by vertex i, a rewiring of edge (i, j) → (i, l) is proposed, in which vertex j is randomly selected from the nearest neighbors of vertex i and vertex l is then randomly selected from the nearest neighbors of vertex j except vertex i; (3) this proposal will be rejected if and only if edge (i, l) already exists or the degree of vertex j is less than a minimal value k 0 after cutting edge (i, j).
Then the efficiency of each network is sampled independently, and the population shrink to its original size with only P networks with the highest efficiency survive and pass into next generation. As a reference to the dynamics-driven evolution, we also derive the steady-state networks under pure mutations by proposing a mutation-driven evolution. In the evolution, all the networks keep to be replaced by a new network generated from it following the same rules of mutation. For the local rewiring scheme, the degree distribution of the steady-state networks under pure mutations is shown to decay exponentially [25]. If not specified by the context, the parameters default to adopt value Ω = 1000, P = 25, N = 1000, k = 10 , E = 3 and k 0 = 5.
In this work we also involved preferential rewiring scheme [26]: the only change from above description is that vertex l (l = i and l = j) in the rewiring proposal is chosen randomly with a probability Π l ∝ (k l + 1) β , here k l is vertex l's degree and β is the control parameter which determines the strength of preferential rewiring. Obviously when β = 0, the preferential rewiring scheme will degrade to random rewiring, under which the steady-state networks has been proved to be Poissonian [26]. On the opposite side, the maximal value of β used in this paper is 1, under which the steady-state networks will have exponential degree distributions [26].

D. Identification of global hub and Definition of hub-spoke coefficient
For generality, we identify the vertex with the highest degree in a network as the global hub for both heterogeneous and homogenous networks. (If there are multiple vertices with the highest degree, we only identify the one with the smallest index as the only global hub.) We also define the hub-spoke coefficient C hs of a network to be C hs = k hub N −1 , in which k hub is the global hub's degree and N is network size. Obviously, when C hs equals to 1, the network will look completely hub-and-spoke like.

E. Quantification of degree-degree correlation in networks
To give an explicit quantification of the degree-degree correlations in a network, we define two quantities: correlation index R measures the degree-degree correlation on links connecting the global hub and the other vertices, while assortative-mixing index r measures the degreedegree correlations on links connecting the other vertices. We define R to be the normalized ratio of the mean degree of nearest neighbors of the global hub k hub nn to the averaged value k hub nn ran of this mean degree over an ensemble of randomly shuffled networks [22], and calculate it according to here k hub nn max and k hub nn min are the maximal and minimal value of k hub nn in the ensemble of randomly shuffled networks, respectively. Obviously, R ∈ [−1, 1]. When R < 0, the global hub prefers to interact with vertices with low degrees compared with its behavior in the randomly shuffled networks. Otherwise, when R > 0, vertices with high degrees are preferred. On the other hand, we define r to be the assortative-mixing index of the globe hub-removed subnetwork following [27] r = here M ′ is the number of edges in the subnetwork. When r > 0, these vertices prefer to be assortatively connected with vertices having similar degrees; Otherwise, when r < 0, the subnetwork is disassortatively connected.
To make rapid calculation of R, here we give a theoretical prediction of k hub nn ran by in which N k is the number of vertices with degree k, δ is the Kronecker symbol and P * (k) is the probability that a vertex with degree k is connected with the global hub in a randomly shuffled network. Now we approximate P * (k) by in which In numerical simulations, it's shown to be a good approximation for the networks appeared in this paper (see the Supplementary Information).

F. Generation of hub-spoke networks
A hub-spoke network of size N, average connectivity c and minimal degree k 0 is generated through: (1) first generate a random Poissonian network of size N − 1 and average connectivity (2) then evolve the Poissonian network under mutation-driven evolution with minimal degree k ′ 0 = k 0 − 1 until the steady state is reached; (3) then assortatively shuffle the mutated network following [28] with p = 1; (4) finally add a global hub to the shuffled network and connected it with all the other N − 1 vertices.
From numerical simulations, we find such hub-spoke networks have much higher efficiency than the Poisson networks of the same size and average connectivity (Fig. 4).

Zhen Shao and Hai-jun Zhou
Institute of Theoretical Physics, the Chinese Academy of Sciences, Beijing 100080, China

I. LOCAL-MAJORITY-RULE DYNAMICS
A strongly disordered configuration could be constructed as follows: one first divide the vertices into two groups (G + and G − ) of equal size randomly and assign spin +1 to vertices in group G + and assign spin −1 to vertices in group G − ; then as long as In such a way, a vertex (either chosen randomly or reached by following a randomly chosen edge) will be found to be in the spin +1 state with probability 1/2.
Easily seen, there exist clear spin-spin correlations in the strongly disordered configurations of highly heterogeneous networks. For a network, we define the probability distribution q(k) as the probability that a vertex with degree k is found to have the same spin state as the global hub in the strongly disordered configurations. Then we find for highly heterogenous networks, q(k) is clearly higher than 1/2 when k is small and is clearly lower than 1/2 when k is large (Fig. ??). That's to say, the degree-degree correlations in the highly heterogenous networks reached by dynamics driven evolution are consistent with the spin-spin correlations embedded in the strongly disordered configurations of these networks.
However, these spin-spin correlation aren't the main causation of the emergence of highly heterogenous networks in the dynamics-driven evolution. To prove it, we modify the model system by using simplified LMR dynamics. In the simplified LMR dynamical processes, the initial spin configurations are disordered configurations which only need to satisfy the constraint N i=1 σ i = 0. In this paper, a disordered configuration is constructed by dividing the vertices into two groups of equal size randomly and assigning opposite spin states to the vertices in different groups. From numerical simulations, we find the dynamics-driven