Statistical physics of coevolving networks

Fizyka statystyczna stworzyła fundamenty potrzebne do analizy układów składających się z dużej liczby elementów. W jej ramach udowodniono, że problemy, które pozornie wydają się niemożliwe do opisania w sposób ilościowy, można badać w sposób ścisły. Najważniejszym krokiem w tej przemianie była zmiana podejścia do predykcji – z opisu deterministycznego do stochastycznego. Narzędzia stworzone w ramach fizyki statystycznej stosowane były następnie w wielu innych dziedzinach nauki, z których w kontekście niniejszej rozprawy najważniejsza jest nauka o układach złożonych. W centrum nauki o układach złożonych leżą sieci. W przypadku, gdy przedmiot badań składa się z wielu elementów, których interakcje nie są oczywiste, sieci są naturalnym wyborem do jego opisu. Niedawne publikacje wręcz identyfikują układy złożone z koewoluującymi sieciami wielowarstwowymi. Można dyskutować z tak wąską definicją, jednak koewolucja struktury sieci oraz stanu wierzchołków z całą pewnością jest jedną z kluczowych własności układów złożonych. Badania nad wpływem koewolucji na zachowanie poszczególnych modeli są stosunkowo młode. Co więcej, spójna teoria sieci koewoluujących jest jak do tej pory nieosiągalna. Aby poznać uniwersalne prawa, najpierw należy zrozumieć pojedyncze problemy. Zgodnie z tą ideą, niniejsza rozprawa bada koewolucję w różnych modelach sieciowych, tak analitycznych (czy równowagowych), jak i algorytmicznych (czy nierównowagowych). W szczególności, w rozprawie badane są efekty generowane przez uwzględnienie kewolucji w trzech modelach: modelu wyborcy, modelu Axelroda oraz modelu Isinga. Pierwszy z nich jest klasycznym modelem stosowanym w ilościowym opisie systemów społecznych, choć był również stosowany w fizyce, biologii, czy finansach. Model wyborcy jest rozszerzony w rozprawie o koewolucję, domykanie trójkątów, nieliniowe interakcje oraz szum. Model Axelroda ma czysto socjologiczną interpretację – jest to model interakcji społecznych, lub rozprzestrzeniania się kultury. W rozprawie badany jest wpływ różnych rodzajów przełączania krawędzi na końcową topologię sieci. Otrzymane wyniki są porównane z danymi empirycznymi opracowanymi w ramach niniejszej rozprawy. Model Axelroda został poprawiony tak, aby opisać skalowanie obserwowane doświadczalnie. Warto zaznaczyć, iż wcześniej proponowane rozszerzenia modelu nie rozwiązały problemu sprzeczności z danymi. Model Isinga pierwotnie został skonstruowany w celu wyjaśnienia zjawiska ferromagnetyzmu. Zdobył on jednak dużo więcej uwagi niż by na to wskazywało pierwsze zastosowanie. Stał się on punktem odniesienia dla wielu modeli sieciowych i był badany w wielu wariantach – nie tylko motywowanych empirycznie, ale również teoretycznie atrakcyjnych. Model jest rozwinięty w niniejszej rozprawie w tym właśnie abstrakcyjnym kontekście. Dynamika spinów z modelu Isinga jest połączona z cechami topologicznymi wierzchołków w celu zbadania zachowania modelu równowagowego z własnościami topologicznymi uwzględnionymi w hamiltonianie. We wszystkich badanych modelach otrzymane zostały nowe wyniki. W nieliniowym koewoluującym modelu wyborcy została zaobserwowana nowa faza rozbita, a także wysokie wartości współczynnika gronowania. Po dodaniu szumu do modelu otrzymane zostały dwie nowe fazy o interesujących własnościach. Pierwsza faza istnieje w granicy termodynamicznej, druga zaś zawiera klastry topologiczne generowane przez stany wierzchołków, co nie zostało do tej pory zaobserwowane w koewoluującym modelu wyborcy z szumem. Dodatkowo wyprowadzony został nowy opis analityczny modelu. Jako że model ten jest uogólnieniem poprzednio badanych modeli, opis analityczny obejmuje również przypadki graniczne. Również w modelu Axelroda osiągnięto wysokie wartości współczynnika gronowania, a także potęgowy rozkład stopnia wierzchołków. Przede wszystkim jednak, dzięki zastosowanym modyfikacjom model przejawia nowe skalowanie liczby domen ze wzrostem sieci. To nowe skalowanie, w przeciwieństwie do oryginalnego modelu, jest zgodne z danymi empirycznymi. W rozprawie zaproponowany został także model równowagowy sieci koewoluujących. Hamiltonian modelu zawiera nie tylko stany wierzchołków i ich interakcje, ale również ich stopnie jako lokalne cechy topologiczne. Bogaty diagram fazowy otrzymany w ten sposób jest dodatkowo opisany analitycznie. Konfiguracje obserwowane w modelu częściowo pokrywają się z konfiguracjami z modeli nierównowagowych, sugerując możliwość opisania ich w podejściu równowagowym. Wyniki otrzymane w ramach niniejszej rozprawy rzucają nowe światło na modele sieci koewoluujących i ich analizę przy użyciu metod fizyki statystycznej. Teoria układów złożonych nie jest jeszcze kompletna, a kolejne cegły są wciąż kładzione pod jej fundamenty. Być może bardziej ogólna teoria zostanie odkryta po zrozumieniu wystarczającej liczby oddzielnych zjawisk. Zawartość niniejszej rozprawy przyczynia się do powstania takiej teorii dostarczając kolejnych cegieł. Główną z nich są badania nad koewolucją stanu wierzchołków i topologii sieci, jako jedną z kluczowych własności układów złożonych. Otrzymane wyniki nie tylko reprezentują postęp w badaniach nad poszczególnym modelami, ale także mogą być postrzegane jako kolejny krok w kierunku teorii układów złożonych.

