Olivier Corby

Catherine Faron-Zucker

Fabien Gandon

LDScript: a Linked Data Script Language

Keywords: Script Language, Semantic Web, Web of Data, SPARQL Language de script, Web sémantique, Web de données, SPARQL

In addition to the existing standards, Web of Data programmers would take advantage of a dedicated programming language enabling them to define functions on RDF terms, triples and graphs as well as SPARQL query results. In particular, this is the case when defining SPARQL extension functions, and the ability to capitalize complex SPARQL filter expressions into extension functions or to define and reuse dedicated aggregates would support modularity and maintenance of the code. Another use case is the definition of functional properties associated to RDF resources and the definition of procedural attachments as functions assigned to RDFS or OWL classes with the selection of the function to be applied to a resource depending on the type of the resource. To address these needs we define a Linked Data Script language on top of the SPARQL filter expression language. We provide the syntax and the semantics of the LDScript language.

Introduction

RDF is the standard model recommended by the W3C to represent and interchange data on the Semantic Web. It is associated with RDF Schema and/or OWL for ontology-based data modelling and SPARQL for data and ontology querying. The development of the Web of data opens up a wide range of use cases where, in addition to the existing standards, the Semantic Web programmer would take advantage of a dedicated programming language enabling her to define functions on RDF terms or RDF graphs. This is the case, for instance, when defining SPARQL extension functions implemented for a special purpose and domain or application dependent. This would also be needed to capitalize a complex SPARQL filter expression or the definition of special purpose extension aggregates to be reused across queries or sub-queries. Another kind of use cases is the definition of functional properties associated to RDF resources, the results of which are computed on demand. For instance, the value of the surface property of a rectangular object could be computed as the product of the values of its width and length properties; the age of a person could also be computed from her date of birth. These use cases can also be extended to the definition of procedural attachments as functions assigned to RDFS or OWL classes. The selection of the function to be applied to a resource can then be made dependent on the types (classes) of the resource.

The requirements we propose for a programming language enabling such definitions of functions are:

• The objects of the language are RDF terms (URI, blank node and literal), RDF triples, RDF graphs, SPARQL solution mappings and lists of such objects.

• The statements of the language include SPARQL filter expressions and SPARQL queries (the select and construct query forms and the service clause).

• The language provides function definition and function call on lists.

In this paper, we address the research question: Can we define a standardbased programming language that meets the above described requirements?

To answer this question, we define a Linked Data Script language on top of the SPARQL filter expression language, taking advantage of the fact that the SPARQL filter expression language potentially enables users to express function definitions. We then proceed to define a programming language on top of SPARQL filter expression language.

Syntactically, it consists in additional statements: a function statement enabling users to define functions and a let statement enabling him to introduce local variables in the filter language.

We call our extension LDScript, standing for Linked Data Script, as it consists in providing the Linked Data with a script language. We present the syntax and semantics of LDScript as well as an implementation and we illustrate the simplicity as well as the expressive power of this extension with some examples of LDScript functions.

This paper is organized as follows: In Section 2 we present state-of-the-art approaches to define extension functions. In Section 3 we present an overview of LDScript. In Section 4 we define the syntax and semantics of LDScript. In Section 5 we present several use cases and we show how they can easily be addressed by using LDScript. In Section 6 we present our implementation of LDScript within the Corese Semantic Web Factory. In Section 7 we conclude and draw some perspectives of our work.

Related work

SPIN is a W3C member submission which proposes a SPARQL-based rule and constraint language and, additionally, enables one to represent both SPARQL queries (SPIN templates) and SPARQL extension functions (SPIN functions) [START_REF] Knublauch | SPIN -SPARQL Syntax[END_REF]. SPIN is represented in RDF. In SPIN, a SPARQL extension function is identified by a resource of type sp:Function (with sp the prefix denoting the SPIN namespace) which is linked by property sp:body to its definition as a SPARQL query of the form select or ask.

Jena provides a java URI scheme for naming and accessing SPARQL extension functions implemented in Java. This enables one to dynamically load the bytecode implementing the function. By convention, the location of the Java class must be found in the Java classpath and the local name of the function must be the name of the Java class implementing it1 . Here is an example of a SPARQL query using the f:myTest extension function implemented in Java and enabling to filter the RDF triples matching the triple pattern to those for which a call to function f:myTest with the values bound to their subject and object as parameters returns true: PREFIX f: <java:app.myFunctions.> SELECT ?x WHERE { ?x ?p ?y FILTER f:myTest(?x, ?y) } A proposal to implement SPARQL extension functions in JavaScript as an agreed-upon programming language and to share implementations among query engines by using an embedded JavaScript interpreter is described in [START_REF] Williams | Extensible SPARQL Functions With Embedded Javascript[END_REF]. Functions are identified by URLs and their source code may be retrieved at run time by dereferencing their URL. It relies on an RDF schema enabling one to describe a SPARQL extension function and retrieve its source code at run time by dereferencing its URL. Here is an example of RDF statements describing a SPARQL extension function to compute a geographical distance in kilometers. The location of its JavaScript source code is the value of property ex:source (with ex the namespace prefix of the extension function schema) and the function name in the source code that should be called to execute the extension function is the value of property ex:function. <http://example.com/functions/distance> a ex:Function; dc:description "Geographic distance in km"; ex:source <http://example.com/distance.js>; ex:function "gdistance" .

A proposal to implement SPARQL extension functions based on both a generic extension function wfn:call and the SPARQL service clause is described in [START_REF] Atzori | Toward the Web of Functions: Interoperable Higher-Order Functions in SPARQL[END_REF]. Function wfn:call is similar to the Lisp funcall function and takes the extension function to be evaluated as its first argument. Any occurrence of the wfn:call function is replaced by a service call to delegate the evaluation of the extension function to the SPARQL endpoint implementing the function. The SPARQL endpoint's IRI is computed from the extension function's IRI, based on a Function-to-Endpoint IRI pattern.

When compared to these four state-of-the-art proposals, the key idea of our proposal described in the following is to extend the SPARQL language, and more precisely its filter language, in order to enable the definition of extension functions in the SPARQL language itself and using its native syntax.

Overview of LDScript

Our goal is to define functions the objects of which are Linked Data entities (e.g. URI, RDF Literal, RDF triple, etc.) with the main objective of defining SPARQL extension functions and possibly extend SPARQL itself.

One possibility is to rely on an existing programming language, e.g. Java, and use the API of the SPARQL implementation of the RDF entities. However, this approach has several weaknesses. First, it is not interoperable because other SPARQL implementations of RDF entities do not use the same API. Hence, the functions cannot be reused by other SPARQL implementations. Second, one does not benefit of SPARQL native function library dedicated to RDF terms: isURI, isBlank, isLiteral, datatype, strdt, strlang, langMatch, uri, bnode, etc. Third, one must switch back and forth from SPARQL to Java environments with their compiler, project management environment, etc. and link the compiled functions to the SPARQL interpreter.

Another possibility would be to design a specific programming language the object of which would be RDF entities with a library implementing SPARQL functions. The weakness of this approach would be that users would have to learn yet another programming language.

We propose LDScript, a third way that synthetize these two approaches: a programming language the objects of which are RDF entities, compatible with SPARQL and embedding the complete SPARQL function library.

LDScript primarily relies on the SPARQL filter expression language. A SPARQL filter is either (a disjunction or conjunction of) a relational expression or a call to a built-in or externally defined boolean function. Among the builtin SPARQL functions stands the if ternary function which evaluates the first argument and returns the value of the second argument if the first argument results in an effective value of true, or else the value of the third argument. A SPARQL filter restricts the solutions of a graph pattern matching to those satisfying the constraint it expresses: the filtered solutions result in the boolean value true when substituted into the filter expression.

We propose to define functions by taking advantage of the fact that the SPARQL filter language enables users to define expressions. Handbooks of programming languages and programming history explain that typical imperative languages include as commands: variables declaration, assignment, call, return, sequential blocks, iterative commands and if statements. For this reason, in this section we will introduce the corresponding statements in LDScript. Here are the namespaces and prefixes used in the definitions: prefix xt: <http://ns.inria.fr/sparql-extension/> prefix us: <http://ns.inria.fr/sparql-extension/user/> prefix rq: <http://ns.inria.fr/sparql-function/> prefix dt: <http://ns.inria.fr/sparql-datatype/> prefix ex: <htp://example.org/>

LDScript Function Definition

In LDScript, a function definition starts with the function keyword. The first argument of the declaration is the name (a URI) of the function being defined followed by its argument list. The variables in the argument list play the usual role of function arguments. The second argument is the body of the function being defined. It is a LDScript expression or a sequence of expressions. For example, the factorial function us:fac is defined as follows, by using the SPARQL if built-in function and embedding a recursive call: A call to a defined function returns the result of the evaluation of its body, with its arguments bound by the function call. In the body, the arguments are Inria local variables in the sense that the variable bindings are local to the body of the function and exist only during the execution of the function. For instance, according to its above definition, a call to function us:fac will return the value returned by a call to the if SPARQL built-in function form with a given value for variable ?n.

