{'fraction_non_alphanumeric': 0.03396014594442885, 'fraction_numerical': 0.013144354008794087, 'mean_word_length': 4.280069152877253, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
General coevolution of topology and dynamics in networks

We present a general framework for the study of coevolution in dynamical systems. This phenomenon consists of the coexistence of two dynamical processes on networks of interacting elements: node state change and rewiring of links between nodes. The process of rewiring is described in terms of two basic actions: disconnection and reconnection between nodes, both based on a mechanism of comparison of their states. We assume that the process of rewiring and node state change occur with probabilities Pr and Pc respectively, independent of each other. The collective behavior of a coevolutionary system can be characterized on the space of parameters (Pr, Pc). As an application, for a voterlike node dynamics we find that reconnections between nodes with similar states lead to network fragmentation. The critical boundaries for the onset of fragmentation in networks with different properties are calculated on this space. We show that coevolution models correspond to curves on this space describing functional relations between Pr and Pc. The occurrence of a one-large-domain phase and a fragmented phase in the network is predicted for diverse models, and agreement is found with some earlier results. The collective behavior of system is also characterized on the space of parameters for the disconnection and reconnection actions. In a region of this space, we find a behavior where different node states can coexist for very long times on one large, connected network.

Many complex systems observed in nature can be described as dynamical networks of interacting elements or nodes where the connections and the states of the elements evolve simultaneously [1][2][3][4][5]. The links representing the interactions between nodes can change their strengths or appear and disappear as the system evolves on various timescales. In many cases, these modifications in the topology of the network occur as a feedback effect of the dynamics of the states of the nodes: the network changes in response to the evolution of those states which in turn determines the modification of the network. Systems that exhibit this coupling between the topology and states have been denominated as coevolutionary dynamical systems or adaptive networks [1,3,4].
In many systems where this type of coevolution dynamics is implemented, a transition is often observed from a phase where most nodes are in the same state forming a large connected network to a phase where the network is fragmented into small disconnected components, each composed by nodes in a common state [25]. This network fragmentation transition is related to the difference in time scales of the processes that govern the two dynamics: the state of the nodes and the network of interactions [21]. In these models, the time scales of the processes of interaction between nodes and modification of their links are coupled and controlled by a single parameter in the system.
The phenomenon of coevolution raises one of the fundamental questions in dynamical networks, namely whether p-1 the dynamics of the nodes controls the topology of the network, or this topology controls the dynamics of the nodes. In this paper we propose a general framework to approach this question. We consider that the process by which a node changes its neighbors, called rewiring, and that the process by which a node changes its state, have their own dynamics. Furthermore, we assume that these two processes can be independent of each other. As a consequence of this assumption, the collective behavior of a coevolutionary system can be studied on the space of the parameters representing the time scales for both processes. A particular coevolution dynamics can be described by formulating a specific coupling condition between the two competing processes in the network. We shall show that the collective behavior and the existence of a network fragmentation transition for given coevolution models can be predicted from the general phase diagram of the system on this space of parameters.
Let us focus on the mechanisms for the rewiring process of the coevolution phenomenon. For simplicity, we consider that the number of connections in the network is conserved. Then, we assume that any rewiring process consists of two basic actions: disconnection and reconnection between nodes. Both connecting and disconnecting interactions are often found in social relations, biological systems, and economic dynamics [4,5,18,23].
In general, either action, disconnection or reconnection, is driven by some mechanism of comparison of the states of the nodes. We define a parameter d ∈ [0, 1] that measures the tendency to disconnect between nodes in identical states; i.e., d represents the probability that two nodes in identical states become disconnected and 1 − d is the probability that two nodes in different states disconnect from each other. Similarly, we define another parameter r ∈ [0, 1] that describes the probability to connect between nodes in identical states; then, 1 − r is the probability that two nodes in different states connect to each other. A rewiring process can be characterized by the label dr, where d indicates the probability for the disconnection action between nodes sharing the same state, and r assigns the probability for reconnection between nodes possesing the same state. Thus, we can construct a plane (d, r) where any rewiring process subject to disconnectionreconnection actions between nodes can be represented as a point on this plane.
In a simplified approach, we first consider a discrete expression of the plane (d, r) as follows. We assume that either action of the rewiring, disconnection or reconnection, can be driven by three distinct mechanisms: similarity S (interaction between nodes sharing the same state), randomness R (interaction between nodes regardless of their states), and dissimilarity D (interaction between nodes having different states). Then both r and d can only take the values 0(D), 0.5(R), and 1(S). This gives rise to nine possible rewiring processes based on the combinations of these actions and their mechanisms, as shown in is disconnected from node j chosen at random and then reconnected to a node m that possesses a state equal to that of i. We can classify many rewiring process employed in the literature under this scheme. For example, an RS process corresponds to that used in Ref. [18], a DS process was used in Ref. [19], while the rewirings employed in Refs. [20][21][22] can be regarded as of type DR. Note that only the RR process is completely independent of the states of the nodes. Then a coevolutionary system can be analyzed as follows. We assume that the dynamics of the system can be described by the coexistence of a rewiring process dr that takes place with a probability P r , and a process of node state change that occurs with a probability P c . We assume these two probabilities are independent of each other. Therefore, the dynamics of the coevolutionary system is represented by four basic parameters, d, r, P r , P c . The collective behavior of the system can be characterized on the space of these parameters. Then, a specific coevolution model associated to a rewiring process dr consists of a prescribed functional relationship between the probabilities P r and P c that corresponds to a curve on the plane (P r , P c ).
As an application of this scheme, consider a random network of N nodes having average degree of edgesk, i.e., k is the average number of neighbors of a node. Let ν i be the set of neighbors of node i, possessing k i elements. Let us assume that the network topology is subject to a rewiring process dr. For the node state dynamics, we choose a simple imitation rule such as a voterlike model that has been used in various contexts [18,[26][27][28][29]. The state of node i is denoted by g i , where g i can take any of G possible options. The states g i are initially assigned at random with a uniform distribution.
The coevolution dynamics in this system is defined by iterating the following steps: 2. With probability P r , apply rewiring process dr: break the edge between i and a neighbor j ∈ ν i that satisfies mechanism d, and set a new connection between node i and a node l / ∈ ν i that satisfies mechanism r.
3. Choose randomly a node m ∈ ν i such that g i = g m . With probability P c , set g i = g m .
Step 2 describes the rewiring process that allows the acquisition of new connections, while step 3 specifies the process of node state change; in this case the states of the nodes becoming similar as a result of connections. We have verified that the collective behavior of this system is statistically invariant if steps 2 and 3 are interchanged.
The network size N , the average degreek, and the number of options G remain constant during the evolution of the system. Thus, given a rewiring process dr, the parameters of our model are the probability of rewiring, P r , and the probability of changing the state of a node, P c .
The chosen imitation dynamics of the nodes tends to increase the number of connected pairs of nodes with equal states, while some rewiring processes may favor the fragmentation of the network. Therefore, the time evolution of the system should eventually lead to the formation of a set of separate components, or subgraphs, disconnected from each other, with all members of a subgraph sharing the same state. We call domains such subgraphs.
To characterize the collective behavior of the system, we employ, as an order parameter, the normalized average size of the largest domain in the system, S m . Figure 2 shows S m as a function of the probability P r for the discrete rewiring processes in Fig. 1 on a network havingk = 4, with a fixed value of the probability P c .
We observe that most discrete rewiring processes in Fig. 1 lead to collective states characterized by values S m → 1 and corresponding to a large domain whose size is comparable to the system size. However, the rewiring processes DS and RS exhibit a transition at some critical value of P r , from a regime having a large domain, to a state consisting of only small domains for which S m → 0. Those rewirings dr with r = S can sustain a stable regime consisting of many small domains (SS leaves the initial network structure statistically invariant). The critical point P * r for the domain fragmentation transition in each case is estimated by the value of P r for which the largest fluctuation of the order parameter S m occurs. For the rewiring process RS on a network with k = 4, a finite size scaling analysis is shown in the inset in Fig. 2, where N α S m is plotted versus N (P r − P * r ), with P * r = 0.541 ± 0.007, and for various system sizes. We find that the data collapses in the critical region when α = 0.50 ± 0.05. A similar scaling analysis for the rewiring DS in Fig. 2 yields P * r = 0.380±0.007 and α = 0.20±0.05. Thus, there exists a universal scaling function F such that S m = N −α F (N (P r − P * r )) associated to each process RS and DS.
For a given rewiring process, the collective behavior of the coevolving system can be characterized in terms of the quantity S m on the space of parameters (P r , P c ). Figures 3(a) and 3(b) show the phase diagrams arising on the plane (P r , P c ) when the rewiring processes RS and DS, respectively, are employed on networks having different values ofk. In both cases, for each value ofk, two phases appear in the system as the parameters P c and P r are varied: one phase consists of the presence of only small domains and is characterized by S m → 0, and the other is distinguished by the formation of a large domain and is characterized by larger values of S m . These two regimes are separated by a critical curve (P * c , P * r ). Figure 3 expresses the general phase diagram of a coevolving system subject to a given node state dynamics and a given rewiring process. Diverse coevolution models can be represented in this diagram by formulating specific coupling relations between the rewiring and the node state dynamics. In general, such a coupling can be expressed as a functional relation P c (P r ) that describes a curve on the space of parameters in Fig. 3. For example, consider the relation P c = 1 − P r on the phase diagram in Fig. 3(a). This corresponds to the coevolution model proposed in Ref. [18] that uses a rewiring of type RS. In this case, the transition from a large domain regime to a fragmented phase on a network characterized by a value ofk should occur when this straight line intersects the corresponding critical boundary curve in Fig. 3(a). These intersections yield the values P * r = 0.171 fork = 2, P * r = 0.458 for k = 4, and P * r = 0.722 fork = 8, which agree with the critical values found in [18]. Similarly, a rewiring of type DS and the coupling function P c = 1 − P r describe the p-3 two-state voter model introduced in Ref. [19]. The intersection of the line P c = 1 − P r with the boundary curve corresponding tok = 4 on the phase diagram in Fig. 3(b) indicates the critical value P * r = 0.375. This value agrees with that calculated by a different procedure in Ref. [19]. Furthermore, for a network havingk = 8, the predicted critical value for this model is P * r = 0.653. The phase diagrams of Fig. 3 predict the critical values (P * r , P * c ) for the network fragmentation transition in more complicated coevolution models. For example, consider the nonlinear relation P c = aP r sin(πP r ) on the space of parameters of Fig. 3(a). For a = 1.72, this function crosses the critical boundary associated tok = 4 in Fig. 3(a) twice, at the values P * r = 0.25, corresponding to a re-combination of the network, and P * r = 0.77, signaling a fragmentation transition. In the range of parameters P r ∈ (0.25, 0.77), the function lies within the one-large domain region of the phase diagram. Thus, in a coevolution model described by this function on a network characterized byk = 4, a regime of one large domain should exist for this range of parameters. Fork = 2, only a fragmented phase occurs for this coevolution function. Figure 4 shows S m as a function of P r for the two coevolution models presented in Fig. 3 for a network with k = 4. For the model in Ref. [18], the fragmentation transition takes place at the value P * r predicted from Fig. 3. Similarly, for the nonlinear model we confirm the existence of a one-large domain phase confined in the region P r ∈ (0.25, 0.77).  Fig. 3(a), on a network withk = 4. Pc = 1 − Pr (squares); Pc = 1.72Pr sin(πPr) (circles). For each value of Pr, 100 realizations of initial conditions were performed.
We have also investigated the behavior of the system on the space of parameters (d, r) that describes general rewiring processes, while keeping others parameters fixed. As before, we start from a random network and a random uniform distribution of states g i . As an example, let us assume a dynamics such that P r = 1 (the rewiring process is always applied) and P c = 1 (nodes always copy the state of a neighbor). The above algorithm defining the coevolution dynamics can be employed as d and r are changed. Figure 5 shows the average normalized size of the largest network component S, regardless of the states of the nodes, as a function of r, with fixed d = 0.2. The quantity S reveals a network fragmentation transition at a value r = 0.938. We also calculate, for long times, the normalized average size of the largest subset of connected nodes in the largest network component that share the same state, denoted by S g . Figure 5 shows S − S g versus r. We observe that S − S g = 0 for r < 0.56, meaning that p-4 all the nodes on the largest component share the same state, on the average. Since S → 1 for r < 0.56, there is one large domain whose size is comparable to that of the system. For r > 0.938, we have S − S g → 0 and S → 0, corresponding to the occurrence of multiple small domains in the system. In the range 0.56 < r < 0.96, we observe S − S g > 0, indicating that not all the nodes on the largest network component share the same state. Since S → 1 in this range of r, the system there consists of a connected network whose size is comparable to the system size. Thus, in the range 0.56 < r < 0.938 we find a situation where subsets having distinct states coexist on a large connected network. In order to elucidate the nature of this behavior, we show in the inset in Fig. 5 a semilog plot of the average time τ for reaching one large domain (S = S g = 1) in the system versus the system size N , for different values of r. We find that τ scales exponentially with N as τ ∼ e αN . Thus, the one-large domain phase cannot take place in an infinite size system. For a finite size system, the one-large multi-state component should eventually decay to one-large domain. We obtain numerically the exponents α = 0.064 for r = 0.2, in the one-large domain region, and α = 0.167 for r = 0.8 in the onelarge multi-state component region of Fig. 5. This means that the average decay time for the one-large multi-state component is several orders of magnitude larger than the corresponding time for the one-large domain phase. For N = 200, our results imply convergence times of the order of τ ≈ 10 6 for r = 0.2 and τ ≈ 10 14 for r = 0.8. As N increases, the decay of the one-large multi-state component cannot be observed in practice. Thus, our results for continuous values of the parameters r and d of the rewiring process suggest a mechanism for the coexistence of subsets of nodes having different states on a large connected network.
For given values of P r and P c that describe a coevolution dynamics, the collective behavior of the system can be characterized on the space of parameters for the disconnection and reconnection actions, (d, r), by using the quantities calculated in Fig. (5). Figure 6 shows the phase diagram resulting on the plane (d, r) for the values P r = 1 and P c = 1. Three types of behaviors occur in the system as the parameters r and d are changed. Two of these behaviors correspond to the phases already found in Fig 3: a one large-domain phase and a fragmented phase consisting of small domains. These two phases are separated by a region in the plane (d, r) where a supertransient behavior emerges, characterized by the coexistence of several states on one large network component. Figure 6 reveals that the rewiring processes RS (d = 0.5, r = 1) and DS (d = 0, r = 1) yield a fragmented phase when P r = 1 and P c = 1, in agreement with the results found in Fig 3. In conclusion, we have presented a general framework for the study of the phenomenon of coevolution in dynamical networks. Coevolution consists of the coexistence of two processes, node state change and rewiring of links between nodes, that can occur with independent probabili- ties P r and P c , respectively. We have analyzed the process of rewiring in terms of the actions of disconnection and reconnection between nodes, both based on a mechanism of comparison of their states.
For a given rewiring process, the collective behavior of a coevolving system can be represented in the space of parameters (P r , P c ). For a voterlike node dynamics, we found that only reconnections between nodes with similar states can lead to network fragmentation. We have calculated the critical boundaries on this space for the fragmentation transition in networks having different values ofk. The size of the region for the fragmented phase in the space (P r , P c ) decreases with increasingk. This suggests that fragmentation is more likely to be observed in networks wherek ≪ N . We have shown that coevolution models correspond to curves P c (P r ) on the plane (P r , P c ). The occurrence of network fragmentation as well as recombination transitions for diverse models can be predicted in this framework.
We have also characterized the collective properties of the system on the space of actions for rewiring processes (d, r), for given values of P r and P c that define a coevolution dynamics. On a region of this space, we have unveiled a regime where subsets having different states can coexist for very long times in one large, connected network .
We have limited our study to the case when then number of connections in the coevolving network is conserved. This condition is expressed in step 2 of the algorithm, where the application of both actions of disconnection and reconnection occurs with probability equal to one. This condition can be generalized by considering different probabilities for each of these actions. Thus, our framework p-5 provides a scenario for studying coevolving dynamical networks with no conservation of the total number of links.
Other extensions to be investigated in the future include the characterization of the topological properties of the network on the continuous plane (d, r), the consequences of preferential attachment rules for the reconnection action, the consideration of variable connection strengths, and the influence of the node dynamics on the collective behavior of coevolving systems. * * * This work was supported by project C-1692-10-05-B from CDCHTA, Universidad de Los Andes, Venezuela. J.C.G-A was supported by project FISICOS FIS2007-60327 from M.E.C., Spain. He also thanks CNPq, Brazil.