Introduction

In the last few years, it has been increasingly realized that there are many situations which are not well described by well-mixed (mean-field) models, lattices and uniformly distributed spatial models. This is the case with the majority of the so called complex systems, that are better characterized by what is generally known as complex networks [1], [2]. In many of these networks, the distribution of the number of interactions, k, that an individual shares with the rest of the elements of the system, P(k), is found to follow a power-law, P(k)∼k^−γ, with 2<γ<3 in most cases. The ubiquity in Nature of these so-called scale-free (SF) networks has led scientists to propose many models aimed at reproducing the SF degree distribution [1], [2]. Most of the existing approaches are based on growth rules that depend on the instantaneous topological properties of the network and therefore neglect the connection of the structural evolution and the particular function of the network. This is the case with the celebrated “preferential attachment rule” [3], that posits that new nodes attach to the existing ones with probability proportional to their degree. However, accumulated evidence suggests, moreover, that form follows function [4] and that the formation of the network is also related to the dynamical states of its components through a feedback mechanism that shapes its structure.

On the other hand, a paradigmatic case study of the structure and dynamics of complex systems is that of social networks. In these systems, it is particularly relevant to understand how cooperative behavior emerges. The mathematical approach to model the (cooperative versus defective) interactions is usually tackled under the general framework of evolutionary game theory through diverse social dilemmas [5]. In the general case it is the individual benefit rather than the overall welfare what drives the system evolution. The emergence of cooperation in natural and social systems has been the subject of intense research recently [6]–[17]. These works are based either on the assumption of an underlying, given static network (or two static, separate networks for interaction and imitation [18]) or a coevolution and rewiring starting from a fully developed network that already includes all the participating elements. The results show that if the well-mixed population hypothesis is abandoned, so that individuals only interact with their neighbors, cooperation is often promoted on heterogeneous networks, specifically on SF networks. However, the main questions remain unanswered: Are cooperative behavior and structural properties of networks related or linked in any way? If so, how? Moreover, if SF networks are best suited to support cooperation, then, where did they come from? What are the mechanisms that shape the structure of the system?

To contribute to answering those questions, in this paper we analyze the growth and formation of complex networks by coupling the network formation rules to the dynamical states of the elements of the system. As we have already mentioned, many mechanisms have been proposed for constructing complex scale-free networks similar to those observed in natural, social and technological systems from purely topological arguments (for instance, using a preferential attachment rule or any other rule available in the literature [1], [2]). As those works do not include information on the specific function or origin of the network, it is very difficult to discuss the origin of the observed networks on the basis of those models, hence motivating the question we are going to address. The fact that the existing approaches consider separately the two directions of the feedback loop between the function and form of a complex system calls for a new mechanism where the network grows coupled to the dynamical features of its components. Our aim here is to introduce for the first time an attempt in this direction, by linking the growth of the network to the dynamics taking place among its nodes.

Thus, our model combines two ideas in a novel manner: preferential attachment and evolutionary game dynamics. Indeed, with the problem of the emergence of cooperation as a specific application in mind, we consider that the nodes of the network are individuals involved in a social dilemma and that newcomers are preferentially linked to nodes with high fitness, the latter being proportional to the payoffs obtained in the game. In this way, the fitness of an element is not imposed as an external constraint [19], [20], but rather it is the result of the dynamical evolution of the system. At the same time, the network is not exogenously imposed as a starting point but instead it grows from a small seed and acquires its structure during its formation process. Finally, we stress that this is not yet another preferential attachment model in so far as the quantity that favors linking of new nodes has no direct relation with the instantaneous topology of the network. In fact, as we will see, the main result of this interplay is the formation of homogeneous and heterogeneous networks that share a number of topological features with real world networks such as a high clustering and degree-degree correlations. Remarkably, the set of nodes sustaining the observed aggregate behavior is very different from that arising in a complex but otherwise static network. As a particular but most relevant conclusion, we find that the mechanism we propose not only explains why heterogeneous networks are tailored to sustain cooperation, but also provides an evolutionary mechanism for their origin.

Evolutionary Preferential Attachment model