The language for defining the body of a function is LDScript, i.e. the SPARQL filter expression language extended with statements presented in this document. Hence, to define extension functions, LDScript programmers can make use of the expressivity of the whole SPARQL filter expression language. In particular, this includes built-in SPARQL functions, among which the if function form enabling to consider alternatives, and the exists statement to test graph patterns. This also includes extension functions defined in LDScripts or externally defined in another language (as SPARQL allows it).

At compile time, the function statement triggers the storage of the declared function in a table together with the number of its arguments. The same name can be used to declare different functions with different numbers of arguments. Later on, this table enables the LDScript interpreter to retrieve the function definition at runtime for a function call. For example, the SPARQL query below is followed by the definition of function us:fac and the WHERE clause embeds a call to this function to search the resources whose income is greater or equal to 10! = 3,628,800.

SELECT ?x ?i WHERE {

?x ex:income ?i FILTER (?i >= us:fac(10)) } FUNCTION us:fac(?n) { IF (?n = 0, 1, ?n * us:fac(?n -1)) }

Local Variable Declaration

LDScript function definitions can embed local variable declarations. These are expressed in a let statement. Its first argument declares a local variable and its value. Its second argument is an expression which is evaluated with the transient binding of the local variable declared. After completion of the expression evaluation, the binding vanishes. The result of a let statement is the result of its second argument. For instance, the example below shows a let statement that returns the pretty-printing of a date, e.g. "29/01/2017".

LET (?n = now()) { CONCAT(day(?n), "/", month(?n), "/", year(?n)) }

Loop Statements

In order to iterate a statement on the elements of a list of values, LDScript is provided with the for loop statement. For instance the following function iteratively calls the xt:display function on the prime numbers among a given list of natural numbers. The for statement can iterate on the results of a SPARQL select or construct query. In the case of a construct query, it iterates on the triples of the graph. For instance, the following function iteratively calls the xt:display function on RDF triples of the form <URI> a foaf:Person.

FOR (?t IN CONSTRUCT WHERE { ?x a foaf:Person }) { xt:display(?t) }

The for statement can also bind a list of variables to a list of lists of values. In the case of the result of a construct query, the for statement can bind the subject, property and object of each triple to a list of three variables, like in the following example statement.

FOR ((?s, ?p, ?o) in CONSTRUCT WHERE { ?x a foaf:Person }) { xt:display(?s, ?o) }

Function Evaluation

LDScript is provided with the funcall function to call a function whose name is dynamically evaluated within a let statement. For instance, the following let statement enables to apply a function to a variable ?x, whose body is randomly chosen.

LET (?fun = IF (rand() > 0.5, us:foo, us:bar)) { funcall(?fun, ?x) } LDScript is provided with the apply function to iteratively call a binary function on a list of arguments. For example, the following function call enables to compute the sum of the elements of a list of numbers with the binary rq:plus function.

apply(rq:plus, xt:list(1, 2, 3, 4, 5)) Inria

List Datatype

LDScript is provided with a dt:list datatype to manage lists of values. A dt:list datatype value is a list whose elements are RDF terms: URIs, literals, blank nodes or sublists of type dt:list. The elements of a list need not be of the same kind, neither of the same datatype. The dt:list datatype comes with a set of predefined functions among which xt:size returns the size of the list, xt:get returns the n th element, xt:sort sorts the list according to the order by rules of SPARQL, xt:iota returns the list of n first integers, xt:cons adds an element to the head of the list, etc.

The maplist function enables one to apply a function to the elements of a list and return the list of the results. For instance, the call to function maplist shown below returns the list of the results of the calls to function us:fac on the first ten integers.

maplist(us:fac, xt:iota(10))

There are several variants of the maplist function: map applies a function and returns true, mapselect returns the list of elements such that the boolean function returns true.

LDScript Language

The previous section gave an overview of LDScript. In this section we formally define the syntax and semantics of this language.

LDScript Syntax

LDScript grammar is based on SPARQL 2 . The definition of BuiltInCall is extended with let, for, map, funcall and apply statements.

LDScript Semantics

As usually done for programming languages, we formally defined the semantics of the core of LDScript by a set of Natural Semantics inference rules [START_REF] Kahn | Natural Semantics[END_REF]. These rules enable us to define the semantics of the evaluation of the expressions of the language in an environment with variable bindings. The bottom of the rule is the conclusion and the top is the condition. The symbol states that the expression on the right side is evaluated in the environment given on the left side. The → symbol represents the evaluation of the expression on the left side into the value on the right side. An environment is a couple (µ, ρ) where µ is the BGP solution mapping and ρ represents local variable bindings. In addition, the environment contains a reference to the SPARQL dataset.

Rule 1 states that local variables are evaluated within ρ which is managed as a stack, latest variable binding first; rule 2 states that global variables are evaluated within µ which is a BGP solution.

Rules 3 and 4 specify the evaluation of function calls. The ⇒ symbol represents a function definition lookup for the function name on the left side. The solution mapping environment is empty during function body evaluation: there are no global variables. Each function call creates a fresh environment with function parameters (if any) as local variables.

Rule 5 specifies the evaluation of the let clause which declares a local variable to be added to environment ρ. Hence, a declared local variable may hide a function parameter or a BGP variable. BGP variables are accessible in a let statement (e.g. in a filter), unless the let statement is inside a function, in which case the µ environment is empty.

Rule 6 specifies the evaluation of the f or statement by evaluating the first expression that returns a list of values and then binds the variable successively with each element of the list and evaluates the second expression with each local binding. The result of the for statement is always true by convention.

Rules 7, 8, 9, 10, and 11 specify map, eval and apply statements. Rule 12 specifies the evaluation of an LDScript expression. The semantics is that of standard SPARQL expression evaluation, except that the overall environment comprises an environment for local variables in addition to the standard environment for BGP variables.

µ, ρ[x = v] x → v (1) x / ∈ ρ µ[x = v], ρ x → v (2) f () ⇒ f () = body ∧ φ, φ body → res µ, ρ f () → res (3) Inria f (e 1 , ... e n ) ⇒ f (x 1 , ... x n ) = body µ, ρ e 1 → v 1 ... µ, ρ e n → v n φ, [x 1 = v 1 ; ... x n = v n ] body → res µ, ρ f (e 1 , ... e n ) → res (4) µ, ρ e 1 → v 1 ∧ µ, ρ [x = v 1 ] e 2 → res µ, ρ let(x = e 1 , e 2 ) → res (5) µ, ρ e → (v 1 , ...v n ) µ, ρ [x = v 1 ] b → r 1 ... µ, ρ [x = v n ] b → r n µ, ρ f or(x = e, b) → true (6) µ, ρ e → (v 1 , ..v n ) µ, ρ f (v 1 ) → r 1 .. µ, ρ f (v n ) → r n µ, ρ map(f, e) → true (7)
µ, ρ e → f ∧ µ, ρ f (e 1 , ..e n ) → v µ, ρ f uncall(e, e 1 , ..e n ) → v (8) µ, ρ e → (v 1 , ..v n ) µ, ρ apply(f, (v 1 , ..v n )) → v µ, ρ apply(f, e) → v (9) µ, ρ f () → v µ, ρ apply(f, ()) → v (10) µ, ρ apply(f, (v 2 , ..v n )) → r µ, ρ f (v 1 , r) → v µ, ρ apply(f, (v 1 , ..v n )) → v (11) sparql(µ, ρ exp → v) µ, ρ exp → v (12)

Summary

LDScript is a programming language where values are RDF terms, hence its use to define extension functions avoids to cast datatype values from RDF to the target language (e.g. Java) and back. It enables to associate function definitions directly to a SPARQL query, with no need to compile nor link code.

All standard SPARQL functions, among which IF and EXISTS, are natively available in LDScript and can be used directly in a LDScript function definition. The select and construct SPARQL query forms, the SPARQL service clause are statements of the LDScript and can be used as well in the definition of functions. The result of these statements can also be manipulated directly in the language without any cast or additional operations. In addition, the language provides recursion, hence enabling recursive SPARQL queries: a function can execute a SPARQL query that can call the function.

Use Cases

In this section, we present the definition of several LDScript extension functions showing the expressive power and usability of the language. Some additional examples can be found at: http://ns.inria.fr/sparql-extension such as calendar functions that enable one to compute the week day of a date and a converter from decimal to Arabic numbers and reverse.

Extended Aggregates

LDScript enables us to simply define extended aggregates with a simple extension of the SPARQL interpreter. We introduce the aggregate function which is an additional generic aggregate operator. This function takes as arguments the expression to be aggregated (e.g. ?v). The aggregate function aggregates the results of the expression into a dt:list. Then we can call a custom aggregation function with this list as argument. The example below defines sort concat, a variant of the group concat aggregate which sorts the elements before concatenation occurs. The rq prefix and namespace are used to assign a URI to each SPARQL standard function, hence rq:concat function is SPARQL concat function. Hence LDScript enables users to define inline custom aggregates for SPARQL.

SELECT

Application-specific processing

