Cooperation and community structure in social networks

Situations of conflict giving rise to social dilemmas are widespread in society. One way of studying these important phenomena is by using simplified models of individual behavior under conflicting situations such as evolutionary game theory. Starting from the observation that individuals interact through networks of acquaintances, we study the evolution of cooperation on model and real social networks through well known paradigmatic games. Using a new payoff scheme which leaves replicator dynamics invariant, we find that cooperation is sustainable in such networks, even in the difficult case of the prisoner’s dilemma. The evolution and stability of cooperation implies the condensation of game strategies into the existing community structures of the social network in which clusters of cooperators survive thanks to their higher connectivity towards other fellow cooperators.     

Effect of community structure on coevolutionary dynamics with dynamical linking

We investigate the effect of community structure on the evolution of cooperation in the prisoner’s dilemma and the snowdrift game with dynamical linking. We show both analytically and numerically that cooperators are generally more favorable on community networks than on networks without community structure, and in particular, there exists an optimal intermediate value of the model parameter leading to the easiest fixation of cooperators. We show that our results are robust with respect to the initial number of cooperators and are valid for a wide range of the ratio of time scales associated with linking and strategy dynamics. Since community structure is ubiquitous in real social networks, our results may provide new insights into the evolution of cooperation in real world.     

Spatial Games Based on Pursuing the Highest Average Payoff

We propose a strategy updating mechanism based on pursuing the highest average payoff to investigate the prisoner＇s dilemma game and the snowdrift game. We apply the new rule to investigate cooperative behaviours on regular, small-world, scale-free networks, and find spatial structure can maintain cooperation for the prisoner＇s dilemma game. fn the snowdrift game, spatial structure can inhibit or promote cooperative behaviour which depends on payoff parameter. We further study cooperative behaviour on scale-free network in detail. Interestingly, non-monotonous behaviours observed on scale-free network with middle-degree individuals have the lowest cooperation level. We also find that large-degree individuals change their strategies more frequently for both games.     

Combinatorial games with a pass: a dynamical systems approach

By treating combinatorial games as dynamical systems, we are able to address a longstanding open question in combinatorial game theory, namely, how the introduction of a "pass" move into a game affects its behavior. We consider two well known combinatorial games, 3-pile Nim and 3-row Chomp. In the case of Nim, we observe that the introduction of the pass dramatically alters the game's underlying structure, rendering it considerably more complex, while for Chomp, the pass move is found to have relatively minimal impact. We show how these results can be understood by recasting these games as dynamical systems describable by dynamical recursion relations. From these recursion relations, we are able to identify underlying structural connections between these "games with passes" and a recently introduced class of "generic (perturbed) games." This connection, together with a (non-rigorous) numerical stability analysis, allows one to understand and predict the effect of a pass on a game.     

Elimination mechanism promotes cooperation in coevolutionary prisoner’s dilemma games

We propose an elimination mechanism in the study of the evolutionary prisoner’s dilemma games on evolving networks. It assumes that after each round of playing, players whose payoffs are below a certain threshold will be eliminated from the game and the same number of new nodes will be added to the network to maintain the size of the network constant. Numerical results show that moderate values of elimination threshold can result in a maximum cooperation level in the evolutionary prisoner’s dilemma game. Moreover, the elimination mechanism can make the network structure evolve into a high heterogeneity in degree distribution, which is considered to be helpful in promoting cooperation in evolutionary games. The present study may provide new insight for understanding the evolution of cooperation in light of the law ‘survival of the fittest’ in nature.     

Structure-preserving desynchronization of minority games

Perfect synchronicity in N-player games is a useful theoretical dream, but communication delays are inevitable and may result in asynchronous interactions. Some systems such as financial markets are asynchronous by design, and yet most theoretical models assume perfectly synchronized actions. We propose a general method to transform standard models of adaptive agents into asynchronous systems while preserving their global structure under some conditions. Using the minority game as an example, we find that the phase and fluctuations structure of the standard game subsists even in maximally asynchronous deterministic case, but that it disappears if too much stochasticity is added to the temporal structure of interaction. Allowing for heterogeneous communication speeds and activity patterns gives rise to a new information ecology that we study in details.     

Effects of average degree on cooperation in networked evolutionary game

We study effects of average degree on cooperation in the networked prisoner's dilemma game. Typical structures are considered, including random networks, small-world networks and scale-free networks. Simulation results show that the average degree plays a universal role in cooperation occurring on all these networks, that is the density of cooperators peaks at some specific values of the average degree. Moreover, we investigated the average payoff of players through numerical simulations together with theoretical predictions and found that simulation results agree with the predictions. Our work may be helpful in understanding network effects on the evolutionary games.     

