Maribel Fernández
email: maribel.fernandez@kcl.ac.uk

Hélène Kirchner
email: helene.kirchner@inria.fr

Bruno Pinaud
email: bpinaud@labri.fr

Jason Vallet
email: jvallet@labri.fr

Labelled Graph Rewriting Meets Social Networks

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.

Introduction

With the intense development of computing techniques, the last decades have seen an increasing complexity of models needed to study phenomena of the physical world and, at the same time, increasing volumes of data produced by observations and computations. New paradigms of data science and data exploration have emerged and opened the way to analytic approaches, such as data-driven algorithms, analysis and mining (also called data analytics). Social and human sciences are also impacted by this evolution and provide interesting research problems for computer scientists. To illustrate these concepts, we choose to focus our interest on social networks, which have been intensively studied in the last years [START_REF] Carrington | Models and Methods in Social Network Analysis[END_REF][START_REF] Newman | The structure and dynamics of networks[END_REF][START_REF] Scott | The SAGE Handbook of Social Network Analysis[END_REF]. The analysis of social networks, used to represent users and their relations with one another, raises several questions concerning their possible construction and evolutions. Among these questions, the study of network propagation phenomena has initiated a sustained interest in the research community, offering applications in various domains, ranging from sociology [START_REF] Granovetter | Threshold models of collective behavior[END_REF] to epidemiology [START_REF] Bertuzzo | On spatially explicit models of cholera epidemics[END_REF][START_REF] Dodds | A generalized model of social and biological contagion[END_REF] or even viral marketing and product placement [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF]. To solve these problems we need to model and analyse systems that are complex, since they involve data that are massive and highly heterogeneous, dynamic, due to interactions, time, external or internal evolutions, connected and distributed in networks.

We argue in this paper that relevant concepts to address these challenges are: Labelled Graphs to represent networks of data or objects, Rules to deal with concurrent local transformations, and Strategies to express control versus autonomy and to focus on points of interests. Indeed, modelling social networks raises many questions we have to address. First, large networks are involved for which an efficient search of patterns is needed, along with capability of focusing on points of interest and defining appropriate views. Since data are often corrupted or imprecise, one should also deal with uncertainty, which implies that we need to address probabilistic or stochastic issues in the models. The dynamic evolution of data is generally modelled by simple transformations, applied in parallel and triggered by events or time. However, such models should also take into account controlled versus autonomous behaviour. Modelling may reveal conflicts that have to be detected (for instance through overlapping rules) and solved (using precedence, choices, i.e., strategic issues). Memory and backtracking must be provided, through notions of computation history or traces. Last but not least, visualisation is important at all levels: for data analysis, program engineering, program debugging, tests and verification (for instance to provide proof intuition).

In [START_REF] Vallet | A visual analytics approach to compare propagation models in social networks[END_REF], we focused on propagation phenomena and showed how some popular models can be expressed using labelled graph and rewriting. In the current paper, we use this previous work to illustrate our computing model and introduce a generative model for social networks. Indeed, many data sets, extracted from various social networks, are publicly available. 4 However, in order to demonstrate the generality of a new approach, or to design and experiment with stochastic algorithms on a sufficiently large sample of network topologies, it is more convenient to use randomly generated networks. Several generative models of random networks are available to work with (e.g., [START_REF] Barabási | Emergence of scaling in random networks[END_REF][START_REF] Batagelj | Efficient generation of large random networks[END_REF][START_REF] Erdős | On the evolution of random graphs[END_REF][START_REF] Wang | Random pseudofractal scale-free networks with small-world effect[END_REF]). Some, like the Erdös-Rényi (ER) model [START_REF] Erdős | On the evolution of random graphs[END_REF], do not guarantee any specific property regarding their final topology, whereas others can be characterised as small-world or scalefree networks. This paper shows how to generate such models using labelled graphs, rules and strategies.

Port graph rewriting systems have been used to model systems in a wide variety of domains, such as biochemistry, interaction nets, games or social networks (e.g., [START_REF] Andrei | PORGY: Strategy-Driven Interactive Transformation of Graphs[END_REF][START_REF] Fernández | A strategy language for graph rewriting[END_REF][START_REF] Fernández | Strategic port graph rewriting: An interactive modelling and analysis framework[END_REF][START_REF] Vallet | A visual analytics approach to compare propagation models in social networks[END_REF]). In the following, we reuse from [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF] the formal definitions of port graphs with attributes, rewrite rule and rewriting step, the concept of strategic graph program, as well as the definition of the strategy language and its operational semantics, and enrich them in order to achieve a more complete and generic definition. Most notably, the refined definitions permit the use of oriented edges and conditional existence matching, reminiscent of similar solutions found in Elan [START_REF] Borovanský | An overview of ELAN[END_REF] and GP [START_REF] Plump | The Graph Programming Language GP[END_REF]. We use the Porgy environment which supports interactive modelling using port graph rewriting; more details concerning the rewriting platform can be found in [START_REF] Pinaud | PORGY: A Visual Graph Rewriting Environment for Complex Systems[END_REF].

Summarising, our contributions are twofold: we present a general modelling framework, based on strategic port graph rewriting, that facilitates the analysis of complex systems, and we illustrate its power by focusing on social networks (more precisely, their generation). For this application, the visual high-level modelling features of port graph rewriting are particularly relevant. Concepts of port graphs, rules and strategies are illustrated on this specific domain. Conversely, the study of social networks, with their size and complexity, stimulates the search for structure and efficiency in graph rewriting. We identify open problems and questions that arise when studying social networks.

The paper is organised as follows. Section 2 introduces the modelling concepts we propose to use: port graphs, morphism, rewriting, derivation tree, strategy and strategic graph programs are defined in their full generality, while illustrated on the special case of social networks. In Section 3, we focus on social network behaviour simulation, more precisely on social network generation. In Section 4, we conclude by synthesising the lessons learned from this study and giving perspectives for future work.

Labelled Graph Rewriting

Several definitions of graph rewriting are available, using different kinds of graphs and rewrite rules (see, for instance, [START_REF] Barendregt | Term graph rewriting[END_REF][START_REF] Barthelmann | How to construct a hyperedge replacement system for a context-free set of hypergraphs[END_REF][START_REF] Corradini | Algebraic approaches to graph transformation -part i: Basic concepts and double pushout approach[END_REF][START_REF] Habel | Double-pushout graph transformation revisited[END_REF][START_REF] Lafont | Interaction nets[END_REF][START_REF] Plump | Term graph rewriting[END_REF]). In this paper we consider port graphs with attributes associated with nodes, ports and edges, generalising the notion of port graph introduced in [START_REF] Andrei | A Rewriting Calculus for Multigraphs with Ports[END_REF][START_REF] Andrei | A Higher-Order Graph Calculus for Autonomic Computing[END_REF]. The following definitions, based on [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF], have been generalised to use indistinctly either directed or undirected edges. We present first the intuitive ideas, followed by the formal definition of port graph rewriting.

Port graphs

Intuitively, a port graph is a graph where nodes have explicit connection points called ports, to which edges are attached. Nodes, ports and edges are labelled by records listing their attributes.

A signature ∇ used to label the graph is composed of:

-∇ A , a set of attributes; -X A , a set of attribute variables; -∇ V , a set of values; -X V , a set of value variables.

where ∇ A , X A , ∇ V and X V are pairwise disjoint. ∇ A contains distinguished elements Name, (In/Out)Arity, Connect, Attach, Interface. Values in ∇ V are assumed to be of basic data types such as strings, int, bool,. . . or to be well-typed computable expressions built using ∇ and basic types.

Definition 1 (Record). A record r over the signature ∇ is a set of pairs {(a 1 , v 1 ), . . . , (a n , v n )}, where a i ∈ ∇ A ∪ X A for 1 ≤ i ≤ n, called attributes; each a i occurs only once in r, and there is one distinguished attribute Name.

v i ∈ ∇ V for 1 ≤ i ≤ n, called values.
The function Atts applies to records and returns all their attributes:

Atts(r) = {a 1 , . . . , a n } if r = {(a 1 , v 1 ), . . . , (a n , v n )}.
As usual, r.a i denotes the value v i of the attribute a i in r.

The attribute Name identifies the record in the following sense: For all r 1 , r 2 , Atts(r 1 ) = Atts(r 2 ) if r 1 .Name = r 2 .Name.

Definition 2 ((Directed) Port graph). Given sets N , P, E of nodes, ports and edges, a port graph over a signature ∇ is a tuple G = (N, P, E, L) where -N ⊆ N is a finite set of nodes; n, n , n 1 , . . . range over nodes.