Another use case of LDScript extension functions is user-defined calculation such as metrics for approximate matching. We defined the us:match extension function which definition is given in the following SPARQL query where ?q and ?t are two RDFS classes. Given a triple pattern with property rdf:type and Inria a type, i.e., a class (e.g. ex:Researcher), a type in an RDF triple matches the type in the triple pattern when it is a subtype of it (line (09) emulates class subsumption by using a path of properties rdfs:subClassOf), but also when it is a supertype of it (line 10), or when it shares a common supertype (line 11). For instance ( EXISTS { {?t rdfs:subClassOf* ?q } UNION (10) { ?q rdfs:subClassOf* ?t } UNION (11) { ?q rdfs:subClassOf/^rdfs:subClassOf ?t }}) (12) } This kind of approximate matching could be coded in standard SPARQL, without extension function, but the interest to write a LDScript extension function is to define it once and reuse it across queries.

Procedural Attachment

LDScript enables users to perform procedural attachment to RDF resources. The idea is to annotate the URI of a function to declare that it is a method associated to a class. In the example below, we annotate two functions computing surfaces, us:surfaceRectangle and us:surfaceCircle and declare that they implement the method us:surface for us: Then, we can call a method on a resource.

These two exampes shows the natural integration of SPARQL queries into LDScript program. In particular LDScript variables are seamlessly shared with SPARQL variables.

Implementation and test

LDScript is implemented using the SPARQL interpreter of the Corese Semantic Web Factory [START_REF] Corby | KGRAM Versatile Data Graphs Querying and Inference Engine[END_REF][START_REF] Corby | The KGRAM Abstract Machine for Knowledge Graph Querying[END_REF]. The function, let and other statements are implemented by the SPARQL parser, compiler and interpreter. For the LDScript compiler, function definitions are recorded, taking into account the fact that the same function name can be used with different numbers of arguments. The notion of local variable is defined.

Should an error occur, function evaluation resumes in error mode, on the same model as SPARQL evaluation error. In a filter, the filter fails. In a select or a bind clause, "if the evaluation of the expression produces an error, the variable remains unbound for that solution but the query evaluation continues"7 .

Figure 1: Comparison of mean times and their mean absolute differences for JavaScript (JS), Java and LDScript (LDS) computing recursive Fibonacci (-Fib in Blue), Bubble sort (-Bub in green) and statistics (-Stat in red) using a logarithmic scale.

LDScript has been validated on the functions described in Section 5 and extensively used in several STTL transformations on a server available online8 [START_REF] Corby | STTL: A SPARQL-based Transformation Language for RDF[END_REF][START_REF] Corby | A Generic RDF Transformation Software and its Application to an Online Translation Service for Common Languages of Linked Data[END_REF]. We measured the performance of our implementation of LDScript on the execution of (1) a recursive Fibonacci function to test an exponential number of calls, (2) on the Bubble sort algorithms to evaluate loops and (3) on statistics functions for the calculation aspect. We compared with Java and Javascript implementations which, of course, benefit from many years of optimizations. Our goal here is just to show that a direct implementation on top of a SPARQL engine without dedicated optimizations is already usable. The results are shown using a logarithmic scale in figure 1. The extension function fib implements the Fibonacci sequence. The computation of fib(35) = 9227465 on a HP EliteBook laptop takes 3650 ms in LDScript, 68.8 ms in JavaScript and 24.9 ms in Java. Bubble sort on an array of 1000 items takes 580.1ms in LDScript, 6ms in JavaScript and 9.5ms in Java. Three statistics functions together (average, median and standard deviation) on an array containing 100000 integer values takes 157.1 ms in LDScript, 80.5 ms in JavaScript and 6.9 ms in Java.

Conclusion and Future Work

Dedicated programming language enabling Semantic Web programmers to define functions on RDF terms, RDF graphs or SPARQL results can improve modularity, reuse and maintenance of the code produced for Linked Data. This is the case when defining SPARQL extension functions, complex SPARQL filter expressions, functional properties associated to RDF resources and procedural attachments as functions assigned to classes. To address these needs we detailed in this article a lightweight extension of SPARQL filter expression language to enable the definition of extension functions and we defined a Linked Data Script language on top of the SPARQL filter expression language. Compared to state-of-the-art we directly extend the SPARQL language in order to enable the definition of extension functions in the SPARQL language itself and using its native syntax, building on a well-known and widely accepted component of the Web of data. The key point of our proposal is that a programming language can easily be integrated in SPARQL to define extension functions. LDScript reuses the language of SPARQL filter expressions and extends it with several classical programming statements, among which function, let, for, eval and apply. We first provided an overview of the LDScript language and then we detailed the formal definition of the grammar of its syntax and the Natural Semantics inference rules of its semantics. We also provide a full implementation in the Corese Semantic Web Factory and we have developed a set of functions to validate our approach, some example of which were presented in this article.

As future work, we plan to investigate the notion of "Linked Functions" and go further in the definition of a functionnal programming language for SPARQL. We may consider type checking function definition to ensure a certain level of safety. We may also consider compiling functions into target programming languages such as Java.

  FUNCTION us:fac(?n) { IF (?n = 0, 1, ?n * us:fac(?n -1)) } Here is a another example of function definition. A call to the us:status function returns the status of the resource given as parameter. Its definition uses the SPARQL built-in if function and exists operator.

  FUNCTION us:status(?x) { IF (EXISTS { ?x a foaf:Person }, ex:Human, ex:Thing) }

  FOR (?n IN xt:list(1, 2, 3, 4, 5)) { IF (us:prime(?n)) { xt:display(?n) } }

  Function ::= 'function' iri ('()' | VarList) Body Body ::= '{' '}' | '{' Expression (';' Expression)* '}' VarList ::= '(' Var (',' Var)* ')' BuiltInCall ::= SPARQL_BuiltInCall | 'let' '(' Decl (',' Decl) * ')' Body | 'for' '(' VarOrList 'in' ExpQuery ')' Body | Map '(' iri ',' Expression ')' | 'funcall' '(' Expression (',' Expression)* ')' | 'apply' '(' iri ',' Expression ')' Decl ::= VarOrList '=' ExpQuery VarOrList ::= Var | VarList ExpQuery ::= Expression | SelectQuery | ConstructQuery | ServiceGraphPattern Map ::= 'map' | 'maplist' | 'mapselect' 2 http://www.w3.org/TR/sparql11-query/#grammar RR n°8982

