# Snowdrift Game on Topologically Alterable Complex Networks

Authors: Zhe Wang; Hong Yao; Jun Du; Xingzhao Peng; Chao Ding
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In order to study the influence of network’s structure on cooperation level of repeated snowdrift game, in
the frame of two kinds of topologically alterable network models, the relation between the cooperation density
and the topological parameters was researched. The results show that the network’s cooperation density is
correlated reciprocally with power-law exponent and positively with average clustering coefficient; in other
words, the more homogenous and less clustered a network, the lower the network’s cooperation level;
and the relation between average degree and cooperation density is nonmonotonic; when the average degree
deviates from the optimal value, the cooperation density drops.


---

## Body

## 1. Introduction

Recently,complex network has become an effective researching approach on complex systems as well as complex interactions happening over them. Complex network is a sort of abstraction of complex systems; many real world systems such as communication network, transportation network, electricity grid, and logistic network can be modeled as complex networks. One of the pioneering works on complex network was conducted by Barabási and Albert [1]; their works revealed the sudden emergence of scaling on random networks. Since then, the emergence of characteristics on complex networks has become a hot spot. The research of evolutionary game theory (EGT) first appeared in the literature [2] where Nowak observed the emergence of cooperation in game theory when combined with spatial structure, but his work was done on a regular network. His findings provided a possible explanation to why species choose to cooperate with other species when they can gain more advantages through defecting them. The observation was a breakthrough in the traditional Nash equilibrium, and it could partially explain the commonly existing cooperation in natural and social networks. In the literature [3], the snowdrift game with best-takeover strategy was researched in small world networks, and the results showed that the evolution of the game was greatly influenced by the topology of networks. Assenza et al. [4] studied the promotion of cooperation by a highly clustering network structure; they found that the hierarchical invasion of defectors which was previously observed in BA networks does not exist in highly clustered networks. Szolnoki et al. [5] introduced facilitators into the game where a facilitator adopts a “tit-for-tat” strategy while interacting with its neighbors. They observed an enhancement in the cooperation level due to a sufficient number of existing facilitators as well as an obstruction of information spreading. The literature [6] studied the influence of noise on the evolution processes where the interacting networks were three kinds of networks of various topological structures. The memory effect was studied in snowdrift game on regular lattice [7]. All the works above were in the framework of homogeneous networks. However, the recent studies manifest the scale-free characteristic in most real world networks. In that, we propose a snowdrift game on two kinds of scale-free networks, power-law alterable network and clustering coefficient alterable network, so as to investigate the influence of main topological parameters on the emergence of cooperation.


## 2. Network Model

### 2.1. Power-Law Alterable SF Model

During a long period of time, all complex networks were regarded as random graphs. However, the American scientists Barabási and Albert overturned this presumption by their research on aWWW project [1]. They found that the degree distribution of most real world networks comply with power-law characteristic. They produced a network model known as BA scale-free network with a fixed power-law coefficient which is 3. BA model has been very successful in describing some real networks; yet a lot of realistic networks do not share the fixed power-law coefficient, such that a novel network production mechanism was proposed to provide scale-free model with a controllable power-law coefficient [8, 9].Firstly, we distribute alterable normalized weights to isolated nodes; then we link the nodes with corresponding probability. We can control the power-law coefficient by tuning the weights and the total number of edges. The specific algorithm is as follows.(i) Step 1. Distribute weight qi=i-β to node i, i=1,…,N, where 0≤β<1 is a tunable parameter. We normalize the weights:(1)qi∗=qi∑kqk.(ii) Step 2. Link every two nodes with an edge when random numbers r1 and r2 satisfy(2)qi∗>r1>qi+1∗,qj∗>r2>qj+1∗.If node i and node j are not connected yet, link these two nodes.(iii) Step 3. Repeat Step 2 until there are mN edges.The average degree is2m, and the degree distribution satisfies P(k)∝k-γ, and γ satisfies(3)γ=1+1β.Clearly, parameterm, together with β, can tune the network topology.


### 2.2. Clustering Coefficient Alterable SF Model