Our model naturally incorporates an intrinsic feedback between dynamics and topology. The growth of the network starts at time t = 0 with a core of m₀ fully connected nodes. New elements are incorporated to the network and attached to m existing nodes with a probability that depends on the dynamics of each node. In particular, we consider that the dynamics is dictated by the Prisoner's Dilemma (PD) game. In this two-players game, every node initially adopts with the same probability [21] one of the two available strategies, cooperation C or defection D. At equally spaced time intervals (denoted by τ_D) each node i of the network plays with its k_i(t) neighbors and the obtained payoffs are considered to be the measure of its evolutionary fitness, f_i(t). There are three possible situations for each link in the network: (i) if two cooperators meet both receive R, when (ii) two defectors play both receive P, while (iii) if a cooperator and a defector compite the former receives S and the latter obtains T. The four payoffs are ordered as T = b>R = 1>P = S = 0. After playing, every node i compares its evolutionary fitness (payoff) with that corresponding to a randomly chosen neighbor j. If f_j(t)>f_i(t) node i adopts the strategy of player j with probability [22](1)

The growth of the network proceeds by adding a new node with m links to the preexisting ones at equally spaced time intervals (denoted by τ_T). The probability that any node i in the network receives one of the m new links is(2)where N(t) is the size of the network at time t. The parameter ε ∈ [0,1) thus controls the weight of the f_i(t)'s during the growth of the network. When ε>0, nodes with f_i(t)≠0 are preferentially chosen.

The growth of the network as defined above is thus linked to an evolutionary dynamics and controlled by the parameter ε and the two associated time scales (τ_T and τ_D). When ε≃0, referred to as the weak selection limit [14], the network growth is independent of the evolutionary dynamics as all nodes are basically equiprobable. Alternatively, in the strong selection limit, ε→1, the fittest players (highest payoffs) are much more likely to attract the newcomers. Therefore, Eq. (2) can be viewed as an “evolutionary preferential attachment” mechanism. We have carried out numerical simulations of the model exploring the (ε, b)-space. In what follows, we focus on the results obtained when τ_D/τ_T>1, namely, the network growth is faster than the evolutionary dynamics [23]. Taking τ_T = 1 as the reference time, networks are generated by adding nodes every time step, while they play at discrete times given by τ_D. As τ_D>τ_T, the linking procedure is done with the payoffs obtained the last time the nodes played [24]. All results for each value of b and ε reported have been averaged over at least 10³ realizations and the number of links of a newcomer is taken to be m = 2, whereas m₀ = 3. The reader can find a code used to generate the networks (Text S1) as well as information about how to use it (Text S2) in the Supporting Information material. Three of the generated networks are depicted in Fig. 1 for three different values of the temptation to defect. The heterogeneous character of these networks is evident from the figure.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 1. Examples of the networks generated using the evolutionary preferential attachment algorithm.

The networks shown correspond to values of b equal to 1 (a), 2 (b) and 3 (c) in the strong selection limit. Red nodes stand for cooperators and blue ones represent defectors.

https://doi.org/10.1371/journal.pone.0002449.g001

Results

The dependence of the degree distribution on ε is shown in Fig. 2 for b = 1.5. As can be seen, the weak selection limit produces homogeneous networks characterized by a tail that decays exponentially fast with k. Alternatively, when ε is large, scale-free networks arise. Although this might a priori be expected from the definition of the growth rules, this needs not be the case: Indeed, it must be taken into account that in a one-shot PD game defection is the best strategy regardless of the opponent strategy. However, if the network dynamics evolves into a state in which all players (or a large part of the network) are defectors, they will often play against themselves and their payoffs will be reduced. The system's dynamics will then end up in a state close to an all-D configuration rendering f_i(t) = 0 ∀i ∈ [1, N(t)] in Eq. (2). From this point on, new nodes will attach randomly to other existing nodes [see Eq. (2)] and therefore no hubs can come out. This turns out not to be the case, which indicates that for having some degree of heterogeneity, a nonzero level of cooperation is needed. Conversely, the heterogeneous character of the system provides a feedback mechanism for the survival of cooperators that would not outcompete defectors otherwise.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 2. Degree distributions obtained for several values of ε for b = 1.5.

