Labelled Graph Strategic Rewriting for Social Networks

Maribel Fernández (1) , Hélène Kirchner (2) , Bruno Pinaud (3, 4) , Jason Vallet (3, 4)

1 King‘s College London
2 Inria Siège
3 LaBRI - Laboratoire Bordelais de Recherche en Informatique
4 UB - Université de Bordeaux

We develop an algebraic approach, based on labelled-graph strategic rewriting , for the study of social networks, specifically network generation and propagation mechanisms. This approach sheds a new light on these problems, and leads to new or improved generation and propagation algorithms. We argue that relevant concepts are provided by three ingredients: labelled graphs to represent networks of data or users, rewrite rules to describe concurrent local transformations, and strategies to express control. We show how these techniques can be used to generate random networks that are suitable for social network analysis, simulate different propagation mechanisms, and analyse and compare propagation models by extracting common rules and differences, thus leading to improved algorithms. We illustrate with examples the flexibility of the approach.

Mots clés: Labelled port graph; graph rewriting; strategies; strategic rewrite programs; social networks; generation; propagation

Domaines: Informatique [cs]

Maribel Fernández, Hélène Kirchner, Bruno Pinaud, Jason Vallet. Labelled Graph Strategic Rewriting for Social Networks. [Research Report] Université de bordeaux; Inria; King's College London. 2016. ⟨hal-01429893⟩