Barabási and Albert proposed the BA scale-free model; the degree distribution complies with power-law distribution; however, the network’s average clustering coefficient is relatively low which does not agree with realistic conditions. The clustering coefficient is the average connecting probability of two nodes which belong to the neighborhood of a common node, and it describes the network’s local structural property. We adopt the clustering coefficient alterable model in the literature [10] where a triangle connection mechanism is introduced into the BA algorithm. This mechanism raises the average clustering coefficient of the network. By tuning the triangle connection probability, we get a tunable average clustering coefficient. The algorithm is as follows: there are n0 original nodes; after every time step, add a new node i to the network and link node i to n nodes in the current network; the new node i is linked to the original node j with a probability of(4)Πj=kj∑sks,where kj is the degree of node j and ∑sks is the total degree of all nodes. After preferential connection to node j, node i adopts triangle connection with probability pt (that is, to choose a random neighbor of node j) or node i adopts preferential connection with probability 1-pt, until node i is connected to n nodes.


## 2.1. Power-Law Alterable SF Model

During a long period of time, all complex networks were regarded as random graphs. However, the American scientists Barabási and Albert overturned this presumption by their research on aWWW project [1]. They found that the degree distribution of most real world networks comply with power-law characteristic. They produced a network model known as BA scale-free network with a fixed power-law coefficient which is 3. BA model has been very successful in describing some real networks; yet a lot of realistic networks do not share the fixed power-law coefficient, such that a novel network production mechanism was proposed to provide scale-free model with a controllable power-law coefficient [8, 9].Firstly, we distribute alterable normalized weights to isolated nodes; then we link the nodes with corresponding probability. We can control the power-law coefficient by tuning the weights and the total number of edges. The specific algorithm is as follows.(i) Step 1. Distribute weight qi=i-β to node i, i=1,…,N, where 0≤β<1 is a tunable parameter. We normalize the weights:(1)qi∗=qi∑kqk.(ii) Step 2. Link every two nodes with an edge when random numbers r1 and r2 satisfy(2)qi∗>r1>qi+1∗,qj∗>r2>qj+1∗.If node i and node j are not connected yet, link these two nodes.(iii) Step 3. Repeat Step 2 until there are mN edges.The average degree is2m, and the degree distribution satisfies P(k)∝k-γ, and γ satisfies(3)γ=1+1β.Clearly, parameterm, together with β, can tune the network topology.


## 2.2. Clustering Coefficient Alterable SF Model

Barabási and Albert proposed the BA scale-free model; the degree distribution complies with power-law distribution; however, the network’s average clustering coefficient is relatively low which does not agree with realistic conditions. The clustering coefficient is the average connecting probability of two nodes which belong to the neighborhood of a common node, and it describes the network’s local structural property. We adopt the clustering coefficient alterable model in the literature [10] where a triangle connection mechanism is introduced into the BA algorithm. This mechanism raises the average clustering coefficient of the network. By tuning the triangle connection probability, we get a tunable average clustering coefficient. The algorithm is as follows: there are n0 original nodes; after every time step, add a new node i to the network and link node i to n nodes in the current network; the new node i is linked to the original node j with a probability of(4)Πj=kj∑sks,where kj is the degree of node j and ∑sks is the total degree of all nodes. After preferential connection to node j, node i adopts triangle connection with probability pt (that is, to choose a random neighbor of node j) or node i adopts preferential connection with probability 1-pt, until node i is connected to n nodes.


## 3. Game Model