Coevolving agent strategies and network topology for the public goods games

Much of human cooperation remains an evolutionary riddle. Coevolutionary public goods games in structured populations are studied where players can change from an unproductive public goods game to a productive one, by evaluating the productivity of the public goods games. In our model, each individual participates in games organized by its neighborhood plus by itself. Coevolution here refers to an evolutionary process entailing both deletion of existing links and addition of new links between agents that accompanies the evolution of their strategies. Furthermore, we investigate the effects of time scale separation of strategy and structure on cooperation level. This study presents the following: Foremost, we observe that high cooperation levels in public goods interactions are attained by the entangled coevolution of strategy and structure. Presented results also confirm that the resulting networks show many features of real systems, such as cooperative behavior and hierarchical clustering. The heterogeneity of the interaction network is held responsible for the observed promotion of cooperation. We hope our work may offer an explanation for the origin of large-scale cooperative behavior among unrelated individuals.     

Community structure of complex software systems: Analysis and applications

Due to notable discoveries in the fast evolving field of complex networks, recent research in software engineering has also focused on representing software systems with networks. Previous work has observed that these networks follow scale-free degree distributions and reveal small-world phenomena, while we here explore another property commonly found in different complex networks, i.e. community structure. We adopt class dependency networks, where nodes represent software classes and edges represent dependencies among them, and show that these networks reveal a significant community structure, characterized by similar properties as observed in other complex networks. However, although intuitive and anticipated by different phenomena, identified communities do not exactly correspond to software packages. We empirically confirm our observations on several networks constructed from Java and various third party libraries, and propose different applications of community detection to software engineering.     

Effects of the planarity and heterogeneity of networks on evolutionary two-player games

