Advertisement
Research Article

Nodes Having a Major Influence to Break Cooperation Define a Novel Centrality Measure: Game Centrality

  • Gabor I. Simko,

    Affiliations: Department of Medical Chemistry, Semmelweis University, Budapest, Hungary, Vanderbilt University, Nashville, Tennessee, United States of America

    X
  • Peter Csermely mail

    csermely.peter@med.semmelweis-univ.hu

    Affiliation: Department of Medical Chemistry, Semmelweis University, Budapest, Hungary

    X
  • Published: June 28, 2013
  • DOI: 10.1371/journal.pone.0067159

Abstract

Cooperation played a significant role in the self-organization and evolution of living organisms. Both network topology and the initial position of cooperators heavily affect the cooperation of social dilemma games. We developed a novel simulation program package, called ‘NetworGame’, which is able to simulate any type of social dilemma games on any model, or real world networks with any assignment of initial cooperation or defection strategies to network nodes. The ability of initially defecting single nodes to break overall cooperation was called as ‘game centrality’. The efficiency of this measure was verified on well-known social networks, and was extended to ‘protein games’, i.e. the simulation of cooperation between proteins, or their amino acids. Hubs and in particular, party hubs of yeast protein-protein interaction networks had a large influence to convert the cooperation of other nodes to defection. Simulations on methionyl-tRNA synthetase protein structure network indicated an increased influence of nodes belonging to intra-protein signaling pathways on breaking cooperation. The efficiency of single, initially defecting nodes to convert the cooperation of other nodes to defection in social dilemma games may be an important measure to predict the importance of nodes in the integration and regulation of complex systems. Game centrality may help to design more efficient interventions to cellular networks (in forms of drugs), to ecosystems and social networks.

Introduction

Cooperation is necessary for the emergence of complex, hierarchical biological organisms. Prisoner’s dilemma and hawk-dove games are social dilemma games played by agent-pairs having two strategies: cooperation or defection. These games are excellent models to elucidate the appearance of cooperation in situations, when agents generally prefer defection. Such situations are prevalent in evolutionary biology, where personal interests often confront with collective interests [1], [2]. Recent reports defined ‘signaling games’ [3][6] or ‘protein games’ [7][9]. In protein games the applicability of social games was extended to protein-protein interaction networks, where cooperation level of the whole system helped to assess the overall integration of network functions. Here we extend these ideas further, and show the applicability of the spatial game concept to protein structure networks (also called residue interaction networks) having amino acids as their nodes.

In spatial games only those agents are playing with each other, who are neighbors in the underlying contact network. The level of cooperation is very sensitive to the topology of the agent network in a wide variety of social dilemma type games. Cooperation levels in square lattice, small world and scale-free network topologies have been widely assessed [10][17]. However, only a few studies were performed on real world networks [18], [19] and even less studies examined the effects of pre-set starting cooperative and defective strategies on the development of cooperation at the network level [20], [21]. Although, there are a number of spatial game-related programs [22][25], but none of them is able to simulate social dilemma games on real world networks with pre-set initial strategies.

Following our conference report on an initial version of the program [26], here we introduce the improved version of a freely available simulation tool, called NetworGame able to simulate two-player, pairwise interacting social dilemma games on real world networks with any assignment of initial cooperation or defection strategies to network nodes. A novel dynamic centrality, called game centrality, is also defined, which measures the ability of individually defecting nodes to convert others to their strategy. We show the applicability of game centrality on social, protein-protein interaction and protein structure networks, and highlight the importance of hubs in the maintenance of cooperation in complex biological systems.

Results

NetworGame Program for Simulation of Spatial Games on Any Real-world Networks

Our novel NetworGame 2.0 program package is a cross-platform, generic tool to simulate repeated spatial games. This simulation program includes i.) options for pay-off matrices of any symmetric normal form games (with 2 strategies); ii.) well-known, replicator-type strategy update rules (best takes over, Fermi-rule and proportional update [13]), as well as the option for additional, user-defined strategy update rules in a ‘plugin’-type format; iii.) synchronous, and semi-synchronous updating [27]; iv.) and the option for the inclusion of any real world networks in a Pajek [28] format (for the description of the simulation steps see Text S1). The program allows setting the starting strategy of any nodes according to the wish of the experimenter, and introduces the novel use of edge weights by considering edge weights as probabilities of the game played between the corresponding nodes. A brief description of the NetworGame 2.0 software is given in the Methods section, a more detailed description containing the pseudocode of the algorithm used is found in the Electronic (Text S1). The program with a User Guide is freely available from our website: www.linkgroup.hu/NetworGame.php.

Definition of Game Centrality as a Relative Importance of Nodes to Maintain Cooperation

Keeping in mind the relative scarcity of dynamic centrality measures [29][33] we defined a novel dynamic centrality, called game centrality, as follows. Initially let all nodes but node i cooperate, while set the initial strategy of node i to defect. Under these initial conditions the game centrality of a node i (GCi) is equal to the proportion of defectors averaged over the last 50 simulation steps.