The game theory is about the rational behavior in interdependent relations [11]. Simply speaking, individuals in the game have their strategy sets, and each individual chooses its own strategy so as to maximize its interest. Pure strategies and mixed strategies are all available.There are some classical models, such as the prisoner’s dilemma game, the hawk-dove game, the snowdrift game, and the public goods game [12–14].In a pairwise game, each player can choose either to cooperate or to defect; he gets different payoffs according to the strategies that he and his rival adopt. The payoff matrix is shown in Table1. In the matrix, a cooperator gets reward R when faced with another cooperator; otherwise, a cooperator gets the sucker’s payoff S when faced with a defector; a defector gets the temptation T when he is facing a cooperator, but he gets the punishment P if his rival is also defecting. We use a snowdrift game, where T>1, R=1, S=0, and P=-0.5.Table 1
Payoff matrix.
Cooperation
Defection
Cooperation
(R,R)
(S,T)
Defection
(T,R)
(P,P)In every round of game, each individual interacts with all their neighbors and then obtains payoff according to the payoff matrix. After each round, individuali chooses a random neighbor j, and it switches its strategy to j’s with the probability [15, 16] of(5)wi←j=Uj-Uik>T-S,where wi←j is the probability that individual i copies the strategy of individual j’s. Ui (or Uj) is the payoff of individual i (or j) in this round. k> is the bigger degree between i and j. It is clear that individual i only imitates individual j’s strategy when Ui<Uj.Cooperation densityρc (also known as cooperation frequency) measures the cooperation extent in game theory dynamics.


## 4. Simulations and Analysis

When pursuing the analytical solutions, theoretical tools such as the mean field theory have been very successful on regular networks. However, they fail when dealing with complicated network structures while numerical simulations are still effective. In this section, we simulate the repeated snowdrift game on power-law alterable and clustering coefficient alterable networks and analyze the influence of power-law coefficient, average degree, and clustering coefficient on the emergence of cooperation.


### 4.1. Influence of Power-Law Coefficient

In this section, we simulate and analyze the influence of power-law coefficient on the emergence of cooperation in a power-law coefficient alterable model where the total nodes number isN=500 and average degree is 2m=30. Every data in Figures 1–6 is an average value of 50 network model simulations. Initially, 50% of cooperators and 50% of defectors are randomly distributed on the network. On each network, we conduct 10000 time steps (rounds), of which the former 8000 time steps are to guarantee that the system enters a steady state, and the latter 2000 time steps are to generate the average cooperation density ρc. The game model we adopt and the strategy update could be seen in Section 3.Figure 1
ρ
c
-
γ curve (T=1.5).Figure 2
ρ
c
-
T curve with alterable γ.Figure 3
ρ
c
-
k curve with alterable T.Figure 4
ρ
c
-
T curve with alterable 〈k〉.Figure 5
ρ
c
-
γ curve (T=1.5).Figure 6
ρ
c
-
T curve with alterable pt.Figure1 illustrates the relation between the cooperation density ρc and the power-law coefficient γ when the temptation is T=1.5. We can see that ρc decreases as γ increases, and it falls gradually onto a platform after γ>5. The reason, we reckon, is that the degree distribution of the network changes from power-law to Poisson distribution as γ increases; that is to say, the network evolves from heterogeneity to homogeneity; in other words, the degree distribution tends to be more uniform. As a result of that, the influence of nodes with big degrees on the nodes with small degrees weakens, and the small degree nodes tend to defection for their own interest.Figure2 shows the relation between the cooperation density ρc and the temptation parameter T when γ=3, γ=6, and γ=9. As shown in the figure, T has negative relation with ρc; in other words, the payoff matrix’s support of defection is correlated reciprocally with the cooperation density. And there exists a threshold Ta for every specific γ; when T>Ta, the cooperators disappear on the network, ρc=0.By observing the three curves in Figure2, we can see that the more heterogeneous the network is (with smaller γ), the higher the cooperation density is when T<2.5. This phenomenon indicates that the nodes with big degrees have strong influence on those with small degrees, and the small degree nodes tend to cooperate with those with big degrees. Nevertheless, when T>2.5, the three curves reverse their positions, and the cooperation density is low (ρc<0.2). The reason is that all individuals tend to each other due to the high temptation coefficient. The nodes with small degree are less dependent on those with big degree, which weakens the control of the network.


### 4.2. Influence of Average Degree

