Rigid Graphs for Adaptive Networks

Networks with dynamically changing topology can be modelled using rule-based graph transformations. If we are interested in the relative timing of different kinds of change, stochastic models are required adding rate constants to rules controlling their delay once a match has become available. A challenging case are adaptive networks where structural changes and updates of local states are interdependent.

Models for such networks are hard to construct and analyse. Refinements help produce models at the right level of abstraction and enable analysis by mapping to other formalisms. Rigidity is a property of graphs introduced in Kappa to support stochastic refinement, allowing to preserve the number of matches for rules in the refined system.

In this talk we 1)  propose a notion of rigidity in an axiomatic setting based on adhesive categories; 2) show how the rewriting of rigid structures can be defined systematically by requiring matches to be open maps reflecting certain structures; and 3)  obtain in our setting a notion of refinement which generalises that in Kappa, and allows a rule to be partitioned into a set of rules which are collectively equivalent to the original. 

We illustrate our approach on an example of a social network with dynamic topology and discuss how both simple typed graphs and attributed graphs, allowing the representation of complex data states, emerge as instances of the categorical framework.

Joint work with Vincent Danos and Pawel Sobocinski.