Graph topology plays a determinant role in the evolution of cooperation

1. Introduction

Cooperation is an essential ingredient of evolution. Simple organisms have cooperated to produce more complex organisms throughout evolutionary history. Similarly, we know that animals cooperate in families to raise their offspring, and in groups to hunt, as well as to reduce the risk of predation. In spite of its relevance, understanding the evolution of cooperation remains one of the most fundamental challenges to date (for a recent overview, see Hammerstein 2003), tackled by scientists from fields as diverse as anthropology, biology, sociology, ecology, economics, psychology, political science, mathematics, physics, etc., who often adopt Evolutionary Game Theory (Maynard-Smith 1982; Gintis 2000) as a common mathematical framework and the prisoner's dilemma (PD) as a metaphor for studying cooperation between unrelated individuals (Axelrod & Hamilton 1981; Nowak & May 1992). In the simple, one-shot PD, individuals are either cooperators or defectors, acting accordingly whenever two of them interact. They both receive R upon mutual cooperation and P upon mutual defection. A defector exploiting a cooperator gets an amount T and the exploited cooperator receives S, such that T>R>P>S (Mesterton-Gibbons 2001). As a result, in a single round of the PD it is best to defect, regardless of the opponent's decision, which in turns makes cooperators unable to resist invasion by defectors whenever evolution under replicator dynamics (Gintis 2000) takes place in well-mixed populations. Such an extreme scenario is somewhat alleviated, however, whenever the PD is played in a spatially structured population (Nowak & May 1992), such that individuals are then constrained to play solely with their nearest neighbours. Recent experiments (Kerr et al. 2002) have nicely demonstrated the impact of topological constraints on the evolution dynamics of three different strains of the bacteria Escherichia coli.

2. Games on graphs

In the language of graph theory, both scenarios—well-mixed populations and spatially structured populations—correspond to regular graphs, in which individuals occupy the vertices and the network of contacts (NOCs) between them is defined by the edges linking the vertices. Spatial structure, in turn, is typically implemented on so-called two-dimensional lattices, such as a square lattice (Nowak & May 1992), also associated with a regular graph. Indeed, all these types of regular graphs exhibit the same single-peak shape for the degree distribution d(k), defined for a graph with N vertices as d(k)=N_k/N, where N_k gives the number of vertices with k edges (Albert & Barabási 2002; Dorogotsev & Mendes 2003).

Recently, it has been recognized that regular graphs constitute rather unrealistic representations of real world NOCs, in which local connections (spatial structure) coexist with long-range connections (or shortcuts). Indeed, these features have been recently identified as characteristic of a plethora of natural, social and technological NOCs (Barabási & Albert 1999; Amaral et al. 2000; Albert & Barabási 2002; Dorogotsev & Mendes 2003), which often exhibit a power-law dependence on their degree distributions. Indeed, much effort has been invested in obtaining the exponent γ characterizing a given d(k)∼k^−γ power-law distribution, which typically lies between 2 and 3. The scale-free (SF) networks of Barabási & Albert (1999) provide the best-known model leading to such distributions with γ=3. In this model, graphs are generated via the combined mechanisms of growth and preferential attachment, this latter mechanism being the well known ‘rich get richer’ effect in economics (Simon 1955), which is also known as the ‘Matthew effect’ in sociology (Merton 1968). Together, these two mechanisms lead to the appearance of few vertices of high connectivity (so-called hubs), which are both interconnected and also connected to many others of low connectivity. Indeed, starting with a small number (m₀) of vertices, at every time step (in units of discrete graph generation time) one adds a new vertex with m≤m₀ edges that link it to m different vertices (growth). To choose the m vertices one assumes that the probability p_i of linking to vertex i depends on its degree (preferential attachment). After t time steps this algorithm produces a graph with N=t+m₀ vertices and mt edges, with an average connectivity , in which the ‘older’ vertices in the graph generation process are those which tend not only to exhibit larger values of the connectivity, but also to become naturally interconnected, leading to the appearance of strong ‘age-correlations’ between vertices (Albert & Barabási 2002).

The heterogeneity of NOCs is known to have a strong impact in different fields, notably epidemiology, the case of AIDS constituting a paradigmatic example (May et al. 2001). In SF NOCs, the strong heterogeneity leads to a dramatic increase in the likelihood of epidemic outbreaks. Furthermore, the presence of correlations in the NOCs has been investigated recently, both in an epidemiological context (Keeling et al. 1997; Read & Keeling 2003), and also in what concerns the evolution of altruism in viscous populations, by means of the pair correlation method (van Baalen & Rand 1998).

3. Simulations

