Evolutionary games on complex networks : the emergence and maintenance of cooperation

Abstract The object of game theory lies in the analysis of situations where different social actors have conflicting requirements and where their individual decisions will all influence the global outcome. In this framework, several games have been invented to capture the essence of various dilemmas encountered in many common important socio-economic situations. Even though these games often succeed in helping us understand human or animal behavior in interactive settings, some experiments have shown that people tend to cooperate with each other in situations for which classical game theory strongly recommends them to do the exact opposite. Several mechanisms have been invoked to try to explain the emergence of this unexpected cooperative attitude. Among them, repeated interaction, reputation, and belonging to a recognizable group have often been mentioned. However, the work of Nowak and May (1992) showed that the simple fact of arranging the players according to a spatial structure and only allowing them to interact with their immediate neighbors is sufficient to sustain a certain amount of cooperation even when the game is played anonymously and without repetition. Nowak and May's study and much of the following work was based on regular structures such as two-dimensional grids. Axelrod et al. (2002) showed that by randomizing the choice of neighbors, i.e. by actually giving up a strictly local geographical structure, cooperation can still emerge, provided that the interaction patterns remain stable in time. This is a first step towards a social network structure. However, following pioneering work by sociologists in the sixties such as that of Milgram (1967), in the last few years it has become apparent that many social and biological interaction networks, and even some technological networks, have particular, and partly unexpected, properties that set them apart from regular or random graphs. Among other things, they usually display broad degree distributions, and show small-world topological structure. Roughly speaking, a small-world graph is a network where any individual is relatively close, in terms of social ties, to any other individual, a property also found in random graphs but not in regular lattices. However, in contrast with random graphs, small-world networks also have a certain amount of local structure, as measured, for instance, by a quantity called the clustering coefficient. In the same vein, many real conflicting situations in economy and sociology are not well described neither by a fixed geographical position of the individuals in a regular lattice, nor by a random graph. Furthermore, it is a known fact that network structure can highly influence dynamical phenomena such as the way diseases spread across a population and ideas or information get transmitted. Therefore, in the last decade, research attention has naturally shifted from random and regular graphs towards better models of social interaction structures. The primary goal of this work is to discover whether or not the underlying graph structure of real social networks could give explanations as to why one finds higher levels of cooperation in populations of human beings or animals than what is prescribed by classical game theory. To meet this objective, I start by thoroughly studying a real scientific coauthorship network and showing how it differs from biological or technological networks using divers statistical measurements. Furthermore, I extract and describe its community structure taking into account the intensity of a collaboration. Finally, I investigate the temporal evolution of the network, from its inception to its state at the time of the study in 2006, suggesting also an effective view of it as opposed to a historical one. Thereafter, I combine evolutionary game theory with several network models along with the studied coauthorship network in order to highlight which specific network properties foster cooperation and shed some light on the various mechanisms responsible for the maintenance of this same cooperation. I point out the fact that, to resist defection, cooperators take advantage, whenever possible, of the degree-heterogeneity of social networks and their underlying community structure. Finally, I show that cooperation level and stability depend not only on the game played, but also on the evolutionary dynamic rules used and the individual payoff calculations. Synopsis Le but de la théorie des jeux réside dans l'analyse de situations dans lesquelles différents acteurs sociaux, avec des objectifs souvent conflictuels, doivent individuellement prendre des décisions qui influenceront toutes le résultat global. Dans ce cadre, plusieurs jeux ont été inventés afin de saisir l'essence de divers dilemmes rencontrés dans d'importantes situations socio-économiques. Bien que ces jeux nous permettent souvent de comprendre le comportement d'êtres humains ou d'animaux en interactions, des expériences ont montré que les individus ont parfois tendance à coopérer dans des situations pour lesquelles la théorie classique des jeux prescrit de faire le contraire. Plusieurs mécanismes ont été invoqués pour tenter d'expliquer l'émergence de ce comportement coopératif inattendu. Parmi ceux-ci, la répétition des interactions, la réputation ou encore l'appartenance à des groupes reconnaissables ont souvent été mentionnés. Toutefois, les travaux de Nowak et May (1992) ont montré que le simple fait de disposer les joueurs selon une structure spatiale en leur permettant d'interagir uniquement avec leurs voisins directs est suffisant pour maintenir un certain niveau de coopération même si le jeu est joué de manière anonyme et sans répétitions. L'étude de Nowak et May, ainsi qu'un nombre substantiel de travaux qui ont suivi, étaient basés sur des structures régulières telles que des grilles à deux dimensions. Axelrod et al. (2002) ont montré qu'en randomisant le choix des voisins, i.e. en abandonnant une localisation géographique stricte, la coopération peut malgré tout émerger, pour autant que les schémas d'interactions restent stables au cours du temps. Ceci est un premier pas en direction d'une structure de réseau social. Toutefois, suite aux travaux précurseurs de sociologues des années soixante, tels que ceux de Milgram (1967), il est devenu clair ces dernières années qu'une grande partie des réseaux d'interactions sociaux et biologiques, et même quelques réseaux technologiques, possèdent des propriétés particulières, et partiellement inattendues, qui les distinguent de graphes réguliers ou aléatoires. Entre autres, ils affichent en général une distribution du degré relativement large ainsi qu'une structure de "petit-monde". Grossièrement parlant, un graphe "petit-monde" est un réseau où tout individu se trouve relativement près de tout autre individu en termes de distance sociale, une propriété également présente dans les graphes aléatoires mais absente des grilles régulières. Par contre, les réseaux "petit-monde" ont, contrairement aux graphes aléatoires, une certaine structure de localité, mesurée par exemple par une quantité appelée le "coefficient de clustering". Dans le même esprit, plusieurs situations réelles de conflit en économie et sociologie ne sont pas bien décrites ni par des positions géographiquement fixes des individus en grilles régulières, ni par des graphes aléatoires. De plus, il est bien connu que la structure même d'un réseau peut passablement influencer des phénomènes dynamiques tels que la manière qu'a une maladie de se répandre à travers une population, ou encore la façon dont des idées ou une information s'y propagent. Ainsi, durant cette dernière décennie, l'attention de la recherche s'est tout naturellement déplacée des graphes aléatoires et réguliers vers de meilleurs modèles de structure d'interactions sociales. L'objectif principal de ce travail est de découvrir si la structure sous-jacente de graphe de vrais réseaux sociaux peut fournir des explications quant aux raisons pour lesquelles on trouve, chez certains groupes d'êtres humains ou d'animaux, des niveaux de coopération supérieurs à ce qui est prescrit par la théorie classique des jeux. Dans l'optique d'atteindre ce but, je commence par étudier un véritable réseau de collaborations scientifiques et, en utilisant diverses mesures statistiques, je mets en évidence la manière dont il diffère de réseaux biologiques ou technologiques. De plus, j'extrais et je décris sa structure de communautés en tenant compte de l'intensité d'une collaboration. Finalement, j'examine l'évolution temporelle du réseau depuis son origine jusqu'à son état en 2006, date à laquelle l'étude a été effectuée, en suggérant également une vue effective du réseau par opposition à une vue historique. Par la suite, je combine la théorie évolutionnaire des jeux avec des réseaux comprenant plusieurs modèles et le réseau de collaboration susmentionné, afin de déterminer les propriétés structurelles utiles à la promotion de la coopération et les mécanismes responsables du maintien de celle-ci. Je mets en évidence le fait que, pour ne pas succomber à la défection, les coopérateurs exploitent dans la mesure du possible l'hétérogénéité des réseaux sociaux en termes de degré ainsi que la structure de communautés sous-jacente de ces mêmes réseaux. Finalement, je montre que le niveau de coopération et sa stabilité dépendent non seulement du jeu joué, mais aussi des règles de la dynamique évolutionnaire utilisées et du calcul du bénéfice d'un individu.