Statistical physics has introduced key concepts for analyzing systems consisting of a large number of elements. It showed that problems seemingly out of reach for quantitative description can be actually treated in a strict manner. The essential achievement was a shift in the notion of prediction from deterministic to stochastic ground. The approach of statistical physics has been successfully applied in numerous branches of science, of which the most important one for this thesis is the theory of complex systems. Networks create the core of complexity science. When a studied object contains many interacting parts and the pattern of interaction is not trivial, networks are the most natural tool to describe it. Some recent publications even identify complex systems as coevolving multilayer networks. One can argue with such a rigorous definition, but the coevolution of structure and state on its own has proved to be a crucial feature in complex systems. Studies on the coevolution's impact on the behavior of particular models are relatively new. Moreover, a general theory of coevolving networks is so far out of reach. In order to get closer to universal laws we need to understand single problems first. Thus, I seek to explore the effects of coevolution in different models, both analytic (or equilibrium) and algorithmic (or non-equilibrium) ones. The thesis explores outcomes of introducing coevolving mechanisms in three models, namely the voter model, the Axelrod model and the Ising model. The first one is a reference point in the quantitative description of social systems, however it was successfully applied also in physics, biology, and finance. The voter model is extended in this work to integrate coevolution, triadic closure, nonlinear interactions, and noise. The Axelrod model has a purely social interpretation – it's a model of social interactions or dissemination of culture. It is studied in the thesis how different types of rewiring, during the coevolution of the network's structure and state of the nodes, influence the final topology of the system. Results obtained using the Axelrod model are compared with empirical data. The model was improved for better agreement with the empirically observed scaling behavior. Notably, previous extensions of the model didn't resolve the contradiction with the empirical data, which is solved here. The Ising model was originally constructed to explain ferromagnetism. However, it gained much bigger attention than the first application might have suggested. It became a reference point for network models and has been studied in many variations, not only empirically implied but also theoretically thrilling. In this abstract context, the spin dynamics from the Ising model is combined in the thesis with topological traits of the nodes to analyze the outcome of a coevolving equilibrium model with structural traits included in the Hamiltonian. In all models studied throughout this thesis new results are obtained. The most important ones are the following. In the nonlinear coevolving voter model with triadic closure a new shattered phase is observed together with high values of the clustering coefficient. When the noise is included two new phases are obtained. One of these phases persists in the thermodynamic limit. The other one contains topological communities driven by state of the nodes, what was not observed before for the coevolving voter model with noise. Additionally, a new analytical description of the model is proposed. As this model is the most general one, it contains previously studied limit cases like the coevolving voter model or the nonlinear coevolving voter model. Similarly, in the Axelrod model high clustering is generated, as well as a power-law degree distribution. But most importantly, due to the implemented changes the model displays a new scaling of the number of domains with the system size. This result, in contrast to results obtained with the original model, is consistent with empirical data. Finally, an equilibrium model of coevolving networks is proposed for the first time. More precisely, the Hamiltonian of the model includes not only states of the nodes and their mutual interactions, but also degree of the nodes, as a local topological trait. A rich phase diagram obtained in this way is described analytically. The observed configurations coincide with those obtained in non-equilibrium models, suggesting a possibility of their equilibrium description. The results of the thesis provide a new insight into the behavior of coevolving networks from a statistical physics perspective. The theory of complex systems is not yet complete and new building blocks are being discovered. Hopefully, after analyzing and understanding enough separate parts a more universal theory will emerge. The content of this thesis contributes to the development of such theory by providing several new building blocks. Above all, these blocks take into account coevolution of network's structure and state, as one of the crucial properties of complex systems is their adaptive behavior. The obtained results surely represent advancement in particular models that were studied within the scope of the thesis, but can be also seen as another step towards the theory of complex systems.