In the following, we study the impact of NOCs associated with graphs of SF type on the evolution of cooperation as encapsulated in the PD. To this end, we follow common practice and adopt the parameterization introduced by Nowak & May (1992) for the game parameters, such that 2>T=b>1, R=1 and P=S=0, where b, the only parameter of the game, represents the cheating advantage of defectors over cooperators. We have checked that the results do not change if we make S=−ϵ<0 (ϵ≪1) in order to strictly enforce a PD setting. The evolution of cooperators and defectors is carried out implementing the following transition probabilities, which constitute the finite population analogue of replicator dynamics (Gintis 2000; Hauert & Doebeli 2004), to which simulation results converge in the limit of well-mixed populations.

During each generation (which constitutes our unit of discrete evolutionary time), all pairs of directly connected individuals, x and y, engage in a single round of the game, their accumulated payoff being stored as P_x and P_y, respectively, representing the fitness of each individual at the end of one generation. This means that during one generation, there will be as many rounds of the game as edges in the NOCs. At the end of each generation, after all individuals have played once with all their partners, all strategies are updated synchronously. To update a strategy located in vertex x, a neighbour y is drawn at random among all k_x neighbours. The strategy associated with the neighbouring vertex y replaces that of vertex x with a probability given by , where k_> is the larger of k_x and k_y, ensuring that 0≤p≤1. The present results are very robust with respect to changes in the detailed form used for strategy update. No qualitative changes occur if we adopt an asynchronous updating of strategies (Hauert & Doebeli 2004) or if we replace the denominator k_>(T−S) in p by, for example, k_max(T−S), where k_max is the maximum degree of connectivity of the network. Simulations were carried out on graphs with N=10⁴ vertices, in which equilibrium frequencies of cooperators and defectors were obtained, for each value of b, by averaging over 1000 generations after a transient time of 10 000 generations (we confirmed that averaging over larger periods or using different transient times did not change the results). Furthermore, final data results from an average over 100 realizations of the same type of NOCs (10 runs for each of 10 different realizations of the same class of NOCs) specified by the appropriate parameters (N and z). All simulations start with an equal percentage of strategies (cooperators and defectors) randomly distributed among the elements of the population. Moreover, even when graphs are generated via growth and preferential attachment, the evolution of cooperation is studied in graphs generated beforehand, their topology remaining frozen throughout evolution.

4. Evolution of cooperation

Figure 1a shows the results of our simulations for the PD evolving on regular ring-graphs (we used periodic boundary conditions) for different values of the average connectivity z, which not only confirm results obtained previously (Nowak & May 1992) on two-dimensional lattices, but also show how z influences the evolution of cooperation on this type of graph. Deviations from the well-mixed population limits are more pronounced the smaller the value of z, whereas the well-mixed limit is nicely recovered for sufficiently large z. Figure 1b shows the corresponding results for SF NOCs, constructed according to the growth and preferential attachment rules for z≥4. The SF NOCs were generated for m=m₀≥2 and the same number N=10⁴ of vertices. In sharp contrast with figure 1a, we now obtain the result that cooperation dominates over the entire range of b. Contrary to what is observed for regular graphs, dominance of cooperation increases with increasing z, up to a critical value (Pacheco & Santos 2005) above which one quickly approaches the well-mixed population limit. We have confirmed that the results in figure 1 remain valid both for larger populations with up to N=10⁶, as well as for small communities down to N=128; below this, stochastic extinction of cooperators or defectors happens for particular realizations of a given NOCs, as such precluding a clear cut result for the evolution of cooperation. This feature is a size effect that clearly disappears for larger values of N.

• Download figure
• Open in new tab
• Download powerpoint

Figure 1

Frequency of cooperators on different NOCs. Results for the PD shown as a function of the cheating advantage b. Results for (a) regular NOCs and different values of the average connectivity z; (b) scale-free NOCs and different values of z. In all cases, N=10⁴. Cooperation hardly dominates on regular networks, but clearly dominates for all values of b on scale-free NOCs generated including growth and preferential attachment.

In the following, we discuss the mechanisms that contribute to the startling results shown in figure 1b.

From figure 1, it is clear that the topology of the NOCs strongly affects the evolution of cooperation. The features of the Barabási and Albert model (Barabási et al. 1999) allow us to assess separately the relative roles played by growth and preferential attachment in promoting cooperation to the unprecedented levels obtained. Indeed, both growth and preferential attachment contribute to establish the power-law degree distribution associated with SF NOCs. If we modify the rules of construction of the SF NOCs by replacing the preferential attachment rule by a uniform attachment rule, we change the pattern of connections in the population, replacing a power-law degree distribution by an exponential degree distribution, reflecting the fact that the formation of large hubs is now inhibited under uniform attachment, although correlations are still present, albeit to a lesser extent. Furthermore, any type of correlations between vertices can be completely eliminated if we generate SF NOCs according to the configuration model (Molloy & Reed 1995), since this model ensures a maximally random graph compatible with a pre-defined degree distribution, for which we naturally choose those obtained as a result of the Barabási and Albert construction.