TU Graz: Course: 707.000 Web Science and Web Technology: Lecture 2: Small World Problem

We will discuss several examples and research efforts related to the small world problem and set the ground for our discussion of network theory and social network analysis. Readings: An Experimental Study of the Small World Problem, J. Travers and S. Milgram Sociometry 32 425-443 (1969) [Protected Access] Optional: The Strength of Weak Ties, M.S. Granovetter The American Journal of Sociology 78 1360--1380 (1973) [Protected Access] Optional: Worldwide Buzz: Planetary-Scale Views on an Instant-Messaging Network, J. Leskovec and E. Horvitz MSR-TR-2006-186. Microsoft Research, June 2007. [Web Link, the most recent and comprehensive study on the subject!] Originally from: http://kmi.tugraz.at/staff/markus/courses/SS2008/707.000_web-science/

Evolution and coevolution in mutualistic networks

A major current challenge in evolutionary biology is to understand how networks of interacting species shape the coevolutionary process. We combined a model for trait evolution with data for twenty plant-animal assemblages to explore coevolution in mutualistic networks. The results revealed three fundamental aspects of coevolution in species-rich mutualisms. First, coevolution shapes species traits throughout mutualistic networks by speeding up the overall rate of evolution. Second, coevolution results in higher trait complementarity in interacting partners and trait convergence in species in the same trophic level. Third, convergence is higher in the presence of super-generalists, which are species that interact with multiple groups of species. We predict that worldwide shifts in the occurrence of super-generalists will alter how coevolution shapes webs of interacting species. Introduced species such as honeybees will favour trait convergence in invaded communities, whereas the loss of large frugivores will lead to increased trait dissimilarity in tropical ecosystems.