A transition from homogeneous to SF networks is evident. The networks are made up of 10³ nodes with 〈k〉 = 4 and τ_D = 10τ_T.

https://doi.org/10.1371/journal.pone.0002449.g002

The degree of heterogeneity of the networks in the strong selection limit depends slightly on b. The results indicate that when ε→1, networks with the highest degree of heterogeneity, corresponding to the largest values of b, are not those with maximal cooperation levels. In Fig. 3, we have represented the average level of cooperation, 〈c〉, as a function of the two model parameters ε and b. The figure shows that as ε grows for a fixed value of b>1, the level of cooperation increases. In particular, in the strong selection limit 〈c〉 attains its maximum value. This is a somewhat counterintuitive result as in the limit ε→1, new nodes are preferentially linked to those with the highest payoffs, which for the PD game, should correspond to defectors. However, the population achieves the highest value of 〈c〉. On the other hand, higher levels of cooperation are achieved in heterogeneous rather than in homogeneous topologies, which is consistent with previous findings [6]–[8].

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 3. In the bottom panel, we have depicted the (color-coded) average level of cooperation, 〈c〉, as a function of the temptation to defect b and the selection pressure ε.

The networks are those of Fig. 2.

https://doi.org/10.1371/journal.pone.0002449.g003

The interplay between the local structure of the network and the hierarchical organization of cooperation is highly nontrivial. Contrary to what has been reported for static scale-free networks [6], [8], Fig. 4 shows that as the temptation to defect increases, the likelihood that cooperators occupy the hubs decreases. Indeed, during network growth, cooperators are localized neither at the hubs nor at the lowly connected nodes, but in intermediate degree classes. It is important to realize that this is a new effect that originates in the competition between network growth and the evolutionary dynamics. In particular, it highlights the differences between the microscopic organization in the steady state for the PD game in static networks with that found when the network is evolving. We will come back to this question in the Discussion section below.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 4. Probability that a node with connectivity k plays as a cooperator for different values of b in the strong selection limit (ε = 0.99) at the end of the growth of a network with N = 1000 nodes.

https://doi.org/10.1371/journal.pone.0002449.g004

To confirm the robustness of the networks generated by evolutionary preferential attachment, let us consider the realistic situation that after incorporating a (possibly large) number of participants, network growth stops when a given size N is reached, and that afterward only evolutionary dynamics takes place. In Fig. 5, we compare the average level of cooperation 〈c〉 when the network ceased to grow with the same quantity, but computed after allowing the evolutionary dynamics to evolve many more time steps 〈c〉_∞ (without attaching new nodes). The green area indicates the region of the parameter b where the level of cooperation increases with respect to that at the moment the network stops growing. On the contrary, the red zone shows that for b>2.5, cooperative behavior does not survive and the system dynamics evolves to an all-D state. The increment of 〈c〉 when going from the steady state reached during network growth to the stationary regime attained once the underlying structure is static, has its roots on the fixation of cooperation in high degree classes, thus recovering the picture described in [8]. On the other hand, when b>2.5, the few cooperators present in the growing network are not able to invade the hubs and finally, after a few more generations, cooperation is extinguished yielding 〈c〉_∞ = 0. This result highlights the phenomenological difference between playing simultaneously to the growth of the underlying network and playing on fixed, static networks.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 5. Degree of cooperation when the last node of the network is incorporated, 〈c〉, and the average fraction of cooperators observed when the system is time-evolved 〈c〉_∞ after the network growth ends.

Both magnitudes are shown as a function of b for τ_D = 10τ_T. See the text for further details.

https://doi.org/10.1371/journal.pone.0002449.g005