FUNCTION

  us:fib(?n) { IF (n <= 2, 1, us:fib(?n -2) + us:fib(?n -1)) }

  line 05), ex:Person and ex:Engineer will match ex:Researcher if ex:Researcher is declared as a subtype of ex:Person in the ontology, and both ex:Researcher and ex:Engineer as subtypes of ex:Scientist.

	(01) SELECT * WHERE {
	(02)	?x a ?tx .
	(03)	?x ex:author ?d .
	(04)	?d a ?td
	(05)	FILTER us:match(ex:Researcher, ?tx)
	(06)	FILTER us:match(ex:Report, ?td)
	(07) }
	(08) FUNCTION us:match(?q, ?t) {
	(09)

  Rectangle and us:Circle respectively.

	us:surfaceRectangle a xt:Method ;
	xt:name us:surface ;
	xt:input (us:Rectangle) ;
	xt:output xsd:double .
	us:surfaceCircle a xt:Method ;
	xt:name us:surface ;
	xt:input (us:Circle) ;
	xt:output xsd:double .

RR n°8982

https://jena.apache.org/documentation/query/writing functions.html Inria

http://ns.inria.fr/sparql-extension/calendar

http://corese.inria.fr/srv/template?transform=st:calendar Inria

http://corese.inria.fr/srv/template?profile=st:calendar3

http://ns.inria.fr/sparql-extension/datashape RR n°8982

http://www.w3.org/TR/2013/REC-sparql11-query-20130321/#assignment

http://corese.inria.fr Inria

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

SELECT * (eval(xt:method(us:surface, ?x), ?x) as ?m) WHERE { ?x a us:Figure }

The xt:method function below retrieves function ?fun implementing method ?m by finding the type ?t of the resource (04) and then finding a method attached to the type, or a superclass of the type (05). In the latter case, this implements method inheritance following the rdfs:subClassOf relation.

Calendar

We wrote LDScript functions to compute the day of the week given a date literal of type xsd:date 3 and functions to generate a calendar given a year 4 . We designed a dynamic Web page generated from DBpedia events were events of a given year are placed into the calendar 5 . The performance of LDScript is such that the Web page is computed and displayed in real time.

Data Shape

As part of a DataShape validator, we wrote an interpreter for W3C DataShape Property Path language 6 . The function below recursively rewrites a property path shape expression ?pp as a LDScript list. function sh:path(?shape, ?pp){ let ((?q, ?path) = select ?shape ?pp ?q ?path where { graph ?shape { # rdf:rest is for a sequence values ?q { sh:inversePath sh:alternativePath sh:zeroOrMorePath sh:oneOrMorePath sh:zeroOrOnePath rdf:rest } ?pp ?q ?path } } ) { if (! bound(?q)){ if (isURI(?pp)){ ?pp } else { error() } } else if (?q = rdf:rest) { xt:list(sh:sequence, sh:list(?shape, ?pp)) } else { xt:list(?q, sh:path(?shape, ?path)) } } }

The function below rewrites recursively an RDF list of path expressions ?pp (e.g. a sequence) as a LDScript list. function sh:list(?shape, ?pp){ let ( (?l) = select ?shape ?pp (aggregate(sh:path(?shape, ?e)) as ?l) where { graph ?shape { ?pp rdf:rest*/rdf:first ?e }}) { ?l } }


Vincent Chabot

Maëlle Nodet

Arthur Vidard

Taking into account correlated observation errors by progressive assimilation of multiscale information

The description of correlated observation error statistics is a challenge in data assimilation. Currently, the observation errors are assumed uncorrelated (the covariance matrix diagonal) which is a severe approximation that leads to suboptimal results. It is possible to use multi-scale transformations to retain the diagonal matrix approximation while accounting for some correlation. However this approach can lead to some convergence problems due to scale interactions. We propose an online scale selection algorithm that improves the convergence properties in such case.

Motivation: account for correlated satellite observation errors Numerical weather prediction requires the determination of the initial state of the system. Indeed, the true state, at a given moment and in all points of space, is not accessible. In order to retrieve an optimal initial condition one uses the so called data assimilation methods that combine information from observations, model equations and their respective error statistics. Since the late 70s, satellites are a dominant source of information. Errors associated to such data are highly correlated in space, which can be detrimental if this is not properly accounted for. However their density in space allows for the efficient use of multi-scale transformation, which in turn permit a cheap but good approximation of said error statistics representation. For homogeneous spatially correlated Gaussian observation errors this approach is very efficient. For more complex errors, however, it can severely damage the convergence properties of the assimilation methods. Here we present, through a simple case mimicking a laboratory experiment, an illustration of the above-mentioned problem and a possible solution using scale selection during the assimilation process.

Data assimilation: Principle

x a = (I -KH) x f + K y o = x f + K(y o -H(x f )) K = P f H T (HP f H T + R) -1
Variational equivalence: x a is the minimizer of

J(x) = (x -x f ) T P f (x -x f ) + (Hx -y o ) T R(Hx -y o )

Variational Data Assimilation

Let M be a dynamical model describing the evolution of the state variable X in space and time:

∂ t X (X 0 , x, t) + M(X (X 0 , x, t)) = 0 X (X 0 , x, t 0 ) = X 0
Let Y (t) be (partial) observations of this state variable. The aim of data assimilation is to estimate an optimal initial condition X a 0 (often called analysed state) so that it is not far from the first guess X b 0 (in general coming from a previous forecast), and that the model trajectory X (X a 0 , x, t) is close to the observations Y (t).

This is done by defining X a 0 as the minimum of the cost function:

J(X 0 ) = J b (X 0 ) + J o (X 0 ) = 1 2 X 0 -X b 0 2 V + 1 2 t f t i =t 0 ||Y (t i ) -H(X (X 0 , x, t i ))|| 2 O
where V is the model state space, O the observation space and H : V → O the observation operator. Usually, in variational data assimilation, the minimisation is done using a gradient descent type algorithm and the gradient is computed using adjoint methods.

Typically in data assimilation one uses the Mahalanobis distance:

.

2 V = . 2 B , 2 O = . 2 R , with X 2 K = X T K -1
X where R and B are the observation and background error covariance matrices respectively.

Error covariance matrix representation

Crucial choice for B and R: drive the way information is spread and how redundancy of error is delt with. So far: strong research effort for B modelling. R matrix: mostly assumed diagonal.

Main reason for this: management greatly simplified. Number of observations in general non constant over time → prevents from using the same R matrix. Consequelntly: at each assimilation cycle, a new R matrix should be formed and inverted.

Our work: change of variable, which allows diagonal R + non trivial correlations. Linear changes of variable A: assuming observation errors to be additive, unbiased and gaussian, i.e. Y = Y t + with ∼ N (0, R), Y t being the true signal, then AY = AY t + β with β ∼ N (0, ARA T ).

Choice of A such that D A = diag(ARA T ) ARA T → we retain a diagonal approximation:

(Y -H(X )) T R -1 (Y -H(X )) (Y -H(X )) T A T D -1 A A(Y -H(X ))
Here: orthonormal wavelet transform for the operator A (see more options in 2015 reference).

Experimental settings

Experimental framework: mimics the drift of a vortex on a turntable. CORIOLIS experimental turntable (Grenoble, France): simulates the evolution of a vortex in the atmosphere. 1 rotation of the tank = 1 earth rotation. Vortex creation: by stirring the water and made visible thanks to the addition of a passive tracer (fluorescein). Photographs of the vortex constitute the observed image sequence.

Numerical configuration

Shallow-water equations for the horizontal velocity w (x, t) = (u(x, t), v (x, t)), and the water elevation h(x, t):

   ∂ t u -(f + ζ)v + ∂ x B = -ru + κ∆u ∂ t v + (f + ζ)u + ∂ y B = -rv + κ∆v ∂ t h + ∂ x (hu) + ∂ y (hv ) = 0.
with ζ the relative vorticity and B the Bernouilli potential:

ζ = ∂ x v -∂ y u, B = g * h + u 2 + v 2
2 where g * is the reduced gravity. Coriolis parameter: β-plane, f = f 0 + βy , κ diffusion coeff., r bottom friction coeff.

Observation operator

Vortex temporal evolution: fluorescein concentration evolution, observed by an image sequence of the concentration of a passive tracer q transported by the velocity field w : ∂ t q + ∇q • w -ν T ∆q = 0 q(t 0 ) = q 0 . so that: H X t i = q(t i ).

Twin Experiments Configuration

Synthetic observations: created thanks to a model simulation from a known "true state"; then an assimilation experiment is performed starting from another "background" state using the synthetic observations. Result can be compared with the synthetic truth. Results

1: Homogeneous observation error

The observation are obtained by adding a spatially correlated Gaussian noise to selected snapshot of the true trajectory

Y t i = Y t t i + with =∼ N (R, I)
In order to mimic the usual approach, only diagonal approximations of R are used: Comment: Even though D A is only an approximation of R, accounting for some part of the spatial correlation is clearly beneficial.

R pix = diag(R) R wav = D A = diag(ARA T ) 10

Results 2: Inhomogeneous observation error

The observation error is still Gaussian and spatially correlated, but these correlations are now inhomogeneous in space:

Y t i = Y t t i + with = A T D 1/2
A β β ∼ N (0, I) so that D A is the exact representation of R in the wavelet space. Comment: Even though the observation error is exactly represented in the Wavelet case, its minimisation is struggling to converge toward a minimum similar or better than for the pixel case. Main reason for this: some sort of aliasing in the small scales, as illustrated below:

Comments:

Blue / pixel: It starts with a small value (the only difference comes from the noise) and, as time goes by, the vortex drifts and the difference with the initial concentration steadily increases. Green / wavelet: It shows a steep increase at the beginning, but then oscillate around a 'plateau'. This happens because, at this point, the norm is really dominated by the small scales. This is expected, since they are the least affected by the correlated noise, so their associated error variances are the smallest (i.e. one trusts more the small scales). Red, black and purple / wavelets + removing the 1, 2 and 3 finest scales in the multi scale decomposition respectively. The problem appears later (i.e. for larger discrepancies) when removing the finest scales and even disappear for the purple one.

Results 3: Improvement by online scale selection Idea: First assimilate the large scales, in order to reduce the difference between H(X ) and Y , and to be in the monotonic region of the green curve, and then progressively includes the smaller scales.

Conclusion:

Using multi-scale transforms as changes of variables to represent observation error correlation in data assimilation is a cost effective and promising approach. However this can lead to convergence problems in some cases. A progressive assimilation of the finest scale can significantly improve the convergence, making it a more robust approach.

Figure

  Figure caption: "True" initial concentration of the passive tracer (first left) and noisy observations at initial time, after 90 minutes, 150 min and 270 min (right).

Figure caption :

 caption Figure caption: Ratio of residual errors r = (X t -X )/(X t -X b ) along minimisation iterations for both pixel and wavelet based distances in presence of an homogeneous observation error.

Figure caption :

 caption Figure caption: Ratio of residual errors r = (X t -X )/(X t -X b ) along minimisation iterations for both pixel and wavelet based distances in presence of an inhomogeneous observation error.

Figure caption :

 caption Figure caption: Discrepancy between the background initial concentration and the successive observations Y t i -H(X b 0 ) 2 X along time, as would be measured by the observation term of the cost function, with X = diag(R) for Pixel and X = ARA T for Wavelet.

Figure caption :

 caption Figure caption: Ratio of residual errors along minimisation iterations for pixel and wavelet-based and progressive wavelet-based distances in presence of an inhomogeneous observation error.

t , where: y o incomplete observations, errors o unbiased, covariance matrix R x f = x t + f , f background errors unbiased, covariance P f observation operator H = H maps linearly the input parameters to the observations Solution: Best linear unbiased estimator (BLUE):

	Best Linear Unbiased Estimation (BLUE)

What is data assimilation? Combine at best different sources of information to estimate the state of a system: model equations observations, data background, a priori information errors statistics

What is data assimilation for? historically: initial state estimation, for weather forecasting. today, many other applications... ... and many other application domains.

Least squares analysis: solve the inverse problem y o = H(x t ) + o , given a background estimate x f of the true input parameters x


Konstantin Avrachenkov
email: konstantin.avrachenkov@inria.fr

Giovanni Neglia
email: giovanni.neglia@inria.fr

Vikas Vikram Singh

NETWORK FORMATION GAMES WITH TEAMS *

Keywords: 2010 Mathematics Subject Classification. Primary: 91A25, 91A43, 91A06, Secondary 93E15, 60J10 Network Formation Games, Teams, C-stability, Strong stability, Stochastic stability

Network formation games have been proposed as a tool to explain the topological characteristics of existing networks. They assume that each node is an autonomous decision-maker, ignoring that in many cases different nodes are under the control of the same authority (e.g. an Autonomous System) and then they operate as a team. In this paper we introduce the concept of network formation games for teams of nodes and show how very different network structures can arise also for some simple games studied in the literature. Beside extending the usual definition of pairwise stable networks to this new setting, we define a more general concept of stability toward deviations from a specific set C of teams' coalitions (C-stability). We study then a trembling-hand dynamics, where at each time a coalition of teams can create or sever links in order to reduce its cost, but it can also take wrong decisions with some small probability. We show that this stochastic dynamics selects C-stable networks or networks from closed cycles in the long run as the error probability vanishes.

1. Introduction. Network formation games are nowadays a consolidated branch of game theory [START_REF] Demange | Group Formation in Economics: Networks, Clubs, and Coalitions[END_REF][START_REF] Dutta | Networks and Groups: Models of Strategic Formation[END_REF][START_REF] Goyal | Connections: An Introduction to the Economics of Networks[END_REF][START_REF] Jackson | Social and Economic Networks[END_REF]. They study which networks' structures arise when the nodes are selfish rational players, who can sever or create some links in order to increase the utility they perceive from the network. In particular, it is usually assumed that each node can unilaterally sever a link to one of its neighbors, while the creation of a new link requires the approval of both the participating nodes. This idea has lead to the concept of pairwise-stable networks [START_REF] Jackson | A strategic model of social and economic networks[END_REF], i.e., networks for which every existent link is beneficial to both the connected nodes and every inexistent link is not beneficial to at least one of the two nodes it would connect. Different dynamics for links' creation/destruction have been studied. Specific network formation games have been proposed to explain the topological characteristics of existing networks, including the Autonomous Systems' (ASs') network taking for example into account both costs for routing traffic and for a lack of end-to-end connectivity [START_REF] Anshelevich | Strategic network formation through peering and service agreements[END_REF][START_REF] Corbo | An economically-principled generative model of AS graph connectivity[END_REF][START_REF] Johari | A contract-based model for directed network formation[END_REF]. They have also been used to investigate the distributed formation of overlay topologies on top of the Internet [START_REF] Elias | A game theoretic analysis of network design with socialy-aware users[END_REF], or routing topologies among relay stations in future cellular networks [START_REF] Saad | Network formation games among relay stations in next generation wireless networks[END_REF], or among nodes in multi-hop wireless networks to prevent eavesdropping [START_REF] Saad | Network formation games for wireless multihop networks in the presence of eavesdroppers[END_REF].

Network formation games consider that each node is an autonomous decisionmaker, ignoring that in many cases different nodes are under the control of the same authority (e.g. the routers in an AS) and then they constitute a team. We observe that introducing teams in a simple variant of a network formation game proposed in [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF] leads to different stable network structures. This motivates us to study network formation games with teams and define new stability notions for this new class of games. Although the concept of teams is not new to game theory, e.g., there is a recent work by Boncinelli and Pin [START_REF] Boncinelli | Efficiency and stability in a process of teams formation[END_REF] where they analyze team formation process in game theoretic models. To the best of our knowledge this paper is the first to introduce teams in network formation games and aims to open a new and, in our opinion, interesting research direction.

Our first contribution is then to define network formation games for teams of nodes and define team-pairwise stability analogously to pairwise stability in standard network formation games. The second contribution of our paper is to provide a more general concept of stability toward the deviations from a specific set C of teams' coalitions (we talk then about C-stability). This idea can capture the fact that some groups of teams are more likely to cooperate than others. For example, ASs located in far away regions may have no incentive to connect directly. In addition to the above notions of static stability, we also consider the dynamic formation of networks also in the presence of random errors (trembling-hand dynamics). We then discuss the dynamic stability notion called stochastic stability, i.e., which networks are selected by the dynamics as the error probability vanishes. So, as a final contribution, we prove that under this trembling-hand dynamics only C-stable networks or networks from closed cycles are selected with non-zero probability in the long term when trembling vanishes. The case where there is no restriction on the coalition formation among teams, the C-stability is called strong stability. We show that our trembling-hand dynamics selects all strongly stable networks and networks from closed cycles as the error probability vanishes. Now, we describe some existing works related to our stochastic stability result. Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF] are the first ones to consider trembling-hand dynamics in standard network formation games for the case of pairwise interaction between nodes. At each time during pairwise interaction considered in [START_REF] Jackson | The evolution of social and economic networks[END_REF], a pair of nodes are selected and only a link between them is altered. The mutations are present in the dynamics due to a wrong decision taken by the selected pair of nodes at each time. They showed that a stochastically stable network is a pairwise stable network or a network from a closed cycle. Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF] also considered the case where a pair of nodes can add a new link between them and at the same time each node of selected pair can sever existing links with other nodes of network. They applied these models into matching problems such as marriage problem and college admission problem [START_REF] Gale | College admissions and the stability of marriage[END_REF][START_REF] Roth | Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis[END_REF]. For some recent stochastic stability results on matching problems see [START_REF] Klaus | Stochastic stability for roommate markets[END_REF][START_REF] Newton | A one-shot deviation principle for stability in matching problems[END_REF]. We generalize the results from [START_REF] Jackson | The evolution of social and economic networks[END_REF] in both static and dynamic settings. We first introduce teams in network formation games and define teampairwise stability analogous to pairwise stability. We allow teams to form all possible coalitions and define the notion of C-stability. In dynamic formation of networks, we assume that at each time a teams' coalition is formed. The coalition makes a move from the current network to a new network, by adding or severing some links in the current network, if at new network all the teams in the coalition are at least as well off and at least one team is strictly better off. At each time the coalition makes a mistake with small probability and as a result the obtained network need not be beneficial for all the teams in the coalition. We show that a stochastically stable network is a C-stable network or a network belonging to a closed cycle of networks. We also show that if a network of a closed cycle is stochastically stable, all the networks of the closed cycle are stochastically stable. The stochastic dynamics based on the coalitional deviations in general finite games, using different dynamics rules, have been considered before [START_REF] Newton | Coalitional stochastic stability[END_REF][START_REF] Sawa | Coalitional stochastic stability in games, networks and markets[END_REF] . Sawa [START_REF] Sawa | Coalitional stochastic stability in games, networks and markets[END_REF] studied the stochastic stability in general finite games where the mutations are present through a logit choice rule. Newton [START_REF] Newton | Coalitional stochastic stability[END_REF] considers the situation where profitable coalitional deviations are given greater importance than unprofitable single player deviations. In general, the stochastic stability results depend on the way actions being chosen during the infinite play. Some other famous works on stochastic stability in different settings include [START_REF] Boncinelli | Efficiency and stability in a process of teams formation[END_REF][START_REF] Foster | Stochastic evolutionary game dynamics[END_REF][START_REF] Fudenberg | Imitation processes with small mutations[END_REF][START_REF] Fudenberg | Evolutionary game dynamics in finite populations with strong selection and weak mutations[END_REF][START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF][START_REF] Newton | Recontracting and stochastic stability in cooperative games[END_REF][START_REF] Newton | Coalitions, tipping points and the speed of evolution[END_REF][START_REF] Young | The evolution of conventions[END_REF].

The paper is organized as follows. We start providing the basic definitions for network formation games with teams in Section 2. Then, in Section 3 we provide a simple variant of a network formation game proposed in [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF] showing that different network structures arise in the presence of teams. We move then to introduce the general concept of C-stability in Section 4. Section 5 describes the trembling-hand dynamics. We show some numerical results for specific games in Section 6. Finally, we conclude our paper in Section 7.

2. Network formation games with teams: Basic definitions. In this section we define network formation games for teams and we start extending some usual concepts in network formation games' literature to our setting. In particular, we define the notion of team-pairwise stability to characterize meaningful equilibria. Let N = {1, 2, • • • , n} be a finite set of nodes. Let P = {T 1 , T 2 , • • • , T m }, m ≤ n be a partition of N . The undirected edges can be formed both between the nodes belonging to a same set T i (called internal links) as well as belonging to the different sets T i and T j (called external links). The edge between the nodes k and l is denoted by kl. We say that there is a link between T i and T j if there is at least one link kl with k ∈ T i and l ∈ T j . The collection of edges defines a network g.

In standard network formation games, each node k has its own cost c k (g). In network formation games with teams we consider that the nodes belonging to each set T i share the same cost c(T i , g), which depends in general on the structure of the whole network g. As a consequence, they will form or sever links only if this is beneficial for the whole set T i , i.e., if the cost of T i is reduced. For this reason we refer to each T i , i = 1, 2 . . . , m, as a team. In particular, the nodes in a team will agree to create an internal link kh with k, h ∈ T i , if c(T i , g ∪ kh) < c(T i , g), and will agree to sever an internal link kh if c(T i , g \ kh) < c(T i , g). This leads to following definition of internal stability: Definition 2.1 (Internal stability). A network g is internally stable in team T i if no further links can be created or severed within the nodes from T i , i.e., if g ′ is a network which is obtained from g via the addition of new links within the nodes of T i or destruction of existing links within the nodes of T i , then c(T i , g ′ ) > c(T i , g). A network is internally stable if it is internally stable in all the teams. The destruction of an external link is unilateral: any of the two nodes can sever the link if this is beneficial for its team. On the contrary, the creation of an external link requires the agreement of both the teams involved. The link will then be created only if it does not increase the cost of any of the two teams and it decreases the cost of at least one of them. These link formation rules lead to the following notion of equilibrium for network formation games with teams: Definition 2.2 (Team-pairwise stability). A network g is said to be team-pairwise stable if (i) g is internally stable, and (ii) for all the pairs (T i , T j ) if kl ∈ g such that k ∈ T i , l ∈ T j then c(T i , g) ≤ c(T i , g \ kl) and c(T j , g) ≤ c(T j , g \ kl), and (iii) for all the pairs (T i , T j ) if kl / ∈ g, such that k ∈ T i , l ∈ T j and if c(T i , g ∪ kl) < c(T i , g) then c(T j , g ∪ kl) > c(T j , g).

3. Network formation games with teams: A motivating example. Fabrikant et al. [START_REF] Fabrikant | On a network creation game[END_REF] introduced a network formation game where each node can add as well as sever the links unilaterally. Corbo and Parkes [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF] considered the case when link destruction is unilateral but link creation requires the agreement of both the nodes involved. The two games are called in [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF], respectively the Unilateral Connection Game and the Bilateral Connection Game (BCG). We focus on BCG because we are interested in pairwise interaction among the teams. We introduce a simple variant of BCG, that we call the Heterogeneous Bilateral Connection Game (HBCG) and study it in the presence or absence of teams. We observe that, even in a very simple case, a stable network structure in the presence of teams is not stable when each node is an independent rational player. This shows the usefulness of the new stability notions defined in the Section 2 and it motivates us to study network formation games with teams. Note that while in this section we consider a specific cost function from [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF], our definitions and results in the the rest of the paper hold for general cost functions. [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF]. Let N = {1, 2, • • • , n} be a finite set of players (nodes). The cost of a link is 2α which is equally shared between both the corresponding nodes. Let k g (i) denote the degree of node i in network g which is the total number of links connected to i. A node also incurs the cost due to the distance from all other nodes. The distance between the nodes i and j in the network g is defined as the minimal number of hops along a path connecting them and it is denoted by d g (i, j). If there is no path connecting node i and node j, the distance d g (i, j) = ∞ . The cost incurred by node i in network g is

The bilateral connection game

c i (g) = α • k g (i) + j∈N ;j =i d g (i, j). (1)
3.2. The heterogeneous bilateral connection game. We introduce a variant of BCG that we call the Heterogeneous Bilateral Connection Game (HBCG). In HBCG nodes are divided into the disjoint sets {T i } m i=1 . The cost of a link between two nodes from the same set is 2α β , β > 0, and the cost of a link between two nodes from the different sets T i and T j is 4α

β . If all the nodes are independent rational players, the cost of a link formation is equally shared between the corresponding nodes, i.e., a node incurs cost α β by forming a link with a node from a same set and it incurs cost 2α β by forming a link with a node from a different set. In this case, the total cost incurred by a node i belonging to set T in a given network g is given by

c i (g) = α β • k g (i|T ) + 2α β • k g (i|T c ) + j∈N ;j =i d g (i, j),
where k g (i|T ) denotes the number of neighbors of i inside set T and k g (i|T c ) is the number of i's neighbors outside the set T . We observe that if each set T i includes only one node and β = 2, HBCG reduces to BCG. In what follows we consider that each set T i has cardinality at least 2.

If the nodes belonging to each set

T i , i = 1, 2, • • • , m
, form a team, the cost experienced by each member is shared by the whole team. In this case, each team incurs cost 2α β for forming an internal as well as an external link. For a given network g, the cost of a team T i is then defined as

c(T i , g) = k∈Ti c k (g) = 2α β E(T i ) + Tj ∈P j =i E(T i T j ) + k∈Ti j∈N j =k d g (k, j), (2)
where E(T i ) is the total number of internal links of T i and E(T i T j ) is the total number of external links between T i and T j . Finally the cost of a network g is denoted by c(g) and it is defined as the sum of the costs of all teams. We now study the effect of teams on the stability of network topologies. We show that even for a simple case β 2 < α ≤ β a team-pairwise stable network is not a pairwise stable network.

Proposition 1. Consider HBCG with teams and β 2 < α ≤ β. In a network g if all the nodes from each team form a complete network internally, the network g is internally stable.

Proof. Let g be a network where all the nodes from each team form a complete network internally. It is not possible to decrease the cost of a team by deleting internal links because deleting one internal link will increase the cost of each team by at least 2 due to distance, while the cost reduction due to deletion of link is only 2α β ≤ 2. Hence, g is internally stable.

Similarly to the star network in standard network formation games, we define a star network at team level which we call a team-star. A network is a team-star if i) each team has at least two nodes, ii) all the nodes of each team form a complete network internally, iii) there is a central team with a node called central node such that all the nodes of other teams are connected to the central node and iv) there is no other external link. An example of a team-star is in Figure 1 Proposition 2. For β 2 < α ≤ β, a team-star network is team-pairwise stable in HBCG with teams but it is not pairwise stable in HBCG without teams.