In the determination of the simulation step range of the averaging process we considered two opposing effects. 1.) Averaging over a large number of steps resulted in more accurate results. 2.) However, averaging more game rounds also hindered convergence of the mean game centrality value, which determined the number of total rounds of the repeated game as described in the next paragraph. As we will discuss in the following paragraphs, game centrality (GC) is a relative measure useful for the comparison of the nodes in the same network. Therefore, GC may also be calculated and compared using more or less steps of average than 50. However, the selection of the last 50 game rounds as the ‘average-window’ avoided both potential pitfalls.

Game centrality values depend on the number of time steps (game rounds) and the number of parallel simulations. We may minimize GC-variability by measuring the proportion of defectors, where already no large fluctuations can be seen. This condition can be reached most of the times by using prisoner’s dilemma game on real world networks (but can not be reached using e.g. the evolutionary prisoner’s dilemma game on a square lattice [11]). Ensuring this condition, in the simulations of this paper the repeated rounds of serial games were concluded, when the mean value of GC changed less than 0.01 (called as GC-drift threshold) in the last 50 rounds. Small fluctuations caused by the stochasticity of some strategy update rules (e.g. replicator dynamics) and by the occasional stochasticity of edge weights (i.e. using the edge weights as update probabilities) may be minimized by averaging several simulations. The number of simulations was chosen to ensure that the mean error for the proportion of defectors was below 0.01 in the final step (called as GC-fluctuation threshold). As noted earlier, GC is used for the comparison of nodes. Therefore, both the GC-drift and GC-fluctuation thresholds may be set different than 0.01. However, selection of the threshold value 0.01 resulted in enough rounds of game simulations to surpass the initial transitional phase, often observed in repeated games, and resulted in relatively stable game centrality values. We note that the NetworGame simulation program can also be set to run simulations having a user-defined, pre-set number of game rounds.

It is important to note that numerical values of GC also depend on the payoff conditions and payoff parameters of the actual game model, on the applied strategy update rule, on the synchronicity of the update, as well as on the network structure. These features, together with those mentioned earlier, make GC a relative measure for the comparison of nodes in the same network using the same game conditions. Additionally, we found that the ranking of node GC-s largely correlated for different strategy update rules and temptation values for the relatively large yeast protein-protein interaction network studied (having 2,444 nodes and 6,271 edges; see data later). In this sense GC may also be used for a rough comparison of node importance to break cooperation using different game conditions.

In the current simulations we chose the canonical prisoner’s dilemma game with the payoff parameters R = 3, T = 6, S = 0, P = 1 (except for Michael’s strike network, where the temptation value was less: T = 3.1), since selection of the maximal temptation (T) value ensured the largest sensitivity of the initially almost fully cooperating network to the defection of a single node. Simulations used the widely applied best takes over strategy update rule with synchronous update.

Game Centrality Identifies Influential Members of Zachary’s Karate Club Network

Wayne Zachary [34] recorded the strength of contacts between members of a university karate club between 1970 and 1972. Meanwhile, the club had a dispute between the club president and the chief karate instructor, leading to a fission resulting in two separate clubs, which made this social network a gold standard for network modularization studies. To determine the most influential members of the karate club using the game centrality measure (GC) defined above, we simulated a prisoner’s dilemma game on the Zachary karate club network with the initial cooperation of every node except the examined, defective club member. Nodes #3 and #33, as well as #1, #2 and #34 had the top GC values having equal GC values within the first and second group of nodes and decreasing GC in the second group as compared to that of the first group. Node #1 corresponded to the instructor, while node #34 represented the club president. The large efficiency of these two and the other 3 nodes to break cooperation is related to the fact that the 5 nodes listed above had the five highest degrees in the network, and they were also found among the seven nodes having the largest betweenness centrality values (node ID-s in the order of decreasing centralities: #1, #34, #33, #3, #32, #9, #2).

Game Centrality Measures Identify Influential Member-pairs of Michael’s Strike Network

As a next step, we were interested, whether the game centrality of edges (i.e. the average proportion of defectors in the last 50 rounds, where not only a single node, but two neighboring nodes are both initial defectors) is also giving meaningful results. Michael’s strike network [35] was an excellent example to test this measure. Judd H. Michael described a strike in a forest product manufacturing factory. The factory had a new management, who wanted to change the compensation package of the workers. The two union negotiators (Sam and Wendle) were responsible for explaining the changes, but they failed to do so, and a strike broke out. The company hired Judd H. Michael to make a sociogram, which showed that there were three worker groups: younger, English-speaking, older, English-speaking, and younger, Spanish-speaking workers. Sam and Wendle formed a linked pair of nodes. Judd H. Michael advised to contact another linked pair of nodes, Bob and Norm – who were at the overlap of the three communities of the factory sociogram (see Figure S1 of Text S1) –, and to convince them about the changes. By following this strategy, the management solved the problem soon, and the strike ended.

In the social dilemma game simulations of the situation we considered strikers as cooperators and strike-breakers as defectors in canonical prisoner’s dilemma games having the payoff parameters of R = 3, T = 3.1, S = 0, P = 1. Initially everybody was cooperating, but the two linked workers chosen to explain the changes to the others. In repeated simulations the influence of different negotiator-pairs was compared. Simulation of the choice of Bob and Norm showed that they could convince everybody to stop the strike in 100% of the simulations. Simulation of the choice of Sam and Wendle led to the poor result of convincing the others to stop the strike in 8% of the simulations with the same settings, which corresponds well with outcome of the real-world events [35] (we got the same results for the weak prisoner’s dilemma game; data not shown). Our results show, that not only node game centrality, but also edge game centrality is giving a similar outcome than those happened in real-world situations.