The average degree portrays the denseness of the network from a microscopic perspective; in other words, the network gets denser as we increase the average degree. In this section, we study the effect of different average degrees on the cooperation density. Every data is averaged over 100 model simulations. In every model, we conducted 10000 time steps of which the former 8000 time steps were to guarantee that the system has entered a steady state, and the latter 2000 time steps were to generate the average cooperation densityρc.Figure3 illustrates the cooperation density ρc with respect to average degree 〈k〉 for variations of temptation T. As seen in the figure, the relation between ρc and 〈k〉 is nonmonotonous: there exists one optimal average degree 〈k〉m which corresponds to the highest cooperation level when temptation is relatively low (T=1.5, T=2, and T=2.5). When 〈k〉=〈k〉m, the cooperation density reaches the top level, and cooperators are almost all over the network. When 〈k〉<〈k〉m, the cooperation density deceases rapidly, as the steep slope on the left side in Figure 3. When 〈k〉>〈k〉m, the cooperation density also decreases, but with a lower speed, and tends to a constant number 0.5, as the slope in the right of Figure 3. This indicates that we cannot expect more cooperators on a denser network for granted. As a result, we should set the average degree rationally when constructing a real network so as to ensure relatively high cooperation density with a limited cost.The relation between the cooperation densityρc and the temptation coefficient T with a variable 〈k〉 is shown in Figure 4. We can see that the curve corresponding to 〈k〉m is above all other curves only when T is small (T<1.67). This phenomenon depicts that the optimal average degree has an effective range.


### 4.3. Influence of Average Clustering Coefficient

The average clustering coefficient describes the clustering characteristic of a complex network. Most realistic networks are clustered; for instance, one’s friends know each other in social network.BA scale-free networks have relatively low average clustering coefficient which disagree with realistic conditions. In that, we studied the influence of average clustering coefficient on the emergence of cooperation on a clustering coefficient alterable scale-free network. Letn0=n=15; we generated a model whose nodes’ total number is N=300. The average clustering coefficient magnifies as the triangle connection probability pt increases; furthermore, the average clustering coefficient approaches 0.5 when pt=1. The relation between cooperation density ρc and pt is shown in Figure 5, in which every data was averaged over 50 times of simulations. In every simulation, we conducted 15000 rounds of prisoners dilemma game and generated ρc with the average of the latest 5000 time steps.As shown in Figure5, the cooperation density has a positive relation with pt because the average clustering coefficient increases as pt increases and the degree distribution is power-law. Compared with BA models, the dependence relationship of the small degree nodes on the big degree ones is stronger, which encourages the cooperation in the game.Figure6 shows the ρc-T curves with a variable pt. The 4 curves almost coincide with the value range of T, and the difference happens in T∈(1.25,1.75), where the curves with higher pt falls on the upper side of the figure. In other words, the cooperation density increases as the average clustering coefficient increases.


## 4.1. Influence of Power-Law Coefficient

In this section, we simulate and analyze the influence of power-law coefficient on the emergence of cooperation in a power-law coefficient alterable model where the total nodes number isN=500 and average degree is 2m=30. Every data in Figures 1–6 is an average value of 50 network model simulations. Initially, 50% of cooperators and 50% of defectors are randomly distributed on the network. On each network, we conduct 10000 time steps (rounds), of which the former 8000 time steps are to guarantee that the system enters a steady state, and the latter 2000 time steps are to generate the average cooperation density ρc. The game model we adopt and the strategy update could be seen in Section 3.Figure 1
ρ
c
-
γ curve (T=1.5).Figure 2
ρ
c
-
T curve with alterable γ.Figure 3
ρ
c
-
k curve with alterable T.Figure 4
ρ
c
-
T curve with alterable 〈k〉.Figure 5
ρ
c
-
γ curve (T=1.5).Figure 6
ρ
c
-
T curve with alterable pt.Figure1 illustrates the relation between the cooperation density ρc and the power-law coefficient γ when the temptation is T=1.5. We can see that ρc decreases as γ increases, and it falls gradually onto a platform after γ>5. The reason, we reckon, is that the degree distribution of the network changes from power-law to Poisson distribution as γ increases; that is to say, the network evolves from heterogeneity to homogeneity; in other words, the degree distribution tends to be more uniform. As a result of that, the influence of nodes with big degrees on the nodes with small degrees weakens, and the small degree nodes tend to defection for their own interest.Figure2 shows the relation between the cooperation density ρc and the temptation parameter T when γ=3, γ=6, and γ=9. As shown in the figure, T has negative relation with ρc; in other words, the payoff matrix’s support of defection is correlated reciprocally with the cooperation density. And there exists a threshold Ta for every specific γ; when T>Ta, the cooperators disappear on the network, ρc=0.By observing the three curves in Figure2, we can see that the more heterogeneous the network is (with smaller γ), the higher the cooperation density is when T<2.5. This phenomenon indicates that the nodes with big degrees have strong influence on those with small degrees, and the small degree nodes tend to cooperate with those with big degrees. Nevertheless, when T>2.5, the three curves reverse their positions, and the cooperation density is low (ρc<0.2). The reason is that all individuals tend to each other due to the high temptation coefficient. The nodes with small degree are less dependent on those with big degree, which weakens the control of the network.