Another striking feature emerging from the interaction between network growth and the evolutionary dynamics is captured in Fig. 6, where the clustering coefficient, CC, has been represented as a function of the nodes degrees in the strong selection limit for several values of b. This coefficient measures the ratio of the number of triangles existing on the network over the total possible number of triangles, which relates to the possibility that a node connecting to a neighbor of another is also connected to this last one. Specifically, we will look at CC(k), i.e., the way this coefficient depends on the degree of the node. Interestingly enough, the dependence of CC(k) is consistent with a hierarchical organization expressed by the power law CC(k)∼k^−β, a statistical feature found to describe many real-world networks [2]. The behavior of CC(k) in Fig. 6 can be understood by recalling that in scale-free networks, cooperators are not extinguished even for large values of b if they organize into clusters of cooperators that provide the group with a stable source of benefits [8].

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 6. Dependence of the clustering coefficient CC(k)∼k^−β with the nodes' degrees for different values of b in the strong selection limit.

The straight line is a guide to the eye and corresponds to k⁻¹.

https://doi.org/10.1371/journal.pone.0002449.g006

Discussion

Having presented our main simulation results, we now discuss them in detail and provide an interpretation of our observations that allows an understanding of the model behavior. To begin with, let us consider the emergence of cooperation in the resulting network in the strong selection limit (ε→1). The organization of the cooperator nodes explains why cooperation survives and constitutes a unique positive feedback mechanism for the survival of cooperation. For simplicity, let us focus on how cycles of length 3 (i.e., those contributing to CC) arise and grow. When a new node j enters the network, it will preferentially attach to m (recall we are using m = 2) nodes with the highest payoff. Two situations are likely. On the one hand, it may link to a defector hub with a high payoff. As the newcomer receives less payoff than the hub, it will sooner or later imitate its strategy and therefore will get trapped playing as a defector with f_j = 0. Subsequently, node j will not attract any links during network growth. On the other hand, if the new node attaches to a cooperator cluster, the other source of high payoff, and forms a triad with the cluster elements, two outcomes are possible depending on its initial strategy. If the newly attached node plays as a defector, the triad may eventually be invaded by defectors and may end up in the long run in a state where the nodes have no capacity to receive new links. Conversely, if it plays as a cooperator, the group will be reinforced, both in its robustness against defector invasion and in its overall fitness to attract new links, i.e., playing as a cooperator while taking part in a successful (high fitness) cooperator cluster reinforces its future success, while playing as a defector undermines its future fitness and leads to dynamically (and topologically) frozen (f_i = 0) structures, so that defection cannot take long-term advantage from cooperator clusters. Therefore, cooperator clusters that emerge from cooperator triads to which new cooperators are attached can then continue to grow if more cooperators are attracted or even if defectors attach to the nodes whose connectivity verifies k>mb. Moreover, the stability of cooperator clusters and its global fitness grow with their size, specially for their members with higher degree, and naturally favors the formation of triads among its components. Note, additionally, that it follows from the above mechanism that a node of degree k is a vertex of (k−1) triangles and then , the sort of functional form for the clustering coefficient reported in Fig. 6.

Another interesting phenomenon arising from our model is the fact, previously unobserved, that cooperators occupy the nodes with intermediate degree and the hubs are defectors, in contrast with the simulations on static networks [8], [9]. To address this issue we have developed a simple analytical argument. Let be the number of cooperator neighbors of a given node i. Its fitness is , if node i is a defector, and , if it is a cooperator. The value of is expected to change due to both network growth (node accretion flow, at a pace of one new node each time unit τ_T) and imitation processes that take place at a pace τ_D. We will focus on the case in which τ_D is much larger than τ_T. The expected increase of fitness is(3)where Δ_flow means the variation of fitness in node i due to the newcomers flow, and Δ_evol stands for the change in fitness due to changes of neighbors' strategies. The above expression would lead to an expected increase in given by(4)

On the other hand, the expected increase of degree in the interval (t,t+τ_D) only has the contribution from newcomers flow and takes the form (recall that new nodes are generated with the same probability to be cooperators or defectors)(5)

If the fitness (hence connectivity) of node i is high enough as to attract a significant part of the newcomers flow, the first term in Eq. (3) dominates at short time scales, and then the hub degree k_i increases exponentially. Connectivity patterns are then dominated by the growth by preferential attachment, ensuring as in the Barabási-Albert [3] model that the network will have a SF degree distribution. Moreover, the rate of increase(6)is larger for a defector hub (by a factor b) because of its larger fitness, and then one should expect hubs to be mostly defectors, as confirmed by the results shown in Fig. 4. This small set of most connected defector nodes attracts most of the newcomers flow.