We study the effects of the planarity and heterogeneity of networks on evolutionary two-player symmetric games by considering four different kinds of networks, including two types of heterogeneous networks: the weighted planar stochastic lattice(a planar scale-free network) and the random uncorrelated scale-free network with the same degree distribution as the weighted planar stochastic lattice; and two types of homogeneous networks: the hexagonal lattice and the random regular network with the same degree k_0= 6 as the hexagonal lattice. Using extensive computer simulations, we found that both the planarity and heterogeneity of the network have a significant influence on the evolution of cooperation, either promotion or inhibition, depending not only on the specific kind of game(the Harmony, Snowdrift, Stag Hunt or Prisoner's Dilemma games), but also on the update rule(the Fermi, replicator or unconditional imitation rules).     

Arbiter as the Third Man in Classical and Quantum Games

We study the possible influence of a not necessarily sincere arbiter on the course of classical and quantum 2×2 games and we show that this influence in the quantum case is much bigger than in the classical case. Extreme sensitivity of quantum games on initial states of quantum objects used as carriers of information in a game shows that a quantum game, contrary to a classical game, is not defined by a payoff matrix alone but also by an initial state of objects used to play a game. Therefore, two quantum games that have the same payoff matrices but begin with different initial states should be considered as different games.     

Constructing quantum games from symmetric non-factorizable joint probabilities

We construct quantum games from a table of non-factorizable joint probabilities, coupled with a symmetry constraint, requiring symmetrical payoffs between the players. We give the general result for a Nash equilibrium and payoff relations for a game based on non-factorizable joint probabilities, which embeds the classical game. We study a quantum version of Prisoners' Dilemma, Stag Hunt, and the Chicken game constructed from a given table of non-factorizable joint probabilities to find new outcomes in these games. We show that this approach provides a general framework for both classical and quantum games without recourse to the formalism of quantum mechanics.     

Community structure and modularity in networks of correlated brain activity

Functional connectivity patterns derived from neuroimaging data may be represented as graphs or networks, with individual image voxels or anatomically-defined structures representing the nodes, and a measure of correlation between the responses in each pair of nodes determining the edges. This explicit network representation allows network-analysis approaches to be applied to the characterization of functional connections within the brain. Much recent research in complex networks has focused on methods to identify community structure, i.e. cohesive clusters of strongly interconnected nodes. One class of such algorithms determines a partition of a network into 'sub-networks' based on the optimization of a modularity parameter, thus also providing a measure of the degree of segregation versus integration in the full network. Here, we demonstrate that a community structure algorithm based on the maximization of modularity, applied to a functional connectivity network calculated from the responses to acute fluoxetine challenge in the rat, can identify communities whose distributions correspond to anatomically meaningful structures and include compelling functional subdivisions in the brain. We also discuss the biological interpretation of the modularity parameter in terms of segregation and integration of brain function.     

Response of scale-free networks with community structure to external stimuli

The response of scale-free networks with community structure to external stimuli is studied. By disturbing some nodes with different strategies, it is shown that the robustness of this kind of network can be enhanced due to the existence of communities in the networks. Some of the response patterns are found to coincide with topological communities. We show that such phenomena also occur in the cat brain network which is an example of a scale-free like network with community structure. Our results provide insights into the relationship between network topology and the functional organization in complex networks from another viewpoint.     

Graph kernels,hierarchical clustering,and network community structure: experiments and comparative analysis

There has been a quickly growing interest in properties of complex networks, such as the small world property, power-law degree distribution, network transitivity, and community structure, which seem to be common to many real world networks. In this study, we consider the community property which is also found in many real networks. Based on the diffusion kernels of networks, a hierarchical clustering approach is proposed to uncover the community structure of different extent of complex networks. We test the method on some networks with known community structures and find that it can detect significant community structure in these networks. Comparison with related methods shows the effectiveness of the method.     

Evolutionary Games in Two-Layer Networks with the Introduction of Dominant Strategy

We study evolutionary games in two-layer networks by introducing the correlation between two layers through the C-dominance or the D-dominance. We assume that individuals play prisoner's dilemma game(PDG) in one layer and snowdrift game(SDG) in the other. We explore the dependences of the fraction of the strategy cooperation in different layers on the game parameter and initial conditions. The results on two-layer square lattices show that, when cooperation is the dominant strategy; initial conditions strongly influence cooperation in the PDG layer while have no impact in the SDG layer. Moreover,in contrast to the result for PDG in single-layer square lattices, the parameter regime where cooperation could be maintained expands significantly in the PDG layer. We also investigate the effects of mutation and network topology. We find that different mutation rates do not change the cooperation behaviors. Moreover,similar behaviors on cooperation could be found in two-layer random networks.     

Duality, phase structures, and dilemmas in symmetric quantum games

Symmetric quantum games for 2-player, 2-qubit strategies are analyzed in detail by using a scheme in which all pure states in the 2-qubit Hilbert space are utilized for strategies. We consider two different types of symmetric games exemplified by the familiar games, the Battle of the Sexes (BoS) and the Prisoners’ Dilemma (PD). These two types of symmetric games are shown to be related by a duality map, which ensures that they share common phase structures with respect to the equilibria of the strategies. We find eight distinct phase structures possible for the symmetric games, which are determined by the classical payoff matrices from which the quantum games are defined. We also discuss the possibility of resolving the dilemmas in the classical BoS, PD, and the Stag Hunt (SH) game based on the phase structures obtained in the quantum games. It is observed that quantization cannot resolve the dilemma fully for the BoS, while it generically can for the PD and SH if appropriate correlations for the strategies of the players are provided.     

Towards the role of social connectivity and aspiration level on evolutionary game

Investigating the evolutionary game dynamics in structured populations is challenging due to the complexity of social interactions. There has been a growing interest in evolutionary game on social networks, particularly concerning how a specific network structure affects the evolution of strategies. Here, we consider a social network of interacting individuals playing the anti-coordination games with mixed strategies, and present a deterministic nonlinear equation for the evolution of strategies where the aspiration level is an incentive in the selection of strategies. We find that with an intermediate aspiration level, there exists an evolutionarily-stable mixed-strategy equilibrium if the cost-to-benefit ratio of altruistic is chosen below a threshold, which is determined by the largest Laplacian eigenvalue of the network. We also give extensive numerical simulations on regular and scale-free networks which confirm the validity of our analytical findings.     

Fast convergence in language games induced by majority rule

We propose a simple model to investigate the evolutionary dynamics of a naming game on well-mixed populations. We assume that each individual has an inherent propensity to maintain his own word about an object whereas other individuals would affect his decision when they communicate. On the one hand, individuals learn the word of another one with a probability pertaining to their propensities. On the other hand, the focal individual would adopt the word held by the majority in a randomly selected group. We have numerically explored how dynamical behavior evolves as a result of combination of these two competing update patterns. A parameter governs the time scale ratio at which the two update patterns separately progress. We find that an increasing tendency to adopt the word held by the majority results in a rapid extinction of most words, thus more easily induces the system to a global consensus. Large initial probabilities denoting propensity are found to be unfavorable for the achievement of the consensus. Interestingly, simulation results indicate that the convergence time is negligibly affected by the number of initial distinct words when this number exceeds a certain value. Results from our model may offer an insight into better understanding the intricate dynamics of naming games.