Modelling Adaptive Networks: The Case of the Petrified Voters

Abstract

Adaptive networks are characterised by mutual dependencies between nodes' local state changes and evolving topology. Stochastic graph transformation systems are ideally suited to model such networks, but in order to analyse their  properties we require more scalable methods. %We present a case study of a simple but representative example of adaptive networks. In this social network of opinionated voters a node connected to another of different opinion will either convert (changing state) or disconnect and establish a new connection with a node of the same opinion (changing topology). 
To analyse quantitative properties of the model, such as the long-term average ratio of edges connecting nodes of different opinions or the overall rate of change of opinions or connections, we use a refinement technique developed for the Kappa graph rewriting approach to derive a stochastic Petri net, replacing graphs as states by markings representing the frequency of occurrences of certain patterns. In general the number of patterns (and therefore places) is unbounded, but approximations can be used to replace complex patterns by combinations of simpler ones.