Sensitivity of complex networks measurements

Complex networks obtained from real-world networks are often characterized by incompleteness and noise, consequences of imperfect sampling as well as artifacts in the acquisition process. Because the characterization, analysis and modeling of complex systems underlain by complex networks are critically affected by the quality and completeness of the respective initial structures, it becomes imperative to devise methodologies for identifying and quantifying the effects of the sampling on the network structure. One way to evaluate these effects is through an analysis of the sensitivity of complex network measurements to perturbations in the topology of the network. In this paper, measurement sensibility is quantified in terms of the relative entropy of the respective distributions. Three particularly important kinds of progressive perturbations to the network are considered, namely, edge suppression, addition and rewiring. The measurements allowing the best balance of stability (smaller sensitivity to perturbations) and discriminability (separation between different network topologies) are identified with respect to each type of perturbation. Such an analysis includes eight different measurements applied on six different complex networks models and three real-world networks. This approach allows one to choose the appropriate measurements in order to obtain accurate results for networks where sampling bias cannot be avoided-a very frequent situation in research on complex networks.

Multiple Pathways Analysis of Brain Functional Networks from EEG Signals: An Application to Real Data

In the present study, we propose a theoretical graph procedure to investigate multiple pathways in brain functional networks. By taking into account all the possible paths consisting of h links between the nodes pairs of the network, we measured the global network redundancy R (h) as the number of parallel paths and the global network permeability P (h) as the probability to get connected. We used this procedure to investigate the structural and dynamical changes in the cortical networks estimated from a dataset of high-resolution EEG signals in a group of spinal cord injured (SCI) patients during the attempt of foot movement. In the light of a statistical contrast with a healthy population, the permeability index P (h) of the SCI networks increased significantly (P < 0.01) in the Theta frequency band (3-6 Hz) for distances h ranging from 2 to 4. On the contrary, no significant differences were found between the two populations for the redundancy index R (h) . The most significant changes in the brain functional network of SCI patients occurred mainly in the lower spectral contents. These changes were related to an improved propagation of communication between the closest cortical areas rather than to a different level of redundancy. This evidence strengthens the hypothesis of the need for a higher functional interaction among the closest ROIs as a mechanism to compensate the lack of feedback from the peripheral nerves to the sensomotor areas.

Estimating complex cortical networks via surface recordings-A critical note

We discuss potential caveats when estimating topologies of 3D brain networks from surface recordings. It is virtually impossible to record activity from all single neurons in the brain and one has to rely on techniques that measure average activity at sparsely located (non-invasive) recording sites Effects of this spatial sampling in relation to structural network measures like centrality and assortativity were analyzed using multivariate classifiers A simplified model of 3D brain connectivity incorporating both short- and long-range connections served for testing. To mimic M/EEG recordings we sampled this model via non-overlapping regions and weighted nodes and connections according to their proximity to the recording sites We used various complex network models for reference and tried to classify sampled versions of the ""brain-like"" network as one of these archetypes It was found that sampled networks may substantially deviate in topology from the respective original networks for small sample sizes For experimental studies this may imply that surface recordings can yield network structures that might not agree with its generating 3D network. (C) 2010 Elsevier Inc All rights reserved