Game Centrality Correlates with Former Centrality Measures and Reveals Novel Centers of Influence in Protein-protein Interaction Networks

As two proteins approach each other, they signal their status to the other via the hydrogen-bonded network of water molecules. Binding is achieved by a complex set of consecutive conformational adjustments. These concerted, conditional steps were called as a ‘protein dance’, and can be perceived as rounds of a repeated game [6][9]. Here we used the canonical prisoner’s dilemma game with a maximal temptation value (T = 6), since these parameters represent the most stringent conditions of cooperation among the most commonly used social dilemma games.

First we examined the effect of defection of party and date hubs on the cooperation of the high-fidelity yeast (Saccharomyces cerevisiae) protein-protein interaction network (interactome) of Ekman et al. [36] using the canonical prisoner’s dilemma game. Party hubs are hubs, which do not change their neighborhood structure, and are often situated in the middle of network modules. On the contrary, date hubs change their neighbors frequently, and often connect various modules of the interactome. The best distinction between party hubs and date hubs has been a subject of recent discussions [37][43]. Prisoner’s dilemma game simulations confirmed the differences between the two types of hubs. In the simulations initially we let all the 2,444 nodes cooperate except for 30 nodes, which defected. We compared the average game centrality values over 2000 simulations by random sampling 30 defecting nodes from the 63 consensus party hubs (compiled as in [43], see Table S1 of Text S1), or from the 145 consensus date hubs (compiled as in [43], see Table S2 of Text S1), or from all the 2,444 nodes, respectively. Party hubs had the largest game centrality, while date hubs and randomly selected node sets had smaller and smaller game centrality values, i.e. they distorted less and less the initial cooperation (Table 1). Using the chi-square test we found that the distribution of game centralities were significantly different (χ2>400) for the different test cases.

thumbnail

Table 1. Game centrality of party hubs, date hubs and randomly selected nodes of a high-fidelity yeast protein-protein interaction network.

doi:10.1371/journal.pone.0067159.t001

Next, we determined the correlation between degrees, betweenness centralities and GC-s in prisoner’s dilemma games of the 2,444 yeast proteins of the high fidelity yeast interactome [36]. Since both degree and betweenness centrality had a large number of tied values, we used the Goodman-Kruskal gamma test to test the association and significance of the results. Using canonical prisoner’s dilemma game we found that GC has a good correlation with both degrees and betweenness centralities (Table 2). We were also curious, which of the 3 measures of degree, betweenness centrality or game centrality predicts better the phenotypic potential of yeast protein describing their ‘buffering capacity’ against evolutionary changes, i.e. the contribution of an individual yeast protein to the overall robustness of yeast cells [44]. GCs were found to be significantly (p<0.062) better predictors of genetic buffering of evolutionary changes than either degrees or betwenness centralities (Table 2).

thumbnail

Table 2. Correlations of game centrality (GC) with degree, betweenness centrality and phenotypic potential of proteins in a high fidelity yeast interactome.

doi:10.1371/journal.pone.0067159.t002

The functional analysis of the 171 proteins of the high-fidelity yeast interactome [36] causing the final cooperation level to fall from the starting value of close to 1.0 to less than 0.9 showed the overrepresentation (p<0.001) of nucleus-related functions (35%). The second and third most overrepresented classes were signaling- and transport-related functions (33% and 32%, respectively; Figure 1). These results were in compliance with the central position of the nucleus in the structure, organization and dynamics of the cell. Similarly, transport and signaling are central in both internal and external cellular communication.

thumbnail

Figure 1. Functional analysis of yeast proteins having the largest game centralities.

Prisoner’s dilemma game was simulated on a high-fidelity yeast interactome [36], and game centrality measures were calculated as described in Methods. 171 proteins out of the 2,444 nodes of the high-fidelity yeast interactome were selected by selecting nodes, which diminished the cooperation level from ~1 to 0.9 or below. Functional analysis of the 171 proteins was performed using the Cytoscape plug-in, BiNGO [63] to assess the over-representation of associated Gene Ontology molecular function terms. Gene Ontology Slim definitions for Saccharomyces cerevisiae [64] were used discarding the evidence codes IEA (inferred from electronic annotation), ISS (inferred from sequence structural similarity) and NAS (non-traceable author statement). A hypergeometric test with false discovery rate correction [65] was used to select and visualize the significantly enriched GO functions at a level p<0.001, using the GO-s of the entire network as reference set. Colors represent functional categories: red, nucleus-related; blue, transport-related; green, signaling-related; yellow denotes other functions. The size of the circles represents the number of proteins found in the category.

doi:10.1371/journal.pone.0067159.g001

In conclusion, game centrality observed in prisoner’s dilemma games of nodes in a yeast protein-protein interaction network (i.e. in a ‘protein game’) offered a novel characterization of the importance of proteins in complex cellular functions highlighting the importance of intra-modular party hubs to maintain cooperation.