Proof. Let g be a team-star network, then by definition g is internally stable. From the definition of g it is clear that the distance between any two nodes of g is at most 2. A new link between any two non-central teams cannot be created because it costs each team 2α β > 1 while the distance reduction for a team is only 1. Similarly, a new link between the central team and a non-central team cannot be created. Also, no existing link between the central team and a non-central team can be deleted because deleting one such link will cost at least 2 to each team (because there are at least two nodes in the team whose distance to some other node increases by at least one), while the cost due to the destruction of the link is reduced only by 2α β ≤ 2. So, a team-star is team-pairwise stable.

Assume that there is no team, i.e., the nodes belonging to each set T i , i = 1, 2, • • • , m, are independent rational players. Then a team-star network is not pairwise stable because the central node k from the central set T i will form at most one link to each set T j , j = i. Proposition 3. For α > β, a star network is a team-pairwise stable in HBCG with teams as well as pairwise stable in HBCG without teams.

Proof. Let g be a star network. In the presence of teams, no internal links can be formed in g because forming an internal link will cost 2α β > 2 to a team while the distance reduction for a team is only 2. An external link in g between two teams cannot be formed because it will cost each team 2α β > 2 while the distance reduction for a team is only 1. No existing links of g can be deleted because in that case the cost of each team due to distance would be ∞. Hence, g is a team-pairwise stable.