## 4.2. Influence of Average Degree

The average degree portrays the denseness of the network from a microscopic perspective; in other words, the network gets denser as we increase the average degree. In this section, we study the effect of different average degrees on the cooperation density. Every data is averaged over 100 model simulations. In every model, we conducted 10000 time steps of which the former 8000 time steps were to guarantee that the system has entered a steady state, and the latter 2000 time steps were to generate the average cooperation densityρc.Figure3 illustrates the cooperation density ρc with respect to average degree 〈k〉 for variations of temptation T. As seen in the figure, the relation between ρc and 〈k〉 is nonmonotonous: there exists one optimal average degree 〈k〉m which corresponds to the highest cooperation level when temptation is relatively low (T=1.5, T=2, and T=2.5). When 〈k〉=〈k〉m, the cooperation density reaches the top level, and cooperators are almost all over the network. When 〈k〉<〈k〉m, the cooperation density deceases rapidly, as the steep slope on the left side in Figure 3. When 〈k〉>〈k〉m, the cooperation density also decreases, but with a lower speed, and tends to a constant number 0.5, as the slope in the right of Figure 3. This indicates that we cannot expect more cooperators on a denser network for granted. As a result, we should set the average degree rationally when constructing a real network so as to ensure relatively high cooperation density with a limited cost.The relation between the cooperation densityρc and the temptation coefficient T with a variable 〈k〉 is shown in Figure 4. We can see that the curve corresponding to 〈k〉m is above all other curves only when T is small (T<1.67). This phenomenon depicts that the optimal average degree has an effective range.


## 4.3. Influence of Average Clustering Coefficient

The average clustering coefficient describes the clustering characteristic of a complex network. Most realistic networks are clustered; for instance, one’s friends know each other in social network.BA scale-free networks have relatively low average clustering coefficient which disagree with realistic conditions. In that, we studied the influence of average clustering coefficient on the emergence of cooperation on a clustering coefficient alterable scale-free network. Letn0=n=15; we generated a model whose nodes’ total number is N=300. The average clustering coefficient magnifies as the triangle connection probability pt increases; furthermore, the average clustering coefficient approaches 0.5 when pt=1. The relation between cooperation density ρc and pt is shown in Figure 5, in which every data was averaged over 50 times of simulations. In every simulation, we conducted 15000 rounds of prisoners dilemma game and generated ρc with the average of the latest 5000 time steps.As shown in Figure5, the cooperation density has a positive relation with pt because the average clustering coefficient increases as pt increases and the degree distribution is power-law. Compared with BA models, the dependence relationship of the small degree nodes on the big degree ones is stronger, which encourages the cooperation in the game.Figure6 shows the ρc-T curves with a variable pt. The 4 curves almost coincide with the value range of T, and the difference happens in T∈(1.25,1.75), where the curves with higher pt falls on the upper side of the figure. In other words, the cooperation density increases as the average clustering coefficient increases.


## 5. Conclusion

The emergence of cooperation on complex networks is of great importance, and it provides a new explanation of the population behavior evolution in both nature and society. Based on a power-law alterable model and a clustering coefficient alterable model, we studied the prisoners dilemma game on scale-free networks with synchronous update of Schlag strategy.The simulation results show that the cooperation level is correlated reciprocally with the power-law coefficient of the network and the relation between the cooperation density and the network average degree because there exists an optimal average degree corresponding to the highest cooperation level. The cooperation level has a positive relation with the average clustering coefficient when the latter is limited to a certain range.



---

*Source: 361270-2015-10-05.xml*