Secure Full-Duplex Small-Cell Networks in a Spectrum Sharing Environment

In this paper, we propose three relay selection schemes for full-duplex heterogeneous networks in the presence of multiple cognitive radio eavesdroppers. In this setup, the cognitive small-cell nodes (secondary network) can share the spectrum licensed to the macro-cell system (primary network) on the condition that the quality-of-service of the primary network is always satisfied subjected to its outage probability constraint. The messages are delivered from one small-cell base station to the destination with the help of full-duplex small-cell base stations, which act as relay nodes. Based on the availability of the network’s channel state information at the secondary information source, three different selection criteria for full-duplex relays, namely: 1) partial relay selection; 2) optimal relay selection; and 3) minimal self-interference relay selection, are proposed. We derive the exact closed-form and asymptotic expressions of the secrecy outage probability for the three criteria under the attack of non-colluding/colluding eavesdroppers. We demonstrate that the optimal relay selection scheme outperforms the partial relay selection and minimal self-interference relay selection schemes at the expense of acquiring full channel state information knowledge. In addition, increasing the number of the full-duplex small-cell base stations can improve the security performance. At the illegitimate side, deploying colluding eavesdroppers and increasing the number of eavesdroppers put the confidential information at a greater risk. Besides, the transmit power and the desire outage probability of the primary network have great influences on the secrecy outage probability of the secondary network. 

Neurodynamics of an election

Variables influencing decision-making in real settings, as in the case of voting decisions, are uncontrollable and in many times even unknown to the experimenter. In this case, the experimenter has to study the intention to decide (vote) as close as possible in time to the moment of the real decision (election day). Here, we investigated the brain activity associated with the voting intention declared 1 week before the election day of the Brazilian Firearms Control Referendum about prohibiting the commerce of firearms. Two alliances arose in the Congress to run the campaigns for YES (for the prohibition of firearm commerce) and NO (against the prohibition of firearm commerce) voting. Time constraints imposed by the necessity of studying a reasonable number (here, 32) of voters during a very short time (5 days) made the EEG the tool of choice for recording the brain activity associated with voting decision. Recent fMRI and EEG studies have shown decision-making as a process due to the enrollment of defined neuronal networks. In this work, a special EEG technique is applied to study the topology of the voting decision-making networks and is compared to the results of standard ERP procedures. The results show that voting decision-making enrolled networks in charge of calculating the benefits and risks of the decision of prohibiting or allowing firearm commerce and that the topology of such networks was vote-(i.e., YES/NO-) sensitive. (C) 2010 Elsevier B.V. All rights reserved.

Puzzling challenges in contemporary neuroscience: Insights from complexity and emergence in epileptogenic circuits

The brain is a complex system that, in the normal condition, has emergent properties like those associated with activity-dependent plasticity in learning and memory, and in pathological situations, manifests abnormal long-term phenomena like the epilepsies. Data from our laboratory and from the literature were classified qualitatively as sources of complexity and emergent properties from behavior to electrophysiological, cellular, molecular, and computational levels. We used such models as brainstem-dependent acute audiogenic seizures and forebrain-dependent kindled audiogenic seizures. Additionally we used chemical OF electrical experimental models of temporal lobe epilepsy that induce status epilepticus with behavioral, anatomical, and molecular sequelae such as spontaneous recurrent seizures and long-term plastic changes. Current Computational neuroscience tools will help the interpretation. storage, and sharing of the exponential growth of information derived from those studies. These strategies are considered solutions to deal with the complexity of brain pathologies such as the epilepsies. (C) 2008 Elsevier Inc. All rights reserved.

Non-coding RNAs: the architects of eukaryotic complexity