In the absence of teams, a new link in g between two nodes from the same set cannot be formed because it will cost each node α β > 1, while the distance reduction for a node is only 1. A new link in g between two nodes from different sets cannot be formed because it will cost each node 2α β > 2, while the distance reduction for a node is only 1. No existing links of g can be deleted due to the same reason given for the case of teams. Now there is an interesting question: for β 2 < α ≤ β which network is pairwise stable when nodes belonging to sets {T i } m i=1 do not form a team. To get an idea how a pairwise stable network looks like, we consider an instance of HBCG with 9 nodes that are divided into 3 sets, i.e., N = {1, 2, 3, 4, 5, 6, 7, 8, 9} and T 1 = {1, 2, 3}, T 2 = {4, 5, 6}, T 3 = {7, 8, 9}. The team-star network given in Figure 1 is team-pairwise stable but not pairwise stable from Proposition 2. A pairwise stable network in this case when nodes from T 1 , T 2 and T 3 do not form a team is given in Figure 2. A teampairwise stable network c(team-star) < c(g). In the simple case of HBCG, introducing the teams give us a team-pairwise stable network which is not pairwise stable but is less costly than the pairwise stable network.

4. Stability of networks against teams' coalitions. In this section, we introduce the concept of stability against the teams' coalitions. This notion of stability generalizes team-pairwise stability in two directions. First, the creation of a link between two teams requires the agreement of the whole coalition the two teams belong to (if any). Second, a coalition can create/severe simultaneously multiple links among its members (while team-pairwise stability considers only the possibility to either add or remove a single link at a time). In order to formally define this new stability concept we introduce the following definitions analogous to those in [START_REF] Jackson | Strongly stable networks[END_REF] for standard network formation games. Let C ⊂ 2 P denote the set of teams' coalitions.