As we said before, game centrality is a comparative measure within a network having set a game type, strategy update rule, temptation value and synchronicity. To assess the consistency of game centrality ranking, we ran multiple experiments with different temptation values (T = 3.1, 4, 5 and 6) and/or the strategy update rules (best-takes-over and Fermi-rule) for the yeast interactome network. We evaluated the pair-wise correlation (Goodman-Kruskal gamma) between the game centralities for the case of small (3.1 and 4.0) and large temptation values (5.0 and 6.0), while applying the best-takes-over and the Fermi-rule strategy update rules. The smallest pair-wise correlation was 0.72 for the small temptation values and 0.70 for the large temptation values. These results indicate that while the game settings do have effects on the individual game-centrality values, GC may also be used for a rough comparison of node importance to break cooperation using different game conditions.

Game Centrality Identifies Functionally Important Segments of Protein Structures

Next, we extended the use of the game centrality to another important biological network, the protein structure network, where the nodes are amino acids, and the edges between them represent chemical bonds [6], [45], [46]. We analyzed the protein structure network of the Escherichia coli methionyl-tRNA synthetase protein, for which an elegant study [46] showed the existence of several alternative intra-protein signal transduction pathways. These signaling paths span a large distance between the active centre and the anticodon binding region of this enzyme transmitting the allosteric conformational changes induced by substrate binding. The methionyl-tRNA synthetase protein has two major domains, the catalytic domain (responsible for the activation of methionine) and the tRNA anticodon-binding domain. These two domains are connected by the connecting peptide (CP) domain. The catalytic domain can be subdivided to three sub-domains, having two Rossmann-folds and a stem contact fold [46].

First, we compared the game centrality (GC) of the amino acids in the two major domains and their connecting peptide. The average GC values of both major domains were higher (both before and after substrate binding) than that of the connecting peptide domain (Table 3, Figure 2). In agreement with their central role in protein function, the average GC of intra-protein signaling amino acids as defined by Ghosh and Vishveshwara [46] was especially high, if compared to GC-s of the rest of the amino acids (Table 3). Substrate binding induced a decrease of GC of most domains, which is in agreement with the development of a more compact structure, where amino acids may indeed have a lower individual influence on domain-level processes. GC differences between the open and closed conformations reflected that substrate binding affected most the tRNA anticodon domain and the core of the catalytic domain (the first Rossmann-fold domain; Table 3, Figure 2), which is again in agreement with the high increase of compactness around the tRNA and substrate binding pockets upon substrate binding. These findings are also in agreement with the prominent influence of binding sites on the cooperating network of amino acids revealed by molecular dynamics simulations [47].

thumbnail

Figure 2. Game centralities of E. coli methionyl-tRNA synthetase amino acids.

The protein structure network of E. coli methionyl-tRNA-synthetase was constructed, prisoner’s dilemma game was simulated, and game centrality measures were calculated as described in Methods. Game centralities were overlaid to the 3D image of the protein and tRNA made by the PyMOL program package [66]. tRNAMet is shown in green, the most influential amino acids spreading defection are marked red (these amino acids have the largest game centrality, GC values) and the least influential amino acids are blue (having the smallest GC values).

doi:10.1371/journal.pone.0067159.g002
thumbnail

Table 3. Average game centrality (GC) values for E. coli methionyl-tRNA synthetase amino acids.

doi:10.1371/journal.pone.0067159.t003

In conclusion, game centrality values observed in prisoner’s dilemma games of individual amino acids of protein structure networks highlighted the importance of core protein domains, especially the tRNA anticodon binding domain, the active centre and intra-protein signaling amino acids in the maintenance of cooperation of this complex system.

Discussion

In this paper a novel program package, called NetworGame was introduced to simulate various social dilemma type games with a high flexibility for payoff conditions, initial parameters, strategies, strategy update rules and update conditions. We defined a novel dynamic centrality measure called game centrality (GC), and showed that it correlates with previous centrality measures, such as degree, or betwenness centralities. Moreover, GC also predicts novel influential nodes and network segments, which have a functional relevance in several social and biological real world networks.

Although several game simulation tools have been described in the literature, such as GamePlan [22], Gambit [23], Dynamo [24] and VirtualLabs/EvoLudo [25], the NetworGame program package is unique in the sense, that it is able to accept any real-world networks as an input with the complexity of their weighted edges. Moreover, the program can handle individual initial strategies of all networked agents, as well as individual strategy update rules. The current NetworGame 2.0 version has automated, statistics-based simulation length and simulation count options, which were not present in its preliminary NetworGame 1.0 version mentioned in our former conference report [26]. We note that NetworGame 2.0 can also be used for simulations having a user-defined, pre-set number of game rounds.

While game centrality correlated with previous centrality measures, such as degree and betweenness centrality, it also predicted novel nodes and centers of large influence, which had functional relevance both in social and biological real-world networks. Identification of functionally and dynamically important network nodes and segments is not an easy field. i.) The identification of nodes with large and dynamic influence has been notoriously difficult [29][33], [48][50]. ii.) The precise discrimination between hubs with different dynamic parameters became a subject of recent discussions [36][43]. iii.) The contribution of individual proteins to the overall robustness of the cell against evolutionary changes is a largely unresolved question [44], [51], [52]. iv.) Though enzyme active sites and protein binding hot-spots have been identified using network metrics, such as betweenness centrality, amino acids of intra-protein signaling are not readily distinguishable [53][55]. Game centrality provides a novel and promising aspect to compare the influence of network nodes and segments using the cooperation-related, complex dynamic background of social dilemma games.