-P ⊆ P is a finite set of ports; p, p , p 1 , . . . range over ports.

-E ⊆ E is a finite set of edges between ports; e, e , e 1 , . . . range over edges.

Edges can be directed and two ports may be connected by more than one edge. -L is a labelling function that returns, for each element in N ∪ P ∪ E, a record such that:

• for each edge e ∈ E, L(e) contains an attribute Connect whose value is the ordered pair (p 1 , p 2 ) of ports connected by e. • for each port p ∈ P , L(p) contains an attribute Attach whose value is the node n which the port belongs to, and an attribute Arity whose value is the number of edges connected to this port. When edges are directed, ports have instead two attributes, InArity and OutArity, whose respective values are the number of edges directed to and from this port. • For each node n ∈ N , L(n) contains an attribute Interface whose value is the set of names of ports in the node:

{L(p i ).Name | L(p i ).Attach = n}.
We assume that L satisfies the following constraint:

L(n 1 ).Name = L(n 2 ).Name ⇒ L(n 1 ).Interface = L(n 2 ).Interface.
By definition 2, nodes with the same name (i.e., the same value for the attribute Name) have the same set of port names (i.e., the same interface), with the same attributes but possibly with different values. Variables may be used to denote any value.

Two nodes n, n ∈ N connected by an undirected edge are said to be adjacent and each other neighbours. However, for a directed edge (n, n ) ∈ E going from n to n , only n is said adjacent to n (not conversely) and is called a neighbour of n. The set of nodes adjacent to a subgraph F in G consists of all the nodes in G outside F and adjacent to any node in F . N (n) denotes the set of neighbours of the node n.

The advantage of using port graphs rather than plain graphs is that they allow us to express in a more structured and explicit way the properties of the connections, since ports represent the connecting points between edges and nodes. However, the counterpart is that the implementation, rules and matching operations are more complex. So, whenever possible, it is simpler and more efficient to keep the number of ports for each node to a minimum.

Example 1 (Social Network). A social network [START_REF] Brandes | Analysis and visualization of social networks[END_REF] is commonly described as a graph G = (N, E) built from a set of nodes (the users) N and a set of edges E ⊆ N × N linking users. Although in most real-world social relations, two persons relate to each other with a mutual recognition, some social networks present an asymmetric model of acknowledgement, the most popular of them being Twitter, classifying one of the users as a follower while the other is a followee. Such relations can be very simply represented by orienting edges, thus transforming our initial graph in a directed graph.

In this paper, we model a social network as a port graph, where nodes represent users and edges are connections between them. Edges are directed to reflect the relation between users (e.g., follower/followee) and store the attributes of their relation (e.g., influence level, threshold value. . . ). An alternative solution would be to use undirected edges and nodes with two ports called "In" and "Out" for instance, as in [START_REF] Vallet | A visual analytics approach to compare propagation models in social networks[END_REF], to simulate edge direction. In this paper, the nodes representing users have only one port gathering directed connections. While this is sufficient for simple cases, when facing real social networks, multiple ports are useful, either to connect users according to the nature of their relation (e.g., friends, family, co-workers. . . ) or to model situations where a user is connected to friends via different social networks. The full power of port graphs is indeed necessary in multi-layer networks [START_REF] Kivelä | Multilayer networks[END_REF] where edges are assigned to different layers and where nodes are shared. In that case, different ports are related to different layers, which can improve modularity of design, readability and matching efficiency through various heuristics. This is however a topic left for future work.

Example 2 (Propagation). Propagation in a network can be seen as follows: when users perform a specific action (announcing an event, spreading a gossip, sharing a video clip, etc.), they become active. They inform their neighbours of their state change, giving them the possibility to become active themselves if they perform the same action. Such process reiterates as the newly active neighbours share the information with their own neighbours. The activation can thus propagate from peer to peer across the whole network.

To replicate this phenomena observed in real-world networks, some models opt for entirely probabilistic activations (e.g., [START_REF] Chen | Influence maximization in social networks when negative opinions may emerge and propagate[END_REF][START_REF] Wonyeol | CT-IC: Continuously activated and time-restricted independent cascade model for viral marketing[END_REF]) where the presence of only one active neighbour is enough to allow the propagation to occur. Other models use threshold values (e.g., [START_REF] Goyal | Learning influence probabilities in social networks[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF][START_REF] Watts | A simple model of global cascades on random networks[END_REF]) building up during the propagation.

Such values represent the influence of one user on his neighbours or his tolerance towards performing a given action (the more solicited a user is, the more inclined he becomes to either activate or utterly resist).

To express propagation conditions (e.g., a probabilistic model for node activation, or activation after reaching a predefined threshold), it is natural to make use of records with expressions, i.e., include specific attributes whose values are numerical expressions. More specifically:

-Each node n has an attribute Active that indicates whether it contributes to the propagation or not. It is coupled with the Colour attribute, which takes accordingly green or red values. The node n has also a Sigma attribute that measures the maximum influence withstood by n from its active neighbours at the time being. -An edge e that connects two ports p and p of the respective nodes n and n has an attribute Influence which indicates the influence of n (i.e., L(p ).Attach) on n (i.e., L(p).Attach).

The edge e has also a Boolean attribute Marked , initially false, which becomes true when n is inactive, n is active and n has tried to influence n.

Rewriting

We see a port graph rewrite rule L ⇒ R as a port graph consisting of two subgraphs L and R together with a special node (called arrow node) that encodes the correspondence between the ports of L and the ports of R. Each of the ports attached to the arrow node has an attribute T ype ∈ ∇ A , which can have three different values: bridge, wire and blackhole. The value indicates how a rewriting step using this rule should affect the edges that connect the redex to the rest of the graph. We give details below.

Definition 3 (Port graph rewrite rule). A port graph rewrite rule is a port graph consisting of:

two port graphs L and R over the signature ∇, respectively called left-hand side and right-hand side, such that all the variables in R occur in L, and R may contain records with expressions; an arrow node with a set of edges that each connect a port of the arrow node to ports in L or R.

The arrow node has for N ame ⇒. Each port in the arrow node has an attribute Type, which can be of value: bridge, blackhole or wire, satisfying the following conditions:

1. A port of type bridge must have edges connecting it to L and to R (one edge to L and one or more to R). 2. A port of type blackhole must have edges connecting it only to L (at least one edge). 3. A port of type wire must have exactly two edges connecting to L and no edge connecting to R.

The arrow node has an optional attribute Where whose value is a Boolean expression involving the predicate Edge, applied to node and port names, and Boolean operators.

When modelling rumour propagation, the rules never suppress nor add new nodes. Moreover, when there is only one port per node, there is no ambiguity on the rewiring between left and right-hand sides. In that case indeed, the structure and visualisation of the arrow node is much simpler. However, this only holds when the network's structure does not change.