Definition 4.1. A network g ′ is obtainable from g via deviation by a coalition S ∈ C as denoted by g → S g ′ , if

(i) if kl ∈ g ′ , kl / ∈ g, k ∈ T i and l ∈ T j , then {T i , T j } ⊂ S. (ii) if kl ∈ g, kl / ∈ g ′ , k ∈ T i and l ∈ T j then {T i , T j } ∩ S = φ.
The condition (i) requires that new links can be added only between teams that are part of the coalition S. The condition (ii) requires that at least one team of any deleted link has to be part of S. The case T i = T j corresponds to the creation/destruction of internal links from a team of the coalition. We denote G(S, g) as a set of all networks which are obtainable from g via a deviation by S.

Definition 4.2. A deviation by a coalition S from a network g to a network g ′ is said to be improving if (i) g → S g ′ , (ii) c(T, g ′ ) ≤ c(T, g), ∀ T ∈ S (with at least one strict inequality).

Let G I (S, g) be the set of all networks g ′ which are obtainable from g by an improving deviation of S, i.e.,

G I (S, g) = g ′ ∈ G(S, g)|c(T, g ′ ) ≤ c(T, g), ∀ T ∈ S, c(T ′ , g ′ ) < c(T ′ , g) for some T ′ ∈ S .
Let G nI (S) = G(S, g) \ G I (S, g) be the set of networks g ′ which are obtainable from g but do not lead to an improvement (they would be chosen by "error"). It is clear that g ∈ G nI (S, g). It is reasonable to consider that a coalition would only accept improving deviations. This leads to the following definition of stability. Definition 4.3. A network g is C-stable if it is not possible for any coalition S ∈ C to make an improving deviation from g to some other network g ′ .

A C-stable network may not always exist, but in that case there exists some set of networks lies on a closed cycle and all the networks in a closed cycle can be reached from each other via an improving path. We next give the definitions of an improving path and closed cycle.

Definition 4.4 (Improving Path

). An improving path from g to g ′ is a sequence of networks and coalitions g

1 , S 1 , g 2 , • • • , g n-1 , S n-1 , g n such that g 1 = g, g n = g ′ and g k+1 ∈ G I (S k , g k ) for all k = 1, 2, • • • , n -1.
Definition 4.5 (Cycles). A set of networks Q form a cycle if for any g, g ′ ∈ Q there exists an improving path connecting g and g ′ . A cycle Q is said to be a closed cycle when no network in Q lies on an improving path leading to a network that is not in Q.

Theorem 4.6. There exists at least a C-stable network or a closed cycle of networks.

Proof. The proof follows similar lines to the proof for pairwise stable network given in [START_REF] Jackson | The evolution of social and economic networks[END_REF]. Here we sketch the proof for completeness. A network is C-stable if and only if it does not lie on an improving path leading to some other network. So, start at any arbitrary network g. If there exists no improving path from g then g is C-stable otherwise g lies on an improving path leading to some other network. In the first case result is established. We consider the second case. Follow the improving path. Since, there are finite number of networks, then either the improving path ends at some network which has no improving paths and in that case the resulting network must be C-stable or it will form a cycle. That is, there exists either a C-stable network or a cycle. Consider the case where there are no C-stable networks. Given the finite number of networks and non-existence of C-stable networks there must exist a closed cycle.

Dynamic formation of networks under coalitions.

In this section we consider a scenario where networks are formed dynamically over time and coalitions may or may not make errors. We first consider the case when the coalitions of teams do not make errors over time. At each time t = 1, 2, • • • , a coalition S t ∈ C is randomly selected with probability p St > 0. If possible, the coalition selects an improving deviation g t+1 ∈ G I (S t , g t ) with probability p I (g t+1 |S t , g t ). If there is no improving deviation then the coalition does not modify the network, i.e. g t+1 = g t . The above situation can be modeled as a Markov chain over the set of possible networks, whose transition law P 0 is defined as:

P 0 (g ′ |g) = S∈C;GI (S,g) =φ p S p I (g ′ |S, g)1 GI (S,g) (g ′ ) + S∈C;GI (S,g)=φ p S 1 {g ′ =g} (g ′ ), (3)
for all g, g ′ , where p I (•|S, g) is a probability distribution over G I (S, g), and 1 B (•) is an indicator function on a given set B. It is clear that the C-stable networks and the closed cycles of networks are recurrent classes of P 0 . A C-stable network corresponds to an absorbing state of P 0 and a closed cycle corresponds to a recurrent class of P 0 containing more than one state (i.e. more than one network).

We now introduce the possibility that coalitions make errors, i.e., they may not select at a given step an improving coalition and then they can make worse off one of their members. This may take into account the incertitude about the actual costs of a network topology or a bounded rationality. In particular we adapt the usual trembling-hand model [START_REF] Jackson | The evolution of social and economic networks[END_REF]. At each step the coalition chooses a nonimproving deviation with probability εf (S t , g t ) ∈ (0, 1), where f (S t , g t ) takes into account the fact that some coalitions can be more prone to make errors than others and that some network configurations may lead to wrong choices more often than others. The parameter ε allows us to tune the frequency of errors. So, at time t + 1 the coalition S t an improving deviation with probability 1 -εf (S t , g t ) .

In particular it chooses g t+1 ∈ G I (S t , g t ) according to the distribution p I (•) defined above. By combining the probabilities we obtain that the coalition selects g t+1 ∈ G I (S t , g t ) with probability 1 -εf (S t , g t ) p I (g t+1 |S t , g t ). The coalition selects a non-improving deviation with probability εf (S t , g t ). Let p nI (•|S, g) be a distribution over G nI (S, g), the coalition chooses g t+1 ∈ G nI (S t , g t ) with probability εf (S t , g t )p nI (g t+1 |S t , g t ). If there is no improving deviation, then with probability 1 -εf (S t , g t ) the coalition does not modify the network, i.e., g t+1 = g t , and with the complementary probability selects a network in G nI (S t , g t ) according to the distribution p nI (•|S t , g t ). These rules define a perturbed Markov chain whose transition law P ε is:

P ε (g ′ |g) = S∈C GI (S,g) =φ p S (1 -f (S, g)ε)p I (g ′ |S, g)1 GI (S,g) (g ′ ) + f (S, nI (g ′ |S, g)1 GnI (S,g) (g ′ ) + S∈C;GI (S,g)=φ p S (1 -f (S, g)ε)1 {g ′ =g} (g ′ ) + f (S, g)εp nI (g ′ |S, g)1 GnI (S,g) (g ′ ) (4)
for all g, g ′ . It is easy to check that if ε = 0, P ε reduces to P 0 defined above.

The perturbed Markov chain P ε is irreducible because given nonzero errors it is possible to reach all the networks starting from any network in a finite number of steps. It is also aperiodic because with positive probability the state does not change. Hence, there exists a unique stationary distribution µ ε of the perturbed Markov chain. However, when ε = 0, there can be several stationary distributions corresponding to different C-stable networks or closed cycles. Such Markov chains are called singularly perturbed Markov chains [START_REF] Avrachenkov | Singular perturbations of markov chains and decision processes[END_REF], [START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF]. The probability of making error can be sufficiently small. So, we are interested in the networks to which the stationary distribution µ ε assigns positive probability as ε → 0. This leads to the definition of stochastic stability: Definition 5.1. A network g is stochastically stable relatively to the process P ε if lim ε→0 µ ε g > 0. We recall a few definitions from Young [START_REF] Young | The evolution of conventions[END_REF]. If P ε (g ′ |g) > 0, g = g ′ , the one step resistance r(g, g ′ ) from network g to g ′ is defined as the minimum number of errors that are required for the Markov chain to make a transition from g to g ′ in one step. In our case it is clear that r(g, g ′ ) ∈ {0, 1} for any pair (g, g ′ ). One can view the networks as the nodes of a directed graph that has no self loops. The weight of a directed edge is represented by the one step resistance between the corresponding networks and the resistance of a directed path (/tree) is the sum of the weights of its edges. We can then define the resistance from g to g ′ as the resistance of the minimum-resistance path from g to g ′ (there exists at least one because P ε is irreducible). We now introduce a stochastic potential of recurrent classes of P 0 (remember these are important because they are the C-stable networks or the closed cycles of networks). It can be computed by restricting to a reduced graph G where the total number of nodes are the number of recurrent classes of P 0 (one representative g i ∈ G i for each recurrent class G i ). Given two nodes g i , g j of G, the weight of the directed edge from g i to g j is the resistance from g i to g j . Given a node g i ∈ G, consider all the directed spanning trees such that from every node g j ∈ G, g j = g i , there is a unique path directed from g j to g i . Such spanning trees are called g i -trees. The stochastic potential of g i (and then of G i ) is the resistance of the g i -tree having minimum resistance among all the g i -trees. The resistance between any two networks in the same recurrent class is null, because no error is required to move from one to the other. It follows that the stochastic potential of any network g i ∈ G i is the same and then the definition of the stochastic potential of the class G i does not depend on the specific choice of its representative. We have now provided the background required to state and prove the following result.

Theorem 5.2. All C-stable networks and the networks belonging to closed cycles, that have minimum stochastic potential, are stochastically stable networks . Furthermore, if one network in a closed cycle is stochastically stable then all the networks in that closed cycle are stochastically stable.

Proof. We know that the Markov chain P ε is aperiodic and irreducible. From ( 3) and ( 4) it is easy to see that

lim ε→0 P ε (g ′ |g) = P 0 (g ′ |g), ∀ g, g ′ . From (4) it is clear that, if P ε (g ′ |g) > 0 for some ε ∈ (0, ε 0 ], we have 0 < ε -r(g,g ′ ) P ε (g ′ |g) < ∞.
Therefore, the Markov chain P ε is a regular perturbed process because it satisfies all the three conditions given in [START_REF] Young | The evolution of conventions[END_REF]. Hence, it follows from Theorem 4 of Young [START_REF] Young | The evolution of conventions[END_REF] that as ε → 0, µ ε converges to a stationary distribution µ 0 of P 0 and a network g is stochastically stable if and only if g is contained in a recurrent class of P 0 having minimum stochastic potential. Therefore, all C-stable networks and the networks belonging to closed cycles having minimum stochastic potential are stochastically stable. The proof of last part follows from the fact that the stochastic potential of each network in a closed cycle is the same.

Remark 1. The stochastic stability results do not depend on the function f (•) or the distributions of p I (•), p nI (•) and p = (p S ) S∈C .

Strong stability:

We consider the case where there is no restriction on the formation of teams' coalitions, i.e., C = 2 P . In this case C-stability is called strong stability.

Corollary 1. If there is no restriction on the formation of teams' coalitions, all the strongly stable networks and the networks belonging to every closed cycle are stochastically stable.

Proof. Now, it is always possible to reach one network from another network by at most one error due to the formation of grand coalition. Then, the resistance between any two distinct recurrent classes G i and G j is always 1. Hence, the stochastic potential of each recurrent class of P 0 is J-1, where J is the number of recurrent classes of P 0 . In fact, a spanning tree in graph G includes only J -1 links and each of them has resistance 1. The proof then follows from Theorem 5.2.

6. Simulation results. In the previous section we have characterized which networks are selected in the long run by the trembling-hand dynamics, when the error probability ε converges to 0. Studying the dynamics itself for a finite ε is a harder problem, so we resort to simulations to investigate i) which networks appear more frequently during the dynamics and ii) which quasi-stable networks arise and how fast. By a quasi-stable network we mean a network that appears for a long period of time before a random error makes it disappear. We cannot be sure that such networks are indeed stable with respect to the set of coalitions we consider in the specific experiment (in general only a direct inspection of all the possible deviations could reach such conclusion). Nevertheless, specially for the larger values of ε the quasi-stable networks can appear over time durations comparable with those of the stable networks, so that practically speaking, they are as important as stable networks. The dynamics clearly depends on the value of ε, but also on the specific set C of the coalitions we consider: we are going to explore the effect of both. As case study, we consider a simple instance of HBCG with teams defined in Section 3.2. Let the set of nodes be N = {1, 2, 3, 4, 5, 6, 7, 8, 9}. The nodes are divided into three teams, T 1 = {1, 2, 3}, T 2 = {4, 5, 6} and T 3 = {7, 8, 9}. We take α = 1.5 and β = 2. For any experiment the initial network topology is selected uniformly at random among all the possible networks. At each iteration, p = (p S ) S∈C , p I (•), p nI (•) are uniformly distributed. The internal stability is known for this game, so, in the dynamics we update the networks in such a way that the internal stability of the networks is preserved.

The case of all coalitions. We start considering a very small error probability ε = 0.00001. Figure 3 shows the time-evolution of the cost of the network selected by the dynamics. The curve suggests that the network dynamics has selected (very fast) a quasi-stable network of cost 145.5, that is the cost of the team-star for these specific values of α and β. An inspection of the topologies of the networks show that the dynamics reaches a specific team-star network and then nothing changes until the end of the simulation. In this simulation, the probability of appearing a specific team-star network is 0.9979. Note that we do not know if the team-star is stable with respect to the set of all the possible coalitions, but this experiment (and many others we carried on) suggest that this is the case, because we never observed an improving deviation. To check the stability of a team-star network using simulation we run a long experiment at sufficiently low ε = 0.000001 where we take the initial network a team-star network. We do not see any improving deviation till the end of simulation as shown by Figure 4.

Next, we consider the case of much higher error probability ε = 0.01. We can see from Figure 5 that the evolution of network cost is now very noisy because the dynamics jumps to a random network on average every 100 iterations due to high error probability. Even a stable network would not survive for a long time in this case. We run 100 simulations where each simulation starts with an initial condition that is chosen uniformly at random. Figure 6 shows the aggregate empirical distribution of network costs. The probability of appearing team-star network in this case is 0.0303. The network dynamics visits now more often the networks which are more costly than the team-star. We checked some of these networks which appear more frequently and none of them was stable. In particular, for all of them, the team-star was an improving deviation for the grand coalition. One could then wonder why these networks appear more often than the team-star during the dynamics. The reason behind is that such networks appear in much more "forms" than team-star. In fact there are only 9 team-star networks (in each of them a different node is the center of the star). For example some of the networks appearing more frequently are team-stars with a few more links. There are many different ways to place such extra links in order to have a network with the same cost. Said in other words, the classes of isomorphic networks have different sizes, and frequency with which a representant of the class appears during the network dynamics depends on its stability versus deviations but also simply on the size of the class. To check the fraction of time spent in team-star corresponding to different error probabilities over multiple simulations, we run 100 simulations, where initial condition is chosen uniformly at random in each simulation, for a given ε. The summary of these results are given in Figure 7. We observe that probability of appearing team-star increases as error probability decreases. Finally, we calculate the fraction of time team-star appeared, when edge additions or edge deletions occur at random, from our simulations data. The summary of these results are given in Figure 8. In this case, we observe that probability of appearing team star is almost zero corresponding to all the error probabilities considered in the experiment. Without the grand coalition. Here we consider the case where the grand coalition cannot form, but only the coalitions of size up to 2 can be formed. We first consider ε = 0.00001. In Figure 9, we observe first an evolution similar to that in Figure 3 with the network dynamics selecting very fast a team-star, but in this case an error after the 70000-th iteration produces a restart. Interestingly, after the restart, the cost reaches a constant value equal to 146.5. In this case the constant cost hides in reality a continuously changing topology. In fact, there are multiple networks with [START_REF] Corbo | An economically-principled generative model of AS graph connectivity[END_REF] which can be obtained one from the other by improving deviations from a coalition of size 2 and this is actually what is happening in this simulation. These networks are not even quasi-stable according to our definition, but from the point of view of the global cost, the situation does not change. As a final remark, we checked that also for these networks the team-star is an improving deviation, but it can only be enforced by the grand coalition, which is not considered in this case. For the larger error probability ε = 0.01 the dynamics appear to be similar to the previous case.

Only single team coalitions. Since, the creation of an external link requires a coalition of the two teams, then, in this case the only possible change is due to team severing links to other teams if it is beneficial for them or because of a random error. As soon as one of the team is disconnected from the other, there will be no more improving deviation, because the cost of each team becomes infinite. Then in this scenario the network evolves because of the random errors until all the teams are disconnected. This is the absorbing state for the network dynamics. 7. Conclusions. To the best of our knowledge this is the first paper where the concept of teams is introduced in network formation games. We extend the concept of pairwise stable networks to this new class of games, but also define the concept of network stability toward deviations from a specific set C of teams' coalitions. We show that C-stable networks (and closed network cycles), having minimum stochastic potential, are selected by a trembling-hand dynamics when the error probability vanishes. Finally, we resort to simulations to study the evolution of networks in a specific game by using our stochastic dynamics. We think that the idea of teams in network formation games may capture many practical phenomena such as connectivity pattern in the Internet Autonomous systems and it opens new research directions.

Figure 1 .

 1 Figure 1. Teamstar:A teampairwise stable network

Figure 2 .

 2 Figure 2. Pairwise stable network

Figure 3 .

 3 Figure 3. Sample path of network dynamics for ε = 0.00001

Figure 4 .

 4 Figure 4. Sample path at ε = 0.000001 under team-star as initial network

Figure 5 .Figure 6 .

 56 Figure 5. Sample path of network dynamics for ε = 0.01

Figure 7 .

 7 Figure 7. Fraction of time spent in team-star under network dynamics

Figure 8 .Figure 9 .

 89 Figure 8. Fraction of time spent in team-star under Markov model

Acknowledgements. This research was sponsored by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672.