Game centrality values depend on the game model and its payoff conditions, on the applied strategy update rule, on the synchronicity of the update, on the network structure as well as on the number of time steps and total number of simulations. This makes game centrality a relative measure, and requires an especially large level of cautiousness in its use, when the level of final cooperation fluctuates (e.g. in games on square lattice [11], rock-scissors-paper games [56], etc.). However, the case studies we made suggest that game centrality values of both individual nodes and edges (pairs of neighboring nodes) can be useful for the comparison of influence in the same network when using the canonical prisoner’s dilemma game on various networks. Moreover, game centrality may be used for the comparison of different states of the same network, which differ e.g. only in their weight structure, like that of the yeast protein-protein interaction network before and after stress [57].

In this paper we calculated game centrality for initially defecting single nodes or edges (pairs of neighboring nodes) of the network. However, it is important to note that a similar centrality measure may also be calculated for the inverse situation, where a pair of linked nodes is the only initial cooperator in an otherwise defecting network. Moreover, similar centrality measures may also be defined for larger segments of nodes, such as for triangles, motifs, k-cliques, k-clans, k-clubs, k-components, k-plexes, lambda-sets, network skeletons, rich clubs, network cores, or network communities [43] using the NetworGame program.

From a different point of view, game centrality indirectly measures the capability of a node to alter network reciprocity. A highly influential node with large game centrality tends to break the cooperative islands, the sources of network reciprocity in the network. In this paper we do not discuss network reciprocity in detail, but we refer the interested reader to references [58] and [59].

Currently NetworGame only supports pairwise interactions between the players. It is an interesting future work to include group interactions in NetworGame, since it is known [60] that group interaction can lead to behaviors that cannot be attributed to the sum of pairwise interactions.

In conclusion, our NetworGame program package proved to be a useful tool for the analysis of repeated spatial games on real-world networks, and enabled the definition of a novel game-related centrality measure called game centrality (GC). Game centrality correlated with previous centrality measures, such as degree and betweenness centrality. Moreover, GC also identified novel, functionally important nodes and network segments in both social and biological networks. Our work opens the ground for a number of further studies on the dependence of game centrality of various parameters of social dilemma games as well as a wide variety of real world networks including neuronal networks [61]. Game centrality may become a useful measure to identify key network nodes of various processes of network dynamics, such as conformational changes, allosteric and cellular signaling, cell differentiation, cell reprogramming and malignant transformation. Game centrality may help to design more efficient interventions to cellular networks (in forms of drugs), to ecosystems or to social networks.

Methods

Description of the Real World Networks

Zachary’s karate club network. The weighted and undirected social network of the karate club at a US university contained 34 nodes and 78 edges described by Wayne Zachary in 1977 [34]. Michael’s strike network. The social network of a forest product manufacturing factory contained 24 nodes and 38 edges as described by Judd H. Michael in 1997 [35]. Yeast protein-protein interaction network. The giant component of the un-weighted and undirected high-fidelity yeast protein-protein interaction network [36] contained 2,444 nodes and 6,271 edges, covering approximately half of the yeast genome and containing the most reliable ~3% of the expected number of total edges. E. coli methionyl-tRNA synthase protein structure network. We have constructed the structural network from the 3D image of the starting (substrate-free) and the equilibrated (substrate-bound) state of the molecular simulation of the E. coli methionyl-tRNA synthetase/tRNA/MetAMP complex [46] by converting the Cartesian coordinates of the 3D image to distances of amino acid pairs, and keeping all non-covalently bonded contacts within a distance of 0.4 nm. The final weighted network was created by removing self-loops, and calculating the inverse of the average distance between amino acid residues as edge weights. The protein structure network contained 547 nodes, since the first 3 N-terminal amino acids were not participating in the network. The protein structure contained 2,164 edges in the substrate-free network, and 2,153 edges in the substrate-bound network.

Brief Description of the NetworGame Program Package

The NetworGame software is a program that takes a configuration specification describing the social dilemma game rules, the model or real world network and other settings, executes the simulations accordingly, and stores the simulation results. The simulation engine of the NetworGame program is a highly optimized software component for running the actual simulation. The 2.0 version of the NetworGame program is an updated version of the NetworGame 1.0 version published in a preliminary conference report [26]. A more detailed description of the NetworGame program version 2.0 containing the pseudo codes of its algorithms is found in the (Text S1). Both versions of the NetworGame program, as well as their User Guides are freely downloadable from our website: www.linkgroup.hu/NetworGame.php.

Parameters of Simulations and Calculation of Game Centrality (GC)

For the analysis of real-world networks we chose the canonical prisoner’s dilemma game with the payoff parameters R = 3, T = 6, S = 0, P = 1 (except for Michael’s strike network, where we used T = 3), since this selection with a maximal temptation (T) value ensured the largest sensitivity of the initially almost fully cooperating network to the defection of a single node. In our simulations edge weights were not used. All simulations used the widely applied best takes over strategy update rule with a synchronous update. Simulations of repeated games were halted, when the mean value of cooperation changed less than 0.01 in the last 50 rounds. The number of parallel simulations was chosen to ensure that the mean error for the cooperation level was below 0.01 in the final step. These conditions allowed enough simulations to get a statistically meaningful mean estimate, and made the number of simulation steps large enough to surpass the initial transitional phase often observed in simulations of repeated social dilemma games. Game centrality (GC) of node i was calculated as the proportion of defectors averaged over the last 50 simulation steps, when initially node i was set to defect, while all other nodes were set to cooperate.

