Labelled Graph Rewriting Meets 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 UB - Université de Bordeaux
4 LaBRI - Laboratoire Bordelais de Recherche en Informatique

The intense development of computing techniques and the increasing volumes of produced data raise many modelling and analysis challenges. There is a need to represent and analyse information that is: complex –due to the presence of massive and highly heterogeneous data–, dynamic –due to interactions, time, external and internal evolutions–, connected and distributed in networks. We argue in this work that relevant concepts to address these challenges are provided by three ingredients: labelled graphs to represent networks of data or objects; rewrite rules to deal with concurrent local transformations; strategies to express control versus autonomy and to focus on points of interests. To illustrate the use of these concepts, we choose to focus our interest on social networks analysis, and more precisely in this paper on random network generation. Labelled graph strategic rewriting provides a formalism in which different models can be generated and compared. Conversely, the study of social networks, with their size and complexity, stimulates the search for structure and efficiency in graph rewriting. It also motivated the design of new or more general kinds of graphs, rules and strategies (for instance, to define positions in graphs), which are illustrated here. This opens the way to further theoretical and practical questions for the rewriting community.

Domaines: Logique en informatique [cs.LO]

Maribel Fernández, Hélène Kirchner, Bruno Pinaud, Jason Vallet. Labelled Graph Rewriting Meets Social Networks. Rewriting Logic and Its Applications, WRLA 2016, Apr 2016, Eindhoven, Netherlands. pp.1--25, ⟨10.1007/978-3-319-44802-2_1⟩. ⟨hal-01347355⟩