Characterization of self-organization processes in complex networks

Abstract

A estrutura de interações sociais numa população é muitas vezes modelada através de uma rede complexa que representa os indivíduos e respetivas relações sociais. Estas estruturas são conhecidas por afetarem de forma fundamental os processos dinâmicos que suportam. A caracterização desse efeito é, no entanto, uma tarefa complicada pois o tratamento matemático destes sistemas requer o estudo de um espaço de estados de grande dimensão, limitando a aplicabilidade de abordagens analíticas e numéricas. Esta tese teve como objetivo desenvolver métodos, inspirados na Física Estatística dos Sistemas Fora do Equilíbrio, com o fim de caracterizar processos dinâmicos em redes complexas. Nesta tese demonstramos que a estrutura de uma população naturalmente induz a emergência de padrões de correlações entre indivíduos que partilham traços semelhantes, um fenómeno também identificado em estudos empíricos. Estes padrões de correlações são independentes do tipo de processo dinâmico considerado, do tipo de informação que se propaga sendo observados numa classe alargada de redes complexas. Mostramos também que propriedades como o clustering e a densidade de ligações da rede têm um papel fundamental nos padrões de correlações emergentes. Outra questão fundamental diz respeito à relação entre as dinâmicas local e a global em redes sociais. De facto, as redes sociais afetam de forma tão fundamental os processos dinâmicos que suportam que em muitas situações o comportamento coletivo observado não tem qualquer relação aparente com a dinâmica local na sua génese. Este é um problema comum a muitos sistemas complexos e tipicamente associado a fenómenos emergentes e de auto-organização. Neste trabalho esta questão é explorada no contexto do problema da Cooperação e no âmbito da Teoria de Jogos Evolutiva. Para esse fim introduzimos uma quantidade que é estimada numericamente e a que damos o nome de Average Gradient of Selection (AGOS). Esta quantidade, relaciona de forma efetiva as dinâmicas local e global, possibilitando a descrição do processo de auto-organização em populações estruturadas. Através do AGOS mostramos que quando as interações entre indivíduos são descritas através do Dilema do Prisioneiro, uma metáfora popular no estudo da cooperação, a dinâmica coletiva emergente é sensível à forma da rede de interações entre os indivíduos. Em particular, demonstramos que quando a rede é homogénea (heterogénea) no que respeita à distribuição de grau o Dilema do Prisioneiro é transformado numa dinâmica coletiva de coexistência (coordenação). Mostramos ainda que esta transformação depende da pressão de seleção (associada ao grau de determinismo no processo de decisão dos indivíduos) e de taxa de mutações (a adoção espontânea de um novo comportamento por parte de um individuo) consideradas. A relação entre estas duas varáveis pode também resultar em alterações de regimes dinâmicos cujo o resultado pode, em casos particulares, resultar no desfecho drástico para a evolução da cooperação. Finalmente, fazemos uso do AGOS para caracterizar a dinâmica evolutiva da cooperação no caso em que a estrutura co-evolve. Demonstramos que na presença de uma estrutura social a dinâmica global é semelhante à de um jogo de coordenação entre N-pessoas, cujas características dependem de forma sensível das escalas de tempo relativas entre a evolução de comportamentos e a evolução da estrutura. Uma vez mais, a dinâmica global emergente contrasta com o Dilema do Prisioneiro que caracteriza as interações locais entre os indivíduos. Acreditamos que o AGOS, que pode ser facilmente aplicado no estudo de outros processos dinâmicos, proporciona uma contribuição significativa para o melhor entendimento de Sistemas Complexos, em particular aqueles em que as interações entre os elementos constituintes são bem definidos através uma rede complexa.

The structure of social interactions in a population is often modeled by means of a complex network representing individuals and their social ties. These structures are known to fundamentally impact the processes they support. However, the characterization of how structure impacts a dynamical process is by no means an easy task. Indeed, the large configuration space spanned tends to limit the systematic applicability of numerical methods, while analytical treatments have failed to provide a good description of the system dynamics. The aim of this thesis was to develop methods inspired in the Statistical Physics of Systems far from equilibrium to characterize dynamical processes on complex networks. In this thesis we show how the structure of a population naturally induces the emergence of correlations between individuals that share similar traits, which is in accordance empirical evidence. These, so called, ’peer-influence” correlation patterns are independent of the type of dynamical process under consideration, the type of information being spread while being ubiquitous among a wide variety of network topologies. We have also find evidence that central to the ’peer-influence” patterns are topological features such as the clustering and the sparsity of the underlying network of interactions. Another fundamental problem concerns the relationship between local and global dynamics in social networks. Indeed, social networks affect in such a fundamental way the dynamics of the population they support that the collective, population-wide behavior that one observes often bears no relation to the individual processes it stems from. This is in fact a common problem among many Complex Systems typically associated with self-organization and emerging phenomena. Here we study this issue in the context of the problem of Cooperation and in the realm of Evolutionary Game Theory. To that end we introduce a numerically estimated mean-field quantity that we call the Average Gradient of Selection (AGOS). This quantity is able to effectively connect the local and global dynamics, providing a way to track the self-organization of cooperators and defectors in networked populations. With the AGOS we show that when individuals engage in a Prisoner’s Dilemma, a popular cooperation metaphor, the emerging collective dynamics depends on the shape of the underlying network of interactions. In particular, we show that degree homogeneous (heterogeneous) networks the Prisoner’s Dilemma is transformed into a collective coexistence (coordination) dynamics, contrasting with the defector dominance of the local dynamics. We further show that the extent to which these emergent phenomena are observed in structured populations is conditional on the selection pressure (the uncertainty associated with the decision making) and the rate of mutations (the spontaneously adoption of new behaviors by individuals) under consideration. Interestingly, the interplay between selection pressure and mutation rates can lead to drastic regime shifts in the evolution of cooperation. Finally, we make use of the AGOS to characterize the evolutionary dynamics of cooperation in the case of a co-evolving social structure. We demonstrate that in an adaptive social structure the population-wide dynamics resembles that of a N-person coordination game, whose characteristics depend sensitively on the relative time-scales between behavioral and network co-evolution. Once more, the resulting collective dynamics contrasts with the two-person Prisoner’s Dilemma that characterizes how individuals interact locally. We argue that the AGOS, which can be readily applied to other dynamical contexts and processes, provides a significant contribution to a better understanding of Complex Systems involving populations in which who interacts with whom is well-defined by a complex network.