Supporting Information

Text S1.

This supporting information (Text S1) contains a supplementary figure, 2 supplementary tables, a detailed description of the NetworGame algorithm for the simulation of spatial social dilemma games with pseudocodes, as well as 11 supplementary references.

doi:10.1371/journal.pone.0067159.s001

(PDF)

Acknowledgments

The authors would like to thank Saraswathi Vishveshwara (Molecular Biophysics Unit, Indian Institute of Science, Bangalore) and Amit Ghosh (Lawrence Berkeley National Laboratory, Berkeley CA, USA) for the 3D data of the molecular simulation of the E. coli methionyl-tRNA synthetase/tRNA/MetAMP complex and Eszter Hazai (VirtuaDrug Co., Budapest, Hungary) for the protein structure network data. We thank Csaba Böde (Morgan Stanley, Budapest, Hungary) and István A. Kovács (Wigner Research Centre for Physics, Hungarian Academy of Sciences, Budapest, Hungary) for their help in the statistical calculations. We thank members of the LINK-group (www.linkgroup.hu) especially Miklós Antal, Kristóf Kubina, András London, Máté S. Szalay and Shijun Wang (Clinical Center, National Institutes of Health, Bethesda MD USA), as well as György Szabó (Hungarian Academy of Sciences, Budapest, Hungary) for helpful discussions.

The work published in this paper was done while Gabor I. Simko worked at the Budapest University of Technology and Economics, Budapest, Hungary.

Author Contributions

Conceived and designed the experiments: GS PC. Performed the experiments: GS. Analyzed the data: GS PC. Contributed reagents/materials/analysis tools: GS PC. Wrote the paper: GS PC.