The introduction of the Where attribute is inspired from the GP programming system [START_REF] Plump | The Graph Programming Language GP[END_REF] (and from Elan [START_REF] Borovanský | An overview of ELAN[END_REF] with a more general definition), in which a rule may have a condition introduced by the keyword where. For instance, a condition where not Edge(n,n') requires that no edge exists between the nodes n and n . This condition is checked at matching time.

Let us first recall the notion of port graph morphism [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF]. Let G and H be two port graphs over the same signature ∇. A port graph morphism f : G → H maps nodes, ports and (directed) edges of G to those of H such that the attachment of ports and the (directed) edges connections are preserved, all attributes and values are preserved except for variables in G, which must be instantiated in H. Intuitively, the morphism identifies a subgraph of H that is equal to G except at positions where G has variables (at those positions, H could have any instance).

Definition 4 (Match). Let L ⇒ R be a port graph rewrite rule and G a port graph. We say a match g(L) of the left-hand side (also called a redex) is found if:

-There is a port graph morphism g from L to G; hence g(L) is a subgraph of G.

-If the arrow node has an attribute Where with value C, C must be true of g(L). -For each port in L that is not connected to the arrow node, its corresponding port in g(L) must not be an extremity in the set of edges of G -g(L).

This last point ensures that ports in L that are not connected to the arrow node are mapped to ports in g(L) that have no edges connecting them with ports outside the redex, to avoid dangling edges in rewriting steps.

Several injective morphisms g from L to G may exist (leading to different rewriting steps); they are computed as solutions of a matching problem from L to (a subgraph of) G.

Definition 5 (Rewriting step).

According to [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF], a rewriting step on G using a rule L ⇒ R (where C) and a morphism g : L → G (satisfying C), written G → g L⇒R G , transforms G into a new graph G obtained from G by performing the following operations in three phases:

-In the build phase, after a redex g(L) is found in G, a copy R c = g(R) (i.e.,
an instantiated copy of the port graph R) is added to G.

-The rewiring phase then redirects edges from G to R c as follows:

For each port p in the arrow node:

• If p is a bridge port and p L ∈ L is connected to p: for each port p i R ∈ R connected to p, find all the ports p k G in G that are connected to g(p L ) and are not in g(L), and redirect each edge connecting p k G and g(p L ) to connect p k G and p i Rc .

• If p is a wire port connected to two ports p 1 and p 2 in L, then take all the ports outside g(L) that are connected to g(p 1 ) in G and connect each of them to each port outside g(L) connected by an edge to g(p 2 ). • If p is a blackhole: for each port p L ∈ L connected to p, destroy all the edges connected to g(p L ) in G. -The deletion phase simply deletes g(L). This creates the final graph G .

Example 3 (Propagation). Figure 1 shows two rules used for propagation. Active nodes are depicted in green and visited nodes in purple. Red nodes are in an inactive state (however, they may have been visited already). Rule R1 in Figure 1(a) indicates that when an activated node n is connected to an inactive node n, it tries to influence it. If it succeeds, a second rule, Rule R2 in Figure 1(b), makes this node active.

In a social network G = (N, E), let n and n be two nodes (n, n ∈ N ) connected via an edge e = (n, n) ∈ E. The node's attribute L(n).Sigma, giving the influence withstood by n and initially set to 0, is updated such as:

L(n).Sigma = max L(e).Influence r , L(n).Sigma
where r is a random number between 0 and 1 and L(e).Influence is the influence of n on n. The formula is stored as a node attribute in the right-hand side of Rule R1 in Figure 1(a) and each corresponding rewriting performs the update. More details are given in [START_REF] Vallet | A visual analytics approach to compare propagation models in social networks[END_REF].

Given a finite set R of rules, a port graph G rewrites to G , denoted by G → R G , if there is a rule r in R and a morphism g such that G → g r G . This induces a reflexive and transitive relation on port graphs, called the rewriting relation, denoted by → * R . A port graph on which no rule is applicable is irreducible. A derivation, or computation, is a sequence G → * R G of rewriting steps. Each rewriting step involves the application of a rule at a specific position in the graph. A derivation tree from G represents all possible computations (with possibly infinite ones) and strategies are used to specify the rewriting steps of interest, by selecting branches in the derivation tree.

Strategic graph programs

In this section, we recall the concept of strategic graph program, consisting of a located graph (a port graph with two distinguished subgraphs that specify the locations where rewriting is enabled/disabled), a set of rewriting rules, and a strategy expression. We then recall the strategy language presented in [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF] to define strategy expressions. In addition to the well-known constructs to select rewrite rules, the strategy language provides position primitives to select or ban specific positions in the graph for rewriting. The latter is useful to program graph traversals in a concise and natural way, and is a distinctive feature of the language. In the context of social networks, the position primitives are also convenient to restrict the application of rules to specific parts of the graph.

Located graphs and rewrite rules First, we recall that, in graph theory, a subgraph of a graph

G = (N G , E G ) is a graph H = (N H , E H ) contained in G, that is, N H ⊆ N G and E H ⊆ E G . The definition extends to directed port graphs in the natural way: let G = (N G , P G , E G , L G ) and H = (N H , P H , E H , L H ) be port graphs over the signature ∇. H is a subgraph of G if N H ⊆ N G , P H ⊆ P G , E H ⊆ E G , L H = L G | N H ∪P H ∪E H , that is, L H is the restriction to H of the labelling function of G.
Definition 6 (Located graph). According to [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF], a located graph G Q P consists of a port graph G and two distinguished subgraphs P and Q of G, called respectively the position subgraph, or simply position, and the banned subgraph.

In a located graph G Q P , P represents the subgraph of G where rewriting steps may take place (i.e., P is the focus of the rewriting) and Q represents the subgraph of G where rewriting steps are forbidden. We give a precise definition below; the intuition is that subgraphs of G that overlap with P may be rewritten, if they are outside Q.

When applying a port graph rewrite rule, not only the underlying graph G but also the position and banned subgraphs may change. A located rewrite rule, defined below, specifies two disjoint subgraphs M and M of the right-hand side R that are respectively used to update the position and banned subgraphs. If M (resp. M ) is not specified, R (resp. the empty graph ∅) is used as default. Below, we use the operators ∪, ∩, \ to denote union, intersection and complement of port graphs. These operators are defined in the natural way on port graphs considered as sets of nodes, ports and edges.

Definition 7 (Located rewrite rule).

A located rewrite rule is given by a port graph rewrite rule L ⇒ R, and, optionally, a subgraph W of L and two disjoint subgraphs M and M of R.

It is denoted L W ⇒ R M M . We write G Q P → g L W ⇒R M M G Q P and say that the located graph G Q P rewrites to G Q P using L W ⇒ R M M at position P avoiding Q, if G → L⇒R G
with a morphism g such that g(L) ∩ P = g(W ) or simply g(L) ∩ P = ∅ if W is not provided, and g(L) ∩ Q = ∅. The new position subgraph P and banned subgraph Q are defined as

P = (P \ g(L)) ∪ g(M ), Q = Q∪g(M ); if M (resp. M ) are not provided then we assume M = R (resp. M = ∅).
In general, for a given located rule L W ⇒ R M M and located graph G Q P , more than one morphism g, such that g(L) ∩ P = g(W ) and g(L) ∩ Q is empty, may exist (i.e., several rewriting steps at P avoiding Q may be possible). Thus, the application of the rule at P avoiding Q produces a set of located graphs.

Example 4. In influence propagation, banned subgraphs are used to avoid several activations of the same neighbours. Another usage is to select a specific community in the social network where the propagation should take place.

Strategies

To control the application of the rules, a strategy language is presented in [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF]. We recall it in Table 1, including some additional constructs that are needed to deal with directed edges.

Strategy expressions are generated by the grammar rules from the nonterminal S. A strategy expression combines applications of located rewrite rules, generated by the non-terminal A, and position updates, generated by the nonterminal U , using focusing expressions, generated by F . Subgraphs of a given graph can be defined by specifying simple properties, expressed with attributes of nodes, edges and ports. The strategy constructs, generated by S, are used to compose strategies and are strongly inspired from term rewriting languages such as Elan [START_REF] Borovanský | An overview of ELAN[END_REF], Stratego [START_REF] Visser | Stratego: A language for program transformation based on rewriting strategies. System description of Stratego 0.5[END_REF] and Tom [START_REF] Balland | Tom: Piggybacking Rewriting on Java[END_REF].

We briefly explain below the constructs used in this paper. A full description of the language can be found in [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF]. The primary construct is a located rule, which can only be applied to a located graph G Q P if at least a part of the redex is in P , and does not involve Q. When probabilities π 1 , . . . , π k ∈ [0, 1] are associated to rules T 1 , . . . , T k such that π 1 + • • • + π k = 1, the strategy ppick(T 1 , π 1 , . . . , T k , π k ) picks one of the rules for application, according to the given probabilities. all(T ) denotes all possible applications of the transformation T on the located graph at the current position, creating a new located graph for each application. In the derivation tree, this creates as many children as there are possible applications. one(T ) computes only one of the possible applications of the transformation and ignores the others; more precisely, it makes an equiprobable choice between all possible applications.

F ::= crtGraph | crtPos | crtBan | F ∪ F | F ∩ F | F \ F | (F ) | ∅ | ppick(F1, π1, . . . , F k , π k ) | property(F, ρ) | ngb(F, ρ) | ngbOut(F, ρ) | ngbIn(F, ρ) (Determine) D ::= all(F ) | one(F ) (Update) U ::= setPos(D) | setBan(D) | update(f unction{parameters list}) Properties (Properties) ρ := Elem, Expr Elem := node | edge | port Expr := attribute Relop v | true Relop := == | != | > | < | >= | <= | =∼ Compositions (Comparison) C ::= F = F | F != F | F ⊂ F | isEmpty(F ) | match(T ) (
Similar constructs exist for positions focusing: one(F ) returns one node in F and all(F ) returns the full F . In the remaining of this paper, when not specified, F stands for all(F ).

Focusing expressions are used to define positions for rewriting in a graph, or to define positions where rewriting is not allowed. They denote functions used in strategy expressions to change the positions P and Q in the current located graph. In this paper, we use:

-crtGraph, crtPos and crtBan, applied to a located graph G Q P , return respectively the whole graph G, P and Q.

property(F, ρ) is used to select elements of a given graph that satisfy a certain property, specified by ρ. It can be seen as a filtering construct: if the expression F generates a subgraph G then property(F, ρ) returns only the nodes and/or edges from G that satisfy the decidable property ρ = Elem, Expr. Depending on the value of Elem, the property is evaluated on nodes, ports, or edges. ngb(F, ρ) returns a subset of the neighbours (i.e., adjacent nodes) of F according to ρ. Note that the direction of the edge is taken into account; to emphasise it, we introduce ngbOut(F, ρ) and its counterpart ngbIn(F, ρ). If edge is used, i.e., if we write ngb(F, edge, Expr), it returns all the neighbours of F connected to F via edges which satisfy the expression Expr. -setPos(D) (resp. setBan(D)) sets the position subgraph P (resp. Q) to be the graph resulting from the expression D. It always succeeds (i.e., returns id).

The following constructs are also used:

-S;S represents sequential application of S followed by S .

repeat(S)[max n] simply iterates the application of S until it fails, but, if max n is specified, then the number of repetitions cannot exceed n. -(S)orelse(S ) applies S if possible, otherwise applies S . It fails if both S and S fail. -When probabilities π 1 , . . . , π k ∈ [0, 1] are associated to strategies S 1 , . . . , S k such that π 1 + • • • + π k = 1, the strategy ppick(S 1 , π 1 , . . . , S k , π k ) picks one of the strategies for application, according to the given probabilities. This construct generalises the probabilistic constructs on rules and positions.

Example 5 (Propagation). (Example 3 cont'd)

To illustrate the strategy language, let us come back to the propagation model in social networks and to the two rules described in Figure 1. When Rule R1 in Figure 1(a) is applied on a pair of nodes active(n)/non active(n) (green/red): a) we generate a random number r ∈]0, 1]; b) we store in the attribute L(n).Sigma the new value of Sigma for n computed with the previously given formula; and c) using the Marked attribute, we mark the edge e linking n to n to prevent the selection of this particular pair configuration in the next pattern matching searches. This ensures that the active node n will not be able to try to influence the same node n over and over. Once every pair of active/inactive neighbours has been tried, if n is sufficiently influenced (i.e., L(n).Sigma ≥ 1), Rule R2 in Figure 1(b) is applied and n becomes active. This behaviour is expressed with the following strategy:

Strategy 1: Influence propagation in social network.

1 repeat(R1); 2 setPos(property(crtGraph, node, Sigma ≥ "1")); 3 repeat(R2)

This example illustrates how record expressions may be used to compute attribute values and how they are updated through application of rules.

Probabilistic features of the Porgy strategy language, through the use of the ppick() construct, are illustrated in Section 3 for social network generation.

A more complete formal definition of strategic graph programs and their semantics can be found in [START_REF] Fernández | Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework[END_REF]. Correctness and completeness of strategic port graph rewriting are stated and imply in particular that the derivation tree in which each rewrite step is performed according to the strategy -let us call it the strategic derivation tree-is actually a subtree of the derivation tree of the rewrite system without strategy. The strategic derivation tree is a valuable concept because it records the history of the transformations and provides access to generated models. It is, by itself, a source of challenging questions, such as detecting isomorphic models and folding the tree, finding equivalent paths and defining the "best ones", abstracting a sequence of steps by a composition strategy, or managing the complexity of the tree and its visualisation.

From now on, the paper focuses on social networks generation using the introduced labelled graph rewriting concepts and the Porgy environment.

Social network generation

We focus in the following on generating graphs with a small-world property as defined in [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. Such graphs are characterised by a small diameter -the average distance between any pair of nodes is short-and strong local clustering -any pair of connected nodes tend to both be connected to the same neighbour nodes thus creating densely linked groups of nodes, also called communities. Popularised by Milgram in [START_REF] Milgram | The small world problem[END_REF], small-world graphs are a perfect case study for information propagation in social networks due to their small diameter allowing a quick and efficient spreading of information among the users. Furthermore, the graph G = (N, E) produced by the generation process satisfies the following requirements: the number of nodes |N | and directed edges |E| are given a priori ; G is formed of a sole connected component thus |E| should at least be equal to |N | -1; any ordered pair of nodes (n, n ) can only be linked once, thus maximising the possible number of edges in G to |E| max = |N | × (|N | -1); finally, the definitive number of communities is left to be randomly decided during the generative operations.

A few previous works have explored the idea of using rules to generate networks. In [START_REF] Kejžar | Probabilistic inductive classes of graphs[END_REF], the authors define and study probabilistic inductive classes of graphs generated by rules which model spread of knowledge, dynamics of acquaintanceship and emergence of communities. The model presented below follows a rather similar approach; however, we have adjusted its generative rules to cope with directed edges and ensure the creation of a graph with a single connected component. This is achieved by performing the generation through local additive transformations, each only creating new elements connected to the sole component, thus increasingly making the graph larger, more intricate and more interesting to study.

Starting from one node, the generation is divided into three phases imitating the process followed by real-world social networks. Whenever new users first join the social network, their number of connections is very limited, mostly to the other users who have introduced them to the social network. Then comes the second phase where the new users reach the people they already know personally, thus creating new connections within the network, which may seem random for any spectator only aware of the present social network. Finally, the new users start to get to know the people with whom they are sharing friends in the network, potentially leading to the creation of new connections.

The method presented below can easily be extended to create graphs with more than one component. One has to use a number of starting nodes equal to the number of desired connected components and ensure that no edge is created between nodes from different components. The generative rules and strategies can then be applied on each component iteratively or in parallel (parallel application of rules is possible but beyond the scope of this paper).

The first step (Sect. 3.1) generates a simple directed acyclic graph representing an initial simple network evolving as new users join it. It is then complemented with additional edges in the second step (Sect. 3.2), as users "import" their pre-existing connections into the social network. Finally, the third and final step (Sect. 3.3) focuses on creating communities as users connect with the friends of their friends within the network.

Generation of a directed acyclic graph

The first step toward the construction of the directed graph G = (N, E) uses the two rules shown in Figures 2(a) and 2(b). Both rewriting operations start with a single node and transform it to generate a second node linked to the first one (thus creating a new node and a new edge with each application). The difference between those two rules lies in the edge orientation as Rule 2(a) creates an outgoing edge on the initiating node, while Rule 2(b) creates an incoming edge.

We can notice the left hand-sides of both rules require the existence of a node prior to their application, thus imposing the starting graph upon which the rules will be applied to have at least one node. As we also seek to ensure that only one connected component exists prior to any transformation, we use a single node as the starting graph. The whole node generation is achieved during this first phase and managed using Strategy 2. It repeatedly applies the generative rules |N | -1 times so that the graph reaches the appropriate number of nodes. As mentioned earlier, each rule application also generates a new edge, which means that once executed, Strategy 2 produces a graph with exactly |N | nodes and |N | -1 edges. The orientation of each edge varies depending of the rule applied (either 2(a) or 2(b)), moreover, their application using the ppick() construct allows us to ensure an equiprobable choice between the two rules. We focus next on generating additional edges.

Creating complementary connections

We still need to generate (|E|-|N |+1) additional edges in the graph G. However, because we want to ensure the creation of communities during the last phase, we do not wish to create all the remaining edges just now. Depending on how we balance the number of edges created during this phase and the next one, the final graphs will present different characteristics (see Figures 5 and6). During this phase, we aim to create either seemingly random connections between the network users or to reciprocate already existing single-sided connections. We use two rules to link existing nodes thus creating a new additional edge with each application. The first rule (Fig. 3(a)) simply considers two nodes and adds an edge between them to emulate the creation of a (one-sided) connection between two users. The second rule (Fig. 3(b)) reciprocates an existing connection between a pair of users: for two nodes n, n ∈ N connected with an edge (n , n), a new edge (n, n ) is created; it is used to represent the mutual appreciation of users in the social network. Note that, because each node is randomly chosen among the possible matches, we do not need to create alternative versions of these rules with reversed oriented edges.

In both rules, the existence of edges between the nodes on which the rule applies should be taken into account. Though the rules visual representations do not explicitly indicate it, any edge (n, n ) created by either rule cannot already exist in the network, thus forbidding the rules to apply in such case. This requirement can be taken into account by adding a condition "where not Edge(n,n')" introduced in Definition 3. It can also be handled through positions for limiting the elements to be considered during matching. We use the latter solution here. Strategy 3 presents how we proceed. First, we filter the elements to consider during the matching. We randomly select one node among the nodes whose outgoing arity (OutArity) is lower than the maximal possible value (i.e., |N | -1), and we banish all of its outgoing neighbours as they cannot be considered as potential matching elements. Then, Rule 3(a) or Rule 3(b) are equiprobably applied to add a new edge from the selected node. Previously banishing neighbours allows only considering pair of nodes not already connected. This ensures that the graph is kept simple (i.e., only one edge per direction between two nodes).

We all possible rule application combinations, thus, if one of the rules can be applied, it is found. If neither rule can be applied, the maximum number of edges in the graph has been reached, i.e., the graph is complete. The values given for the number of edges |E | is too high to create a simple graph. If the strategy went well, we are left with (|E| -|E | -|N | + 1) remaining edges to create in the next step for enforcing communities within G.

Construction of communities

To create a realistic social network, we want to add communities. Thus, some of the links between users have to follow certain patterns. Based on ideas advanced in several previous works (e.g., [START_REF] Cartwright | Structural balance: a generalization of Heider's theory[END_REF][START_REF] Kejžar | Probabilistic inductive classes of graphs[END_REF][START_REF] Leskovec | Signed networks in social media[END_REF][START_REF] Nick | Simmelian backbones: Amplifying hidden homophily in facebook networks[END_REF]), we focus our interest on triad configurations (i.e., groups formed by three users linked together) to generate and extend communities via the three rewrite rules introduced in Figure 4.

The first triad rule (Fig. 4(a)) considers how a first user (A) influences a second user (B) who influences in turn a third user (C). This situation can produce some sort of transitivity as "the idol of my idol is my idol", meaning that A is much likely to influence C. We use here the term "idol" instead of the more classical "friend" because we only consider single-sided relations as a base for the transformation. The second rule (Fig. 4(b)) shows two users (B and C) being influenced by a third user (A). When in this position, the users B and C might start exchanging (similar connections, common interests. . . ), thus creating a relation between the two of them (either from B to C or the opposite). The last rule (Fig. 4(c)) depicts one user (B) being influenced by two other users (A and C). This case can happen when A and C are well-versed about a common subject of interest which is of importance to B. An exchange can thus appear between the two influential users (from A to C for instance).

The three rules use a where not Edge(n,n') condition to forbid the existence of an edge between two matching nodes. The condition is visually encoded using a cross-shaped headed edge to indicate which edge should be verified as non-existent during the matching operations.

Strategy 4 is used to drive the three rules. Like the previous strategy, this one aims at equiprobably testing all possible combinations between the rules.

Resulting network generation

Once the last strategy execution is completed, the social network generation is achieved. For the sake of simplicity, the strategies presented above aim at making equiprobable choices between rules. The probabilities may of course be modified to take into account any specific condition present in the modelled system, moreover, whatever the chosen probabilities are, the following result holds. Proof. Let us prove by induction that the generated port graphs are directed, simple (at most one edge in each direction between any two nodes) and weakly connected (connected when direction of edges is ignored). This is trivially true for G 0 and each rewrite step preserves these three properties, thanks to the positioning strategy that controls the outdegree in Edge generation (Strategy 3) and the forbidden edges in the rules for Community generation (Figure 4). As the strategic program never fails, since a repeat strategy cannot fail, this means that a finite number of rules has been applied and the three properties hold by

Implementation, Experimentation and Visualisation

We use the Porgy system [START_REF] Pinaud | PORGY: A Visual Graph Rewriting Environment for Complex Systems[END_REF] to experiment with our generative model. The latest version of the rewriting platform5 is available either as source code or binaries for MacOS and Windows machines. To ensure that our constructions present characteristics of real-world social networks, we have performed several generations using different parameters and measured the characteristic path length -the average number of edges in the shortest path between any two nodes in the graph -and the clustering coefficient -how many neighbours of a node n are also connected with each other -as defined in [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. In a typical random graph, e.g., a graph generated using the Erdös-Rényi model [START_REF] Erdős | On the evolution of random graphs[END_REF] or using our method with the parameters |N | = 100 nodes, |E| = 500 edges and |E | = |E| -|N | + 1 = 401, the average characteristic path length is very short (L 2.274), allowing information to go quickly from one node to another, but the clustering coefficient is low (C 0.101), implying the lack of well-developed communities. However, with the parameters used in Figure 5 (respectively, Figure 6), we retain a short characteristic path length L 2.563 (resp. L 3.372) while increasing the clustering coefficient C 0.426 (resp. C 0.596), thus matching the characteristics of small-world graphs: a small diameter and strong local clustering. The graphs generated using our method can be subsequently used as any randomly generated network. For instance, we have used such graphs in [START_REF] Vallet | A visual analytics approach to compare propagation models in social networks[END_REF] to study the evolution of different information propagation models. Porgy was used in this work to run several propagation scenarios and analyse the resulting outputs with its visualisation tools.

Conclusion

Our first experiments and results on generation and propagation in social networks, obtained in [START_REF] Vallet | A visual analytics approach to compare propagation models in social networks[END_REF] and in this work, illustrate how labelled port graph strategic rewriting provides a common formalism in which different mathematical models can be expressed and compared. The ultimate goal is to provide a simulation environment helpful for making decisions, such as choosing good parameters, detecting and preventing unwanted situations, or looking for a better diffusion strategy.

As a first approach to this ambitious challenge, we focused on social networks that already offer a big variety of situations and problems. Several lessons and research directions can be drawn from this study, both for the rewriting community and for the social network community.

First, dealing with this application domain led us to validate the concepts of labelled port graphs on a given signature, of rules that are themselves also labelled port graphs with variables from the given signature, and of strategy constructs added to define positions in graphs in a flexible way. When modelling the evolution of the studied network, the derivation tree (also a port graph) provides support for history tracking, state comparison, state recovery and backtracking. For the social network community, the rewrite rule approach is not quite surprising because some works such as [START_REF] Kejžar | Probabilistic inductive classes of graphs[END_REF] already use rules to generate social networks, although without claiming it. The fact that different models can be expressed in a common formalism provides a good argument for those who are interested to compare various algorithms and models. In such situations, simulations can indeed help for taking decision, for instance to prevent bad situations, or to look for optimal diffusion strategy.

Indeed several issues remain to address. For rewriting, although graph rewriting has been largely studied, addressing social network applications causes a drastic change of scale for the structures. Dealing with millions of nodes and edges requires great attention to size and complexity. There is also room for improvement in data storage and retrieval -in connection with graph data bases-, subgraph matching algorithms -either exact or approximate-for finding one or all solutions, parallel graph rewriting avoiding dangling edges, and probabilistic or stochastic issues for matching and rewriting, for instance, in the context of imprecise data or privacy constraints. Also related to size, but even more to complexity of information data, there is a need for data structuring and management, that may be carried on by abstraction pattern, focusing on points of interests, hierarchies and views (for instance, through multi-layer graphs). All these notions need a precise and logical definition that may be influenced by well-known programming language concepts. As programs, data need certification and validation tools and process, not only at one step but all along their evolution. The knowledge developed in the logic and rewriting community should be valuable in this context. This study has also revealed the importance of visualisation and raises some challenges in this area. Visualisation is important, more widely, for data analysis, program engineering, program debugging, testing or verifying. However, the representation of dynamic or evolving data, such as social networks or richer graph structures, is yet an actual research topic for the visualisation community.

In future work, we plan to address multi-layer networks, based on societal problems. An example is tracking criminal activities. The objective then is to build a new methodology for tracking, based on construction, manipulation and analysis of heterogeneous digital information coming from different sources: legal records of tribunal sentences, social networks coming from exchanges, meetings, phone calls, information on financial flows and even family relations. Beyond the modelisation challenge, in connection with jurists and social scientists, we expect that our formalism of labelled port graphs, rules and strategy will provide an adequate framework for simulations and hypotheses testing.

  (a) R1 : Influence trial. An active neighbour (green) influences an inactive node (red) by visiting it (transformation into a blue node). (b) R2 : Node activation. A visited node (blue) sufficiently influenced is activated (transformation into a green node).

Fig. 1 .

 1 Fig.1. Rules used to express a propagation model. For both rules, we use two specific node's attributes -active and visited -to manage the matching performed, the different colours being visual cues helping users identifying the node state at a glance. Green nodes, or active nodes, must have their attributes active equal to 1 and visited equal to 0; red nodes, or inactive nodes, must have their attributes active equal to 0 and visited equal to 0; finally, blue nodes, or visited nodes, must have their attributes active equal to 0 and visited equal to 1.

  Let L, R be port graphs; M, M subgraphs of R; W a subgraph of L; k ∈ N; π i=1...k ∈ [0, 1]; k i=1 πi = 1; let attribute be an attribute label in ∇ A ; v ∈ ∇ V a valid expression without variables; Rules (Transformations) T ::= LW ⇒ R M M | (T T ) | ppick(T1, π1, . . . , T k , π k ) (Applications) A ::= all(T ) | one(T ) Positions (Focusing)

  Strategies) S ::= id | fail | A | U | C | S; S | if(S)then(S)else(S) | (S)orelse(S) | repeat(S)[(k)] | while(S)[(k)]do(S) | ppick(S1, π1, . . . , S k , π k ) | try(S) | not(S)

Fig. 2 .

 2 Fig. 2. Rules used for generating and re-attaching nodes to the social network. For both rules, a new node is created in the right-hand side and connected to the preexisting node. The main difference between the two rules resides in the generated edge orientation: going from the pre-existing node (belonging to the social network) to the newly added node in Rule (a) or oriented in the opposite direction in Rule (b).

Strategy 2 :

 2 Node generation: Creating a directed acyclic graph of size N 1 //equiprobabilistic application of the two rules used for generating nodes 2 repeat( 3 ppick(one(GenerationN ode1), 0.5, 4 one(GenerationN ode2), 0.5) 5 )(|N | -1) // Generation of N nodes

  (a) Rule GenerationEdge.(b) Rule GenerationMirror.

Fig. 3 .

 3 Fig. 3. First set of rules used to generate additional connections within the social network. Rule (a) is used to create a new connection between two previously created and unrelated nodes, while Rule (b) is applied on a pair of connected nodes and generates a new edge reciprocating the pre-existing connection.

3 : 8 (

 38 aim to create |E | more edges, where |E | < (|E| -|N | + 1) to keep the number of edges below |E|. The use of the ( )orelse() construct allows testing Strategy Edge generation: addition of |E | edges if possible. 1 repeat( 2 //select one node with an appropriate number of neighbours 3 setPos(one(property(crtGraph, node, OutArity < |N | -1))); 4 //for this node, forbid rule applications on its outgoing neighbours 5 setBan(all(ngbOut(crtPos, node, true))); 6 //equiprobable application of the edge generation rules 7 ppick((one(GenerationEdge))orelse(one(GenerationM irror)), 0.5, one(GenerationM irror))orelse(one(GenerationEdge)), 0.5); 9 )(|E |)

  (a) Rule CommunityLegacy. (b) Rule CommunityDown.(c) Rule CommunityUp.

Fig. 4 .

 4 Fig. 4. Generation of additional connections based on triads. Rule (a) is used to identify influence chains: when C is influenced by B, itself influenced by A, the rule creates a new connection from A to C. Rule (b) focuses on triads where two users B and C are influenced by a third person A: this common characteristic can lead B and C to develop a relation. Rule (c) is somewhat the opposite of Rule (b): two users A and C influence a third user B, creating a connection between them (from A to C). Two distinctive edge types are used: standard arrow edges for representing existing connections and crossshaped headed edges for indicating edges which should not exist during the matching phase.

Proposition 1 .

 1 Given three positive integer parameters |N |, |E|, |E |, such that |N |-1 ≤ |E| ≤ |N |×(|N |-1) and |E | ≤ |E|-|N |+1, let the strategy S |N |,|E|,|E | be the sequential composition of the strategies Node generation, Edge generation and Community generation described above, and G 0 be a port graph composed of one node with one port. The strategic graph program [S, G 0 ] terminates with a port graph G with |N | nodes and |E| edges, which is simple, directed and weaklyconnected.

Strategy 4 : 5 ( 6 ( 7 ) 10 ( 11 ( 12 ) 15 (

 456710111215 Community generation: remaining edges creation to strengthen communities one(CommunityU p))orelse(one(CommunityLegacy)), 0.5, one(CommunityLegacy))orelse(one(CommunityU p)), 0.5) one(CommunityLegacy))orelse(one(CommunityDown)), 0.5, one(CommunityDown))orelse(one(CommunityLegacy)), 0.5) one(CommunityDown))orelse(one(CommunityU p)), 0.5, 16 (one(CommunityU p))orelse(one(CommunityDown)), 0.5) 17 ), 1/3) 18 )(|E| -|E | -|N | + 1)

  rewriting induction. Then by construction, the strategy Node generation creates a new node and a new edge at each step of the repeat loop, exactly |N | -1, and is the only strategy that creates new nodes. From here, G has exactly |N | nodes and |N | -1 edges. The strategies Edge generation and Community generation create a new edge at each step of the repeat loop, so respectively |E | and |E| -|E | -|N | + 1. As a result, when the strategy S terminates, the number of edges created is equal to |N | -1 + |E | + |E| -|E | -|N | + 1 = |E|.

