Evolutionary dynamics on evolving graphs

At the core of any system of interacting entities lie evolution, its driving force of change, and a graph, encoding its structure. In this thesis we investigate how the former affects the latter, and vice versa, whereby we resort to the tools of evolutionary game theory, population dynamics, and graph theory. We begin our journey by considering evolutionary dynamics as they unfold in the absence of population structure from a deterministic and stochastic point of view, then steer to the realm of static graphs endowed with evolutionary games subject to a host of imitation processes, and, at last, stop for a while to leverage the knowledge acquired along the way to develop the modified Petford--Welsh algorithm, a highly scalable decentralised heuristic approach to cluster detection. Picking up where we left off, we then expound on more elaborate forms of imitation dynamics by paying a visit to a plethora of models of contagion, cascade, and consensus dynamics. Soon thereafter, we leave behind the world of simple graphs, enter the domain of multilayer and evolving graphs, and examine how they co-evolve with the evolutionary processes pertaining to them. Finally, we reach our destination, where we put to use the theory that we have become acquainted with to devise a model of the flow of the news across a co-evolving graph comprised of a layer of news providers and a layer of news consumers. V središču vsakega sistema entitet v interakciji se nahajata graf, ki ponazarja njegovo strukturo, in evolucija kot gonilna sila sprememb. V tem delu raziskujemo, kakšen je njun medsebojni vpliv, pri čemer posežemo po orodjih evolucijske teorije iger, populacijske dinamike in teorije grafov. Najprej si z determinističnega in s stohastičnega vidika ogledamo, kako se evolucijska dinamika odvija, kadar populacije niso strukturirane, tik za tem v zgodbo vključimo statične grafe, podvržene evolucijskim igram in raznim procesom imitacije, in ob koncu poglavja spotoma pridobljeno znanje vpletemo v razvoj prirejenega Petford--Welshevega algoritma, decentraliziranega hevrističnega pristopa k odkrivanju gruč, ki se zlahka spopade z rastočo količino podatkov. Nato obrnemo novo stran in preidemo na bolj zapletene oblike imitacijske dinamike, pri čemer pod drobnogled vzamemo cel nabor modelov dinamike okužbe, kaskad in soglasja. Kaj kmalu opustimo obravnavo statičnih grafov in se posvetimo večplastnim in razvijajočim se grafom, kjer preučujemo njihov sorazvoj z evolucijskimi procesi, ki so jim podrejeni. Pripoved nazadnje sklenemo tako, da z uporabo teorije, s katero smo se seznanili, ustvarimo model pretoka novic po večplastnem grafu -- s plastjo ponudnikov novic in plastjo njihove publike -- ki se spreminja sočasno s potekom dinamike.