Around 98% of all transcriptional output in humans is noncoding RNA. RNA-mediated gene regulation is widespread in higher eukaryotes and complex genetic phenomena like RNA interference, co-suppression, transgene silencing, imprinting, methylation, and possibly position-effect variegation and transvection, all involve intersecting pathways based on or connected to RNA signaling. I suggest that the central dogma is incomplete, and that intronic and other non-coding RNAs have evolved to comprise a second tier of gene expression in eukaryotes, which enables the integration and networking of complex suites of gene activity. Although proteins are the fundamental effectors of cellular function, the basis of eukaryotic complexity and phenotypic variation may lie primarily in a control architecture composed of a highly parallel system of trans-acting RNAs that relay state information required for the coordination and modulation of gene expression, via chromatin remodeling, RNA-DNA, RNA-RNA and RNA-protein interactions. This system has interesting and perhaps informative analogies with small world networks and dataflow computing.

A game-theoretic network formation model

We study the dynamics of a game-theoretic network formation model that yields large-scale small-world networks. So far, mostly stochastic frameworks have been utilized to explain the emergence of these networks. On the other hand, it is natural to seek for game-theoretic network formation models in which links are formed due to strategic behaviors of individuals, rather than based on probabilities. Inspired by Even-Dar and Kearns (2007), we consider a more realistic model in which the cost of establishing each link is dynamically determined during the course of the game. Moreover, players are allowed to put transfer payments on the formation of links. Also, they must pay a maintenance cost to sustain their direct links during the game. We show that there is a small diameter of at most 4 in the general set of equilibrium networks in our model. Unlike earlier model, not only the existence of equilibrium networks is guaranteed in our model, but also these networks coincide with the outcomes of pairwise Nash equilibrium in network formation. Furthermore, we provide a network formation simulation that generates small-world networks. We also analyze the impact of locating players in a hierarchical structure by constructing a strategic model, where a complete b-ary tree is the seed network.

Periodic Reordering

For many networks in nature, science and technology, it is possible to order the nodes so that most links are short-range, connecting near-neighbours, and relatively few long-range links, or shortcuts, are present. Given a network as a set of observed links (interactions), the task of finding an ordering of the nodes that reveals such a range-dependent structure is closely related to some sparse matrix reordering problems arising in scientific computation. The spectral, or Fiedler vector, approach for sparse matrix reordering has successfully been applied to biological data sets, revealing useful structures and subpatterns. In this work we argue that a periodic analogue of the standard reordering task is also highly relevant. Here, rather than encouraging nonzeros only to lie close to the diagonal of a suitably ordered adjacency matrix, we also allow them to inhabit the off-diagonal corners. Indeed, for the classic small-world model of Watts & Strogatz (1998, Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442) this type of periodic structure is inherent. We therefore devise and test a new spectral algorithm for periodic reordering. By generalizing the range-dependent random graph class of Grindrod (2002, Range-dependent random graphs and their application to modeling large small-world proteome datasets. Phys. Rev. E, 66, 066702-1–066702-7) to the periodic case, we can also construct a computable likelihood ratio that suggests whether a given network is inherently linear or periodic. Tests on synthetic data show that the new algorithm can detect periodic structure, even in the presence of noise. Further experiments on real biological data sets then show that some networks are better regarded as periodic than linear. Hence, we find both qualitative (reordered networks plots) and quantitative (likelihood ratios) evidence of periodicity in biological networks.

Modeling connectivity in terms of network activity

A new complex network model is proposed which is founded on growth, with new connections being established proportionally to the current dynamical activity of each node, which can be understood as a generalization of the Barabasi-Albert static model. By using several topological measurements, as well as optimal multivariate methods (canonical analysis and maximum likelihood decision), we show that this new model provides, among several other theoretical kinds of networks including Watts-Strogatz small-world networks, the greatest compatibility with three real-world cortical networks.

Física estatística aplicada a sistemas sociais através do estudo de redes complexas

In this work a study of social networks based on analysis of family names is presented. A basic approach to the mathematical formalism of graphs is developed and then main theoretical models for complex networks are presented aiming to support the analysis of surnames networks models. These, in turn, are worked so as to be drawn leading quantities, such as aggregation coefficient, minimum average path length and connectivity distribution. Based on these quantities, it can be stated that surnames networks are an example of complex network, showing important features such as preferential attachment and small-world character