Figures 5 and 6

 6 are two examples of social networks generated using a sequential composition of the previous strategies. Although both graphs have the same number of nodes and edges (|N | = 100 and |E| = 500), they have been generated with different |E |, respectively |E | = 50 for Fig. 5 and |E | = 0 for

Fig. 5 .

 5 Fig. 5. A generated social network. |N | = 100 nodes, |E| = 500 edges and |E | = 50. With these parameters, the average characteristic path length is L 2.563 and the average clustering coefficient is C 0.426.

Fig. 6 .

 6 Fig. 6. This changes the number of purely random edges created in the resulting graph and explains why the first graph seems to visually present less structure than the other one. Conversely, a graph with only randomly assigned edges could be generated with |E | = |E| -|N | + 1.To ensure that our constructions present characteristics of real-world social networks, we have performed several generations using different parameters and measured the characteristic path length -the average number of edges in the shortest path between any two nodes in the graph -and the clustering coefficient -how many neighbours of a node n are also connected with each other -as defined in[START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. In a typical random graph, e.g., a graph generated using the Erdös-Rényi model[START_REF] Erdős | On the evolution of random graphs[END_REF] or using our method with the parameters |N | = 100 nodes, |E| = 500 edges and |E | = |E| -|N | + 1 = 401, the average characteristic path length is very short (L 2.274), allowing information to go quickly from one node to another, but the clustering coefficient is low (C 0.101), implying the lack of well-developed communities. However, with the parameters used in Figure5(respectively, Figure6), we retain a short characteristic path length L 2.563 (resp. L 3.372) while increasing the clustering coefficient C 0.426 (resp. C 0.596), thus matching the characteristics of small-world graphs: a small diameter and strong local clustering.

Fig. 6 .

 6 Fig. 6. A generated social network. |N | = 100 nodes, |E| = 500 edges and |E | = 0. With these parameters, the average characteristic path length is L 3.372 and the average clustering coefficient is C 0.596.

Table 1 .

 1 Syntax of the Strategy Language.

For instance from http://snap.stanford.edu

Porgy website: http://tulip.labri.fr/TulipDrupal/?q=porgy

Acknowledgements. We thank Guy Melançon (University of Bordeaux) and all the other members of the Porgy project. We also thank the anonymous reviewer for carefully reading this paper and making valuable suggestions for improvement.


Laura Roa Castro12
email: laura.roacastro@irt-systemx.fr

Julie Stal-Le Cardinal2

DEFINITION OF THE COLLABORATIVE SIMULATION SYSTEM (CM&SS) FROM A SYSTEMIC PERSPECTIVE IN VEHICLE INDUSTRY CONTEXT

Keywords: Collaborative design, Organization of product development, Process modelling Collaborative simulation, Systemic approach

During the last decades modelling and simulation technics has grown in importance in the product development context. For example, from an industrial point of view, simulation models seem to be an excellent alternative on vehicle construction and more specifically, in the decision making process. Nevertheless, the simulation activity becomes more difficult with the complexity of the product, highlighting more and more often a collaborative problem on the organization of the product development. But, how can this problem be defined? Several collaborative approaches have been proposed in this field. However, the majority of those approaches concern only one dimension of the problem. This paper introduces the Collaborative Modelling & Simulation System (CM&SS) from a systemic perspective in vehicle industry context. The systemic approach enables the definition of different dimensions of the system aiming at a successful performance of a collaborative simulation.

INTRODUCTION

The present work has been developed in SIM project context (French acronym for Multidisciplinary Simulation and Engineering) at the Research Institute of Technology (IRT) SystemX in partnership with Industrial Engineering Laboratory (LGI) from Ecole Centrale Paris. Since the project has two industrial partners: Renault and Airbus Group, the main framework of this research is related to vehicle construction for both, automotive and aeronautics industries.

Vehicle construction is a complex universe based on real or simulated tests. Simulated tests take part in Modelling and Simulation (M&S) technics, those technics have grown in importance in the last decades in different fields. In aeronautic and automotive industry context, M&S technics, along with packages of documents and applications describing the vehicle at different stages of the development, make part of the virtual representation of the vehicle, also called Virtual Vehicle. A subassembly of it, is the Behavioural Virtual Vehicle: BVV. Since this research is related to both aircrafts and cars, this work states BVV even if the aeronautic industry already refers to as BDA, Behavioural Digital Aircraft (CRESCENDO Consortium Members, 2012).

BVV is obtained by processing elementary objects. This processing is insured by collaborative capacities such as support and organisation. However, those capacities have a value in the organization only if they are performed by a team. The team, the processing of the capacities and the virtual objects (simulation models, documents, applications, etc.) constitute a complex technic society. The need to organize the simulation models, people and capacities is the heart of our research.

Several collaborative approaches have been proposed in modelling and simulation field. Nevertheless, the majority of those approaches concern only one dimension of the problem, such as interoperability problem or monitoring difficulty [START_REF] Castro | An Overview Of Collaborative Simulation On Design Process[END_REF]. In the same work a definition of collaborative characteristics in M&S context was proposed. The present paper introduces the Collaborative Modelling & Simulation System (CM&SS) from a systemic perspective in vehicle industry context. The systemic approach enables the definition of the system from different axis, allowing a better description of the dimensions and highlighting the relationship between them. This approach will favour a successful performance of a collaborative simulation. This document is divided into 4 sections. Section 2 introduces the systemic approach and the CM&SS, Section 3 presents the four main axes of the CM&SS and section 4 is dedicated to conclusions and future work.

COLLABORATIVE MODELLING AND SIMULATION SYSTEM: CM&SS

Since a lot of collaborative M&S works can be found in the literature, and given the variety and the complexity of its definition, it was necessary to find a holistic and extensive approach, convenient to the industrial partners and allowing a characterisation of the collaborative simulation as complete as possible. The systemic approach seems to answer that need. The CM&SS (Collaborative Modelling and Simulation System) proposed in this work is then based on the systemic approach. Subsection 2.1 presents an overview of the systemic approach. Subsection 2.2 presents the CM&SS principles.

Systemic Approach

The traditional systemic approach was proposed by Jean-Louis Le Moigne in his book Approche systémique [START_REF] Le Moigne | Approche systemique[END_REF]. J.L. Le Moigne perceived the complex system as a structure irreducible to an analytic, causality or deterministic model. The complex system is constantly evolving and is defined by four main axes: teleological, genetic, functional and ontological. The teleological axis refers to the objectives of the system. The genetic axis concerns the evolution through time of the system. The functional axis describes the functions of the systems: what the system is supposed to do. Finally, the ontological axis characterization is about the resources of the system. Figure 21 illustrates the vision of the complex system from J.L. Le Moigne.

In 2009, A. Schindler (Schindler, 2009) proposes an adaptation of systemic approach, based on one of the teaching program at Ecole Centrale Paris. This adaptation presents the four axes as a directional method in the construction of a complex system. In addition, once the system has been built, a verification of each item should be done by going backward. A. Schindler adaptation is presented in Figure 12. In order to have a better illustration of the equivalence between both approaches, the four rectangles on Figure 12 point out the four axis proposed by J.L Le Moigne (1990).

The CM&SS: Collaborative Modelling and Simulation System

Based on both approaches, this paper aims at defining a Collaborative Modelling and Simulation System. From this point forward called CM&SS. This section presents the basics of each of the four system axes: teleological, genetic, functional and ontological. Then, in section 3, a deeper presentation of all axes will be done.

Teleological axis defines the environment of the CS&SS and the added value expected from the system. The environment is represented via four features:

 Stakeholders of the system  Organizational stakes  Principal objectives  Perimeter
The added value of a system is usually related to the product or service given by the system. The service supposed to be delivered, in a future, by the CM&SS is related to the orchestration of different elements of the collaborative system in order to have quality solution for the decision maker as soon as possible.

Genetic axis has two main objectives. The first one is the definition of the lifecycle of the system itself. The second one is related to the way of how the system will evolve in the future. For now, the work is concentrated on the definition of the lifecycle of the CM&SS. The functional axis of the CM&SS is supported by the definition of the valued-added collaborative process. The process is linked to indicators in order to manage the collaboration and to have a return of experience.

Finally, the ontological axis refers to the means and resources of the systems, it could be material or human. The materials resources of the CM&SS are related to the IT platform as a system support. The human resources refer to the actors who act on the system.

The CM&SS from a systemic point of view is represented in Figure 3. The bold arrows represents the links between the different axes. Those links refine the description of the system, making its interest clear and improving its comprehension. The links can be understood as follow: The CM&SS aims at processing of the simulation artefact (virtual object). The processing is carried out taking into account the organizational stakes, the perimeter of the system and the stakeholder points of view.

The execution of the CM&SS is done by the human resources (actors). The actors make part of the stakeholder. Their skills allow the construction of the simulation artefact. This construction keep their Knowledge print on it. In addition, they make part of a big network, involving important relationships.

The execution, the sharing and the control of the CM&SS is founded on collaborative process. Those process support the added value creation by means of IT tools. As mentioned in subsection 2.2 the environment of the CM&SS is represented via four features. This subsection is dedicated to the explanation of those characteristics.

CM&SS AXES

Teleological axis

The stakeholders

Because the simulation practice helps in the decision making process and the decision are taken by people, the most important part of the system environment are the stakeholders. At the end, a success collaborative simulation serves to decision maker. An analysis has been done aiming at finding the principal stakes and attended values of the stakeholders. This analysis was built on the work of (Roa [START_REF] Castro | Actor based design for a Collaborative Modelling and Simulation System[END_REF] and is briefly presented in this paper.

Considering different interpretations of stakeholder and system actors, two definition founded on the literature are settled for this research so as to avoid misunderstanding of their meanings.



Stakeholders: Individuals and groups who affect or are affected by organizations' actions. [START_REF] Smudde | A holistic approach to stakeholder management: A rhetorical[END_REF])  Actor: anything with behaviour that acts on the system. A primary actor initiates interaction to achieve goal. A supporting actor: performs sub-goals to help use case [START_REF] Cockburn | Writing Effective Use Cases[END_REF] In CM&SS context, the actors will be referred as a human resources of the system. Likewise, in this case the actors of the CM&SS make part of the stakeholders but all the stakeholders are not necessary actors.

The choice of the stakeholders of CM&SS was done regarding Renault and Airbus Group organisation. Both companies have a hierarchical structure for their engineering department. Moreover, they both implement a matrix organization for a given programme (e.g. A320 program). For the engineering department, this organization means that some of their people will work a limited quantity of time for a given program. The program organization has a particular structure for the simulation process. [START_REF] Sirin | Value creation in collaborative analysis model development process[END_REF] Propose three view points for the detailed model design phase: System architect, model architect and model supplier. Those points of view correspond a three roles in the organization program. Figure 4 from [START_REF] Castro | Actor based design for a Collaborative Modelling and Simulation System[END_REF] illustrates the matrix organization and the main roles.

The cross in the table illustrate the simulation organization for a given program. Program organization is temporary, whereas engineering organization is longer-lasting. The simulation requirements for a program are fulfilled by calling people from engineering organization. Then, people that usually works in different engineers department is summoned to work together during the program. A detailed definition of the stakeholder, their values and their stakes in the CM&SS can be found in the same work.

Organizational Stakes

A general context of the organization objectives concerning CM&SS have been defined. The reference organizations for this research are Renault and Airbus Group. Those stakes were established by a common agreement during some project meetings.

The main stake is related to the development of a vehicle such as aircraft or a car by processing elementary objects by which the BVV (Behavioural Virtual Vehicle) is obtained. This development requires, amongst others, the collaboration of different engineer's teams. The collaborative capacities such as support and organisation insure the processing of the elementary objects. The team, the processing of the capacities and the virtual objects (simulation models, documents, applications, etc.) constitute a complex technic society. Bold captions in Figure 5 represent the three main elements of interest for the organization. The principle need will be the organization of the simulation models (objects), people and capacities in a vehicle development.

Principal Objectives

The principal Objectives are mainly related to the project. SIM project has a very specific needs and is the frame of reference of this research. The existence of SIM project can be explained by using two categories: -Need to provide end to end collaborative process and tools, from the conception of the model architecture until the results analysis. -Need of a unified framework for model sharing (exchange process, a common management model including configuration management, common representation standards, co-simulation standards).

Perimeter

Since modelling and simulation technics are practiced in different development phases, the choice of one or two interest phases helps to focalized the research. From this point forward it will be very important to make the difference between the product lifecycle, simulation lifecycle and simulation process.

At Airbus Group and Renault industries, the term product lifecycle, makes reference to the complete life cycle of the product, from the first idea until product removal and is represented by the upper chevron illustration in Figure 6. In the other hand, the term simulation lifecycle, in the same context, is associated to simulation models evolution through product lifecycle. For example, in phase 0 (Need identification and mission analysis) the simulation models are less detailed and precise that in phases C (Detailed definition). The simulation lifecycle is represented by the bottom chevron illustration in Figure 6.

Finally, the term simulation process is related to the activities needed for models creation. Those activities are represented by a V cycle. Several V cycle are illustrated in Figure 6 because the models created throughout different phases are not the same but they all created based on the same process



The potential collaborative gain: A collaborative interest comes when two or more entities are presented [START_REF] Bedwell | Collaboration at work: An integrative multilevel conceptualization[END_REF]. As long as more and more people participate, more collaborative actions will be required. The very early phases of the development process (Phases 0 and A) concern less people and then the characteristics related to collaboration, such as communication, interaction and awareness, are easier to handle.



The industrials needs: The engineering teams dedicated to simulation development in very early phases (0 and A) at Airbus Group and at Renault are about ___ and ___ respectively. However, the number of people dedicated doing the same task in phases B and C are about __ and __. Collaborative stakes seems more interesting in phases B and C (preliminary definition and detailed definition).

According to those three factors, the CM&SS will be developed by centring the attention on phases B and C, regarding carefully the variation of the collaborative process between different phases.

Genetic Axis

As explained in sub-section 2.2. Even if genetic axis has two main objectives. For now, the work was concentrated on the definition of the lifecycle of the CM&SS.

Simulation process is common expressed by using a V cycle diagram, some example can be found in the system and software engineering and systems and lifecycle process standard (Standard: ISO/IEC 15288:2008 , 2008). Figure 7 presented below, proposes an adaptation of the standard to the simulation process. The variation regarding other adaptations presented before (ProSTEP iViP, 2014) or [START_REF] Sirin | Value creation in collaborative analysis model development process[END_REF] is the difference made between the system level and the model and simulation level, already proposed by [START_REF] Chen | Architecture framework associated to vehicle architecture definition[END_REF] and the inclusion of the main stakeholders. In addition. The circles on the figure highlight the main adaptation regarding the standard ISO15288.

Functional axis

This axis is focused on the creation of the added-value collaborative process and the indicators linked to the process allowing collaboration management and retour of experience.

Process

Two main process are of the special interest of the system: modelling and simulation process and collaborative process for modelling and simulation. Modelling and simulation process concerns the development of the model itself. This process was identified from several workshops at Renault

Company. An outline is presented in [START_REF] Castro | An Overview Of Collaborative Simulation On Design Process[END_REF]. From this work, a summary of industrial needs on collaborative work in M&S domain was presented.

The collaborative process for M&S, will be defined in future work using coming industrial audits

Indicators

Once the process will be proposed, some indicators will be defined concerning mainly: the management of the collaboration process and the retour of the experience. This indicators will be determined regarding also the expected values of the stakeholders.

Ontological axis

As explained before, ontological axis is related to the resources of the system. CM&SS has two kind of resources: human resources and material resources. A concisely description is presented in subsection 3.4.1 and 3.4.2 respectively.

Human Resources

The human resources of the CM&SS can also be called the actors of the system. As defined on section 3.1.1, an actor will be the person acting on the system. The primary actors of the CM&SS will initiate the collaboration to achieve a goal. The supporting actor will perform sub-goals to help according with the global objective. The notion of primary and supporting actor has been proposed by [START_REF] Cockburn | Writing Effective Use Cases[END_REF]. Another important mention in CM&SS is the relationship between an actor and a stakeholder. The actors of the CM&SS make part of the stakeholders but all the stakeholders are not necessary actors.

For the moment, we propose three main attributes of the actors: their relationship, skills and knowledge.

The relationship: The relationship of the actors will be extremely related to their main stakes. This attribute is also associated to some collaborative features such as team cooperation, coordination, communication interaction and awareness. A deeper description of those features is proposed in the literature by [START_REF] Bedwell | Collaboration at work: An integrative multilevel conceptualization[END_REF] and [START_REF] Salas | Team work: emerging principles[END_REF].

Skills and knowledge features are closely linked to Modelling and simulation problem.

The skills: An evaluation of the skills concerning the persons within organization, will be necessary in order to define the actors of the CM&SS because modelling and simulation process requires a very specific expertise according to the system to be developed.

The knowledge: this attribute constitute a key point for the simulation organization because of two main reasons: First, a model is a representation of a system, used to understand the reality (behaviours), built on a solid scientific basis. The scientific basis makes reference to the skills. The understanding of the behaviours makes reference to the knowledge put in the model as fingerprint. A model externalizes the comprehension of a system, revealing the potential scientific clues. This leads also to the second reason: the intellectual property (IP) constraints. When the model exchange takes place in the extended enterprise, IP problem regarding the disclosure of specific contents is more delicate. Some approaches as a withe, grey and black box has been proposed aiming at the protection of this knowledge. [START_REF] Lee | The Middle-out Systems Engineering for Gay-Box[END_REF].

Material Resources

In the future, CM&SS will be supported by an IT platform, this application should materialize the concepts developed during the research and will be tested by the partners of the project: Renault and Airbus Group.

CONCLUSION AND FUTURE WORK

The systemic approach presented in this paper permits the characterization of the Collaborative Modelling and Simulation System (CM&SS) and allows us to succeed in a global vision of the system.

By adapting the traditional systemic approach to this research, four main axes of CM&SS have been introduced (teleological, genetic, functional and ontological). The four axes have been split in elementary items related to our system, the systemic approach highlights the relationship between them, giving us a complete vision of what the CM&SS should be.

The Systemic representation of the CM&SS in Figure 3, introduced in subsection 2.2 shows the complete system. Figure 8 presented below, is focused on the main elements of the system and their relationship.

Those elements have been chosen under interconnection criteria, that is, the elements interconnected from different axis. From this figure, we conclude that: the CM&SS is an actor based methodology, aiming at the performance of a simulation object (simulation artifact), supported by added-value collaborative process implemented through an IT platform. It will be developed by focusing on phases B and C of the product development (B: preliminary definition. C: detailed definition). But regarding carefully the variation of the collaborative process between different phases. The orchestration of different elements of the system will lead to a quality solution for the decision maker as soon as possible.

Future work will be emphasized first, in the definition of added-value collaborative process and its indicators, regarding the simulation artifact and the human recourses (Actors) description. We also plan to study in depth, the actors, since CM&SS will be an actor based system, their relationship, knowledge and skills that deserved to be widely considered. In a second time, an IT platform will be proposed based on the methodology.

Figure 21 :

 21 Figure21: Systemic Approach (Schindler, 2009) and correspondence with systemic approach (Le Moigne, 1990) Figure12: Systemic Approach.[START_REF] Le Moigne | Approche systemique[END_REF]

Figure 3 :

 3 Figure 3: Systemic representation of the Collaborative Modelling and simulation System CM&SS

Figure 4 :

 4 Figure 4: Matrix organization, stakeholders and actors

Figure 6

 6 Figure 6 represents the three lifecycles that this research deals with: product lifecycle, simulation lifecycle and simulation process. Regarding all the phases, the scope of this research has been defined taking into account three factors and is delimited by the circle in Figure 6 :  The gap in the literature: This gap evidenced in the work done by (Roa Castro & Stal-Le Cardinal, 2014) suggest a positioning of the research in the early product development phases (before fabrication) in others words, phases 0, A,

Figure 6 :

 6 Figure 6: Research perimeter according to product development and simulation phases

Figure 7 :

 7 Figure 7: Simulation process

ACKNOWLEDGMENTS

This research work has been carried out under the leadership of the Technological Research Institute SystemX, and therefore granted with public funds within the scope of the French Program "Investissements d'Avenir". Furthermore, we wish to express our esteem and sincere acknowledgement to colleagues in IRT SystemX for their encouragement, friendship moral support and their scientific assistants for all the time.