Figure 2 shows the impact of these new NOCs on the evolution of cooperation, for N=10⁴ and z=4. In all cases, cooperation is enhanced with respect to what one obtains on regular NOCs. Nonetheless, only the NOCs including both growth and preferential attachment are able to sustain cooperation for 1<b<2. Furthermore, comparison between the results obtained using the Barabási and Albert and the Configuration Models clearly shows that the correlations built up between individuals due to growth and preferential attachment are responsible for the dominance of cooperation for large values of b.

• Download figure
• Open in new tab
• Download powerpoint

Figure 2

Impact of growth, preferential attachment and vertex correlations on the evolution of cooperation. Comparison of results obtained using as NOCs graphs generated according to the model of Barabási and Albert (circles), the growth and uniform attachment model (triangles) and the configuration model (squares) shows that cooperation dominates for 1<b<2 only when both growth and preferential attachment are used simultaneously. In all cases, the size is N=10⁴ and the average connectivity is z=4.

Furthermore, the heterogeneity intrinsic to SF NOCs also contributes to the enhancement of cooperation obtained in figure 1b. Indeed, the fact that in heterogeneous NOCs, individuals interact different numbers of times per generation means that cooperators may increase their relative fitness by maximizing the number of cooperator neighbours. Defectors, however, may also increase their fitness by exploiting more cooperators. The results in figure 1b show that cooperators are those who profit from the heterogeneity of the NOCs, as explained in the following.

From an individual perspective, a defector is best surrounded by cooperators (the opposite strategy), since these are the interactions which will maximize his relative fitness. As such, defectors occupying hubs exploit and may easily invade most of their cooperator neighbours. However, in doing so, the number of neighbour cooperators will decrease in subsequent generations, which in turn acts to reduce the relative fitness of such defector hubs. Whenever their fitness becomes comparable to that of a cooperator neighbour, invasion may occur. Once cooperators invade a hub, the situation changes profoundly. Indeed, and contrary to defectors, cooperators benefit most by interacting with cooperators (the same strategy). Therefore, a cooperator occupying a hub will tend to increase the fraction of cooperator neighbours, in turn maximizing his own fitness. In other words, once invading a hub, a cooperator becomes so successful that it is very difficult for defectors to ‘strike back’, as evidenced by the results shown in figures 1 and 2. The picture emerging from this discussion is one in which evolution favours cooperators to become the most connected individuals, in this way succeeding in outperforming defectors. Such a picture is entirely corroborated by the results shown in figure 3, in which we plot the fraction of defectors which populate vertices of the NOCs sorted by degree and grouped into four major degree intervals. Initially, the relative fraction of defectors for each interval is approximately 50% (cross-hatched bars). Whenever the stationary regime is reached, defectors initially occupying the highly connected sites are wiped out by cooperators, managing to survive in vertices of moderate connectivity.

• Download figure
• Open in new tab
• Download powerpoint

Figure 3

Evolution of defectors by degree. The figure provides a typical scenario for the change in the distribution of defectors by degree, occurring as a result of evolution under natural selection. The cross-hatched bars show the fraction of vertices initially occupied by defectors (≈50%), for each degree-range specified by the intervals shown. Evolution leads to a stationary regime, with a distribution of defectors given by the solid bars. Clearly, defectors are efficiently wiped out from those vertices with largest connectivity, managing to survive as moderately connected individuals (results obtained for N=10³, z=4 and b=1.7).

In keeping with this discussion, it is also clear how preferential attachment ensures cooperation dominance for large b. On such NOCs, hubs become directly interconnected, a feature which helps to sustain cooperation. Conversely, cooperation dominance is suppressed whenever the edges which directly interconnect hubs are artificially removed.

5. Minimal model

How realistic are the SF NOCs studied so far? Empirical evidence gathered to date (Dorogotsev & Mendes 2003) indicates that, in social and biological NOCs, (i) vertices of highest connectivity exhibit degrees substantially lower than those produced with the simple Barabási and Albert model and (ii) display values for the cluster coefficient which are larger than those obtainable with that model (the cluster coefficient provides a measure of the extent to which direct neighbours of a given vertex are direct neighbours of each other, being roughly proportional to the number of such triangular connections). Furthermore, one may argue that the single-round PD best suits interactions between simple organisms (Kerr et al. 2002) unable either to retain memory of past encounters or to anticipate future encounters. For such organisms, growth can be easily envisaged as an active mechanism during the generation of NOCs, whereas preferential attachment seems too sophisticated as a rule, since the model of Barabási and Albert implicitly requires the cognitive capacity to process a significant amount of information (Mossa et al. 2002), being as such unlikely for simple organisms and/or large communities. On the contrary, these organisms most probably adopt local rules of attachment, in reaction to local properties of the NOCs, and independent of its global topology.