References

  1. 1. Axelrod R (1984) The evolution of cooperation. New York: Basic Books.
  2. 2. Nowak MA (2006) Five rules for the evolution of cooperation. Science 314: 1560–1563. doi: 10.1126/science.1133755
  3. 3. Bergstrom CT, Számadó S, Lachmann M (2002) Separating equilibria in continuous signalling games. Philos Trans R Soc Lond B Biol Sci 357: 1595–1606. doi: 10.1098/rstb.2002.1068
  4. 4. Donaldson MC, Lachmann M, Bergstrom CT (2007) The evolution of functionally referential meaning in a structured world. J Theor Biol 246: 225–233. doi: 10.1016/j.jtbi.2006.12.031
  5. 5. Zollman KJ, Bergstrom CT, Huttegger SM (2013) Between cheap and costly signals: the evolution of partially honest communication. Proc Biol Sci 280: 20121878. doi: 10.1098/rspb.2012.1878
  6. 6. Kovacs IA, Szalay MS, Csermely P (2005) Water and molecular chaperones act as weak links of protein folding networks: energy landscape and punctuated equilibrium changes point towards a game theory of proteins. FEBS Lett 579: 2254–2260. doi: 10.1016/j.febslet.2005.03.056
  7. 7. Chettaoui C, Delaplace F, Manceny M, Malo M (2007) Games network and application to PAs system. Biosystems 87: 136–141. doi: 10.1016/j.biosystems.2006.09.006
  8. 8. Schuster S, Kreft JU, Schroeter A, Pfeiffer T (2008) Use of game-theoretical methods in biochemistry and biophysics. J Biol Phys 34: 1–17. doi: 10.1007/s10867-008-9101-4
  9. 9. Csermely P, Palotai R, Nussinov R (2010) Induced fit, conformational selection and independent dynamic segments: an extended view of binding events. Trends Biochem Sci 35: 539–546. doi: 10.1016/j.tibs.2010.04.009
  10. 10. Szabó G, Fáth G (2007) Evolutionary games on graphs. Phys Rep 446: 97–216. doi: 10.1016/j.physrep.2007.04.004
  11. 11. Nowak RM, May MA (1992) Evolutionary games and spatial chaos. Nature 359: 826–829. doi: 10.1038/359826a0
  12. 12. Santos FC, Pacheco JM (2005) Scale-free networks provide a unifying framework for the emergence of cooperation. Phys Rev Lett 95: 98104. doi: 10.1103/physrevlett.95.098104
  13. 13. Tomassini M, Luthi L, Giacobini M (2006) Hawks and doves on small-world networks. Phys Rev E 73: 016132. doi: 10.1103/physreve.73.016132
  14. 14. Wang S, Szalay MS, Zhang C, Csermely P (2008) Learning and innovative elements of strategy update rules expand cooperative network topologies. PLoS ONE 3: e1917. doi: 10.1371/journal.pone.0001917
  15. 15. Perc M, Szolnoki A, Szabó G (2008) Restricted connections among distinguished players support cooperation. Phys Rev E 78: 066101. doi: 10.1103/physreve.78.066101
  16. 16. Helbing D, Szolnoki A, Perc M, Szabó G (2010) Evolutionary establishment of moral and double moral standards through spatial interactions. PLoS Comput Biol 6: e1000758. doi: 10.1371/journal.pcbi.1000758
  17. 17. Wang Z, Szolnoki A, Perc M (2012) If players are sparse social dilemmas are too: Importance of percolation for evolution of cooperation. Sci Rep 2: 369. doi: 10.1038/srep00369
  18. 18. Holme P, Trusina A, Kim BJ, Minnhagen P (2003) Prisoners’ dilemma in real-world acquaintance networks: Spikes and quasiequilibria induced by the interplay between structure and dynamics. Phys Rev E 68: 030901. doi: 10.1103/physreve.68.030901
  19. 19. Fu F, Chen X, Liu L, Wang L (2007) Social dilemmas in an online social network: the structure and evolution of cooperation. Phys Lett A 371: 58–64. doi: 10.1016/j.physleta.2007.05.116
  20. 20. Han-Xin Y, Kun G, Xiao-Pu H, Bing-Hong W (2008) Evolutionary snowdrift game on heterogeneous Newman-Watts small-world network. Chin Phys B 17: 2759–2763. doi: 10.1088/1674-1056/17/8/002
  21. 21. Chen X, Fu F, Wang L (2008) Influence of different initial distributions on robust cooperation in scale-free networks: A comparative study. Phys Lett A 372: 1161–1167. doi: 10.1016/j.physleta.2007.09.044
  22. 22. Langlois JP (1996) GamePlan: http://home1.gte.net/vze3hvm3/html.htm.
  23. 23. McKelvey RD, McLennan AM, Turocy TL (2010) Gambit: Software Tools for Game Theory, Version 0.2010.09.01. http://www.gambit-project.org.
  24. 24. Sandholm DWH, Dokumaci E, Franchetti F (2012) Dynamo: Diagrams for Evolutionary Game Dynamics, version 0.2.5. http://www.ssc.wisc.edu/~whs/dynamo.
  25. 25. Traulsen A, Claussen JC, Hauert C (2012) Stochastic differential equations for evolutionary dynamics with demographic noise and mutations. Phys Rev E 85: 041901. doi: 10.1103/physreve.85.041901
  26. 26. Farkas IJ, Korcsmáros T, Kovács IA, Mihalik Á, Palotai R, et al. (2011) Network-based tools in the identification of novel drug-targets. Science Signaling 4: pt3. doi: 10.1126/scisignal.2001950
  27. 27. Saif MA, Gade PM (2009) The prisoner’s dilemma with semi-synchronous updates: evidence for a first-order phase transition. J Stat Mech Theor Exp 7: P07023. doi: 10.1088/1742-5468/2009/07/p07023
  28. 28. Batagelj V, Mrvar A (1998) Pajek - Program for large network analysis. Connections 21: 47–57. doi: 10.1017/cbo9780511996368
  29. 29. Braha D, Bar-Yam Y (2006) From centrality to temporary frame: dynamic centrality in complex networks. Complexity 12: 59–63. doi: 10.1002/cplx.20156
  30. 30. Lehrman K, Gosh R, Kang JH (2010) Centrality metric for dynamic networks. Proc. 8th Workshop Mining Learning Graphs 70−77.
  31. 31. Masuda N, Kori H (2010) A dynamics-based centrality for general directed networks. Phys Rev E 82: 056107. doi: 10.1103/physreve.82.056107
  32. 32. Klemm K, Serrano MA, Eguiluz VM, Miguel MS (2012) A measure of individual role in collective dynamics. Sci Rep 2: 292. doi: 10.1038/srep00292
  33. 33. Ghosh R, Lerman K (2012) Rethinking centrality: the role of dynamical processes in social network analysis. http://arxiv.org/abs/1209.4616.
  34. 34. Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthrop Res 33: 452–473.
  35. 35. Michael JH (1997) Labor dispute reconciliation in a forest products manufacturing facility. Forest Products J 47: 41–45.
  36. 36. Ekman D, Light S, Björklund A, Elofsson A (2006) What properties characterize the hub proteins of the protein-protein interaction network of Saccharomyces cerevisiae? Genome Biol 7: R45.
  37. 37. Han JD, Bertin N, Hao T, Goldberg DS, Berriz GF, et al. (2004) Evidence for dynamically organized modularity in the yeast protein-protein interaction network. Nature 430: 88–93. doi: 10.1038/nature02555
  38. 38. Batada NN, Reguly T, Breitkreutz A, Boucher L, Breitkreutz BJ, et al. (2006) Stratus not altocumulus: a new view of the yeast protein interaction network. PLoS Biol 4: e317. doi: 10.1371/journal.pbio.0040317
  39. 39. Kim PM, Lu LJ, Xia Y, Gerstein MB (2006) Relating three-dimensional structures to protein networks provides evolutionary insights. Science 314: 1938–1941. doi: 10.1126/science.1136174
  40. 40. Komurov K, White M (2007) Revealing static and dynamic modular architecture of the eukaryotic protein interaction network. Mol Syst Biol 3: 110. doi: 10.1038/msb4100149
  41. 41. Bertin N, Simonis N, Dupuy D, Cusick ME, Han JD, et al. (2007) Confirmation of organized modularity in the yeast interactome. PLoS Biol 5: e153. doi: 10.1371/journal.pbio.0050153
  42. 42. Agarwal S, Deane CM, Porter MA, Jones NS (2010) Revisiting date and party hubs: novel approaches to role assignment in protein interaction networks. PLoS Comput Biol 6: e1000817. doi: 10.1371/journal.pcbi.1000817
  43. 43. Kovács IA, Palotai R, Szalay MS, Csermely P (2010) Community landscapes: a novel, integrative approach for the determination of overlapping network modules. PLoS ONE 7: e12528. doi: 10.1371/journal.pone.0012528
  44. 44. Levy SF, Siegal ML (2008) Network hubs buffer environmental variation in Saccharomyces cerevisiae. PLoS Biol 6, e264.
  45. 45. Dokholyan NV, Li L, Ding F, Shakhnovich EI (2002) Topological determinants of protein folding. Proc Natl Acad Sci U S A 99: 8637–8641. doi: 10.1073/pnas.122076099
  46. 46. Ghosh A, Vishveshwara S (2007) A study of communication pathways in methionyl- tRNA synthetase by molecular dynamics simulations and structure network analysis. Proc Natl Acad Sci U S A 104: 15711–15716. doi: 10.1073/pnas.0704459104
  47. 47. Liu T, Whitten ST, Hilser VJ (2007) Functional residues serve a dominant role in mediating the cooperativity of the protein ensemble. Proc Natl Acad Sci U S A 104: 4347–4352. doi: 10.1073/pnas.0607132104
  48. 48. Csermely P (2008) Creative elements: network-based predictions of active centres in proteins, cellular and social networks. Trends Biochem Sci 33: 569–576. doi: 10.1016/j.tibs.2008.09.006
  49. 49. Liu YY, Slotine JJ, Barabási AL (2011) Controllability of complex networks. Nature 473: 167–173. doi: 10.1038/nature10011
  50. 50. Nepusz T, Vicsek T (2012) Controlling edge dynamics in complex networks. Nature Physics 8: 568–573. doi: 10.1038/nphys2327
  51. 51. Csermely P (2006) Weak links: Stabilizers of complex systems from proteins to social networks. Springer, Heidelberg.
  52. 52. Masel J, Trotter MV (2010) Robustness and evolvability. Trends Genet 26: 406–414. doi: 10.1016/j.tig.2010.06.002
  53. 53. Csermely P, Sandhu KS, Hazai E, Hoksza Z, Kiss HJM, et al. (2011) Disordered proteins and network disorder in network representations of protein structure, dynamics and function. Curr Prot Pept Sci 13: 19–33. doi: 10.2174/138920312799277992
  54. 54. Zhuravlev PI, Papoian GA (2010) Protein functional landscapes, dynamics, allostery: a tortuous path towards a universal theoretical framework. Q Rev Biophys 43: 295–332. doi: 10.1017/s0033583510000119
  55. 55. Rader AJ, Brown SM (2011) Correlating allostery with rigidity. Mol Biosyst 7: 464–471. doi: 10.1039/c0mb00054j
  56. 56. Szolnoki A, Szabó G (2004) Phase transitions for rock-scissors-paper game on different networks. Phys Rev E 70, 037102.
  57. 57. Mihalik Á, Csermely P (2011) Heat shock partially dissociates the overlapping modules of the yeast protein-protein interaction network: a systems level model of adaptation. PLoS Comput Biol 7: e1002187. doi: 10.1371/journal.pcbi.1002187
  58. 58. Nowak MA, May RM (1992) Evolutionary games and spatial chaos. Nature 359: 826–829. doi: 10.1038/359826a0
  59. 59. Nowak MA (2006) Five rules for the evolution of cooperation. Science 314: 1560–1563. doi: 10.1126/science.1133755
  60. 60. Perc M, Gómez-Gardeñes J, Szolnoki A, Floría LM, Moreno Y (2013) Evolutionary dynamics of group interactions on structured populations: a review. J Royal Soc Interface 10: 20120997. doi: 10.1098/rsif.2012.0997
  61. 61. Kötter R, Reid AT, Krumnack A, Wanke E, Sporns O (2007) Shapley ratings in brain networks. Front Neuroinform 1: 2. doi: 10.3389/neuro.11.002.2007
  62. 62. Steiger JH (1980) Tests for comparing elements of a correlation matrix. Psychol Bull 87: 245–251. doi: 10.1037/0033-2909.87.2.245
  63. 63. Maere S, Heymans K, Kuiper M (2005) BiNGO: a Cytoscape plugin to assess overrepresentation of Gene Ontology categories in biological networks. Bioinformatics 21: 3448–3449. doi: 10.1093/bioinformatics/bti551
  64. 64. The Gene Ontology Consortium (2000) Gene ontology: tool for the unification of biology. Nat Genet 25: 25–29.
  65. 65. Benjamini Y, Hochberg Y (1995) Controlling the false discovery rate: a practical and powerful approach to multiple testing. J Roy Statist Soc B 57: 289–300.
  66. 66. DeLano WL (2002) The PyMOL Molecular Graphics System. DeLano Scientific, San Carlos, CA, USA. http://www.pymol.org.