On the contrary, for nodes of intermediate degree, say of connectivity m≪k_i≪k_max, the term Δ_flowf_i in Eq. (3) can be neglected, i.e., the arrival of new nodes is a rare event, so that for a large time scale, k ˙_i = 0. Note that if k ˙_i(t) = 0 for all t in an interval t₀≤t≤t₀+T, the size of the neighborhood is constant during the whole interval T and thus the evolutionary dynamics of strategies through imitiation is the exclusive responsible for the strategic field configuration in the neighborhood of node i. During these stasis periods the probability distribution of strategies approaches that of a static network in the neighborhood of node i. It is clear that this scenario can be occasionally subject to sudden (avalanche-type of) perturbations following “punctuated equilibrium” patterns in the rare ocasions in which a new node arrive. Recalling that the probability for this node i of intermediate degree to be a cooperator is large in the static regime [8] we then arrive to the conclusion that for these nodes the density of cooperators must reach a maximum, in agreement with Fig. 4. Furthermore, our simulations show that these features of the shape of the curve are indeed preserved as time goes by, giving further support to the above argument based on time scale separation and confirming that our understanding of the mechamisms at work in the model is correct.

Conclusions

In summary, we have presented a model in which the rules governing the formation of the network are linked to the dynamics of its components. The model provides an evolutionary explanation for the origin of the two most common types of networks found in natural systems: When the selection pressure is weak, homogeneous networks arise, whereas strong selection pressure gives rise to scale-free networks. A remarkable fact is that the proposed evolution rule gives rise to complex networks that share many topological features with those measured in real systems, such as the power law dependence of the clustering coefficient with the degree of the nodes. Interestingly, our results make it clear that the microscopic dynamical organization of strategists in evolutionarily grown networks is very different from the case in which the population evolves on static networks. Furthermore, as we have seen, the generated networks are robust in the sense that after the growth process stops, the dynamical behavior keeps its character.

Thinking of the specific application we are discussing here, the emergence of cooperation, it is particularly remarkable the special role of individuals with an intermediate number of connections. As we have reasoned above, as time proceeds and the network grows, cooperation increases by invading those intermediate nodes, and on the other hand the range of intermediate degrees grows as well, leading to further increase of cooperation. On the contrary, hubs or well connected nodes, which on the static scenario are the supporters of cooperation, in the evolutionary process are defectors that thrive and accumulate new nodes by being so, only to fall eventually in the class of intermediate degree nodes and become cooperators. The analogy with the effect of a well-doing middle class in a western-like society is tempting but would of course be too far-fetched to push it beyond a general resemblance. Nevertheless, one particular situation in which models like this, based on the evolutionary preferential attachment mechanism, may prove very relevant is in the formation of social networks of entrepreneurs or professionals, such as those studied in Silicon Valley [25], [26]. The way these networks grow upon arrival of new individuals and subsequent cooperative interactions made them a natural scenario to apply these ideas in detail. Finally, another important conclusion is the resilience of the cooperative behavior arising in these networks, in so far as it does not decrease for a wide range of parameters upon stopping the growth process, and, in most cases it even exhibits a large increase of the cooperation level.

On more general theoretical grounds, figuring out why scale-free networks are so ubiquitous in Nature is one of the most challenging aspects of modern network theory. At variance with previous hypotheses, the evolutionary preferential attachment mechanism of Eq. (2) naturally incorporates a competition between structural and dynamical patterns and hence it suffices to explain why SF networks are optimized to show both structural and dynamical robustness. The former is given by the scale-free nature of the resulting topology, while the latter is based on the high levels of cooperation attained in the grown networks. Note that this optimization acts at a local level since individuals search their own benefit rather than following a global optimization scheme [27], to be compared with the fact that the resulting network has a very good cooperation level as a whole. Finally, we let for future research the question of whether Eq. (2) can be applied to other sort of dynamics by appropriately defining the dynamical variable f_i(t) and adjusting the growth rules. It is however reasonable to assume that the functional form in Eq. (2) may render general for generating optimized SF networks.

Supporting Information