In this context, the minimal model of SF NOCs recently developed (Dorogotsev et al. 2001) provides a nice means of overcoming these difficulties. Not only does the minimal model lead to NOCs exhibiting the same power-law degree distribution d(k)∼k⁻³, but these new NOCs also exhibit large values for the cluster coefficient. In the minimal model, during growth each new vertex attaches to both ends of a randomly chosen edge. As such, this rule favours the creation of triangular relations between individuals, thereby greatly enhancing the cluster coefficient of the NOCs. In what concerns the present study, it is worth investigating the evolution of cooperation on graphs generated according to this model. The results are shown in figure 4 with solid squares, for N=10⁴ and z=4 (note that, by definition, these graphs share the same number of edges as the corresponding Barabási and Albert graphs), in which overall cooperation can be seen to become further enhanced with respect to the results of the Barabási and Albert model. It is noteworthy that the cluster coefficient in Barabási and Albert NOCs is of the order of 10⁻³, whereas for the minimal model one has values around 0.7 (with a maximum of 1 for a complete graph, in which a single defector wipes out all cooperators). In other words, the present results reinforce the evidence that growth and preferential attachment, even if implemented in a different fashion, lead to a clear dominance of cooperation, independently of the presence (or not) of a significant amount of such triangular relations.

• Download figure
• Open in new tab
• Download powerpoint

Figure 4

Results for the evolution of cooperation in NOCs exhibiting SF and truncated SF degree distributions according to the models described in main text. In all cases, the size is N=10⁴ and the average connectivity is z=4. The results for the Barabási and Albert model (solid circles) are compared with those obtained with the minimal model of Dorogotsev et al. (2001; solid squares) and the truncated Barabási and Albert model, imposing cut-offs of 20 (open triangles), 40 (dashed line) and 60 (open squares) for the maximum connectivity. In all cases, vertex correlations built up during the generation of the graphs due to growth and preferential attachment ensure that cooperation dominates for 1<b<2. As one continues to reduce the cut-off for maximum vertex connectivity, a sudden collapse of cooperation takes place, the behaviour resembling closely that obtained for the evolution of cooperation on regular networks.

6. Evolution under extrinsic constraints

Up to now, we have tacitly assumed that individuals have no limitations in what concerns the number of interactions they engage in per generation. This assumption will generally depend on what type of individuals are at stake and the kind of cooperation one is modelling, but it is reasonable to conceive communities in which extrinsic factors limit the interacting capacity of individuals. What is the impact of this effect on the evolution of cooperation?

Let us imagine that individuals engaging in a PD round with a neighbour expend a certain energy. Finite resources may impose, therefore, an upper limit to the number of connections that individuals in a population may sustain, which in turn imposes constraints on the topology of the NOCs. A simple means of modelling this feature is by introducing a cut-off in the degree distribution such that whenever the connectivity of an individual reaches the cut-off limit, no further connections to this individual may be established from that moment on during graph generation.

The Barabási and Albert model leads to typical values for the maximum connectivity well above 200, for N=10⁴ and z=4. In figure 4, we show the result of introducing such cut-offs in the Barabási and Albert model, for different values of the cut-off parameter (a more socially motivated mechanism leading also to the truncation of the degree distribution has been proposed by Mossa et al. (2002)). It is noteworthy that, in spite of limiting the maximum connectivity of the vertices, growth and preferential attachment still remain active and determinant mechanisms in the generation of the NOCs. Clearly, figure 4 shows that cooperation dominates even when the connectivity of each node is severely truncated down to values of the order of 20. These are impressive results which evidence the robustness of these mechanisms in sustaining cooperation.

As one imposes cut-offs below 20 (for N=10⁴ and z=4), cooperation collapses to a behaviour which first approaches that obtained with the growth-only model, shown in figure 2. This is a clear signal that below a certain critical cut-off value, preferential attachment is no longer effective during graph generation. Subsequent reduction of the cut-off limit leads to further hindrance of cooperation. However, since the resulting degree distributions remain heterogeneous, cooperation is still enhanced when compared to the behaviour obtained on, for example regular graphs. This is not surprising, and reflects the fact that heterogeneity promotes cooperation.

7. Conclusions

The present results show how different topologies of NOCs determine different dynamics for the evolution of cooperation. Graphs generated via growth and (different flavours of) preferential attachment provide sufficient conditions for cooperation to dominate, even in small communities with finite communication resources, and may help us understand why cooperation is so widespread and evolutionary competitive. It is likely that, throughout evolution, the topology of the NOCs itself has evolved. Moreover, NOCs relevant for anthropological studies of cooperation may be different from those most relevant to economics, political science or behavioural ecology. The combination of evolutionary game theory and graph theory provides the flexibility for carrying out more realistic simulations, retaining the unifying nature of this mathematical framework in such a wide and interdisciplinary endeavour.