Luis-Daniel Ibáñez

Hala Skaf-Molli

Pascal Molli
email: pascal.molli@univ-nantes.fr

Olivier Corby
email: olivier.corby@inria.fr

Col-Graph: Towards Writable and Scalable Linked Open Data

Linked Open Data faces severe issues of scalability, availability and data quality. These issues are observed by data consumers performing federated queries; SPARQL endpoints do not respond and results can be wrong or out-of-date. If a data consumer finds an error, how can she fix it? This raises the issue of the writability of Linked Data. In this paper, we devise an extension of the federation of Linked Data to data consumers. A data consumer can make partial copies of different datasets and make them available through a SPARQL endpoint. A data consumer can update her local copy and share updates with data providers and consumers. Update sharing improves general data quality, and replicated data creates opportunities for federated query engines to improve availability. However, when updates occur in an uncontrolled way, consistency issues arise. In this paper, we define fragments as SPARQL CONSTRUCT federated queries and propose a correction criterion to maintain these fragments incrementally without reevaluating the query. We define a coordination free protocol based on the counting of triples derivations and provenance. We analyze the theoretical complexity of the protocol in time, space and traffic. Experimental results suggest the scalability of our approach to Linked Data. … …

Introduction

The Linked Open Data initiative (LOD) makes millions of RDF-triples available for querying through a federation of SPARQL endpoints. However, the LOD faces major challenges including availability, scalability [START_REF] Buil-Aranda | Sparql webquerying infrastructure: Ready for action?[END_REF] and quality of data [START_REF] Acosta | Crowdsourcing linked data quality assessment[END_REF].

These issues are observed by data consumers when they perform federated queries; SPARQL endpoints do not respond and results can be wrong or out-ofdate. If a data consumer finds a mistake, how can she fix it? This raises the issue of the writability of Linked Data, as already pointed out by T. Berners-Lee [START_REF] Berners-Lee | The read-write linked data web[END_REF].

We devise an extension of Linked Data with data replicated by Linked Data consumers. Consumers can perform intensive querying and improve data quality on their local replicas. We call replicated subsets of data, fragments. First, any participant creates fragments from different data providers and make them available to others through a regular SPARQL Endpoint. Local fragments are writable, allowing modifications to enhance data quality. Original data providers can be contacted to consume local changes in the spirit of pull requests in Distributed Version Control Systems (DVCS). Second, the union of local fragments creates an opportunistic replication scheme that can be used by federated query engines to improve data availability [START_REF] Montoya | Fedra: Query Processing for SPARQL Federations with Divergence[END_REF][START_REF] Saleem | Daw: Duplicate-aware federated query processing over the web of data[END_REF]. Finally, update propagation between fragments is powered by live feeds as in DBpedia Live [START_REF] Morsey | Dbpedia and the live extraction of structured data from wikipedia[END_REF] or sparqlPuSH [START_REF] Passant | sparqlpush: Proactive notification of data updates in rdf stores using pubsubhubbub[END_REF].

Scientific issues arise concerning the consistency of these fragments. These questions have been extensively studied in Collaborative Data Sharing Systems (CDSS) [START_REF] Karvounarakis | Collaborative data sharing via update exchange and provenance[END_REF], Linked Data with adaptations of DVCS [START_REF] Sande | R&wbase:git for triples[END_REF][START_REF] Cassidy | Version control for rdf triple stores[END_REF] and replication techniques [START_REF] Ibáñez | Live linked data: Synchronizing semantic stores with commutative replicated data types[END_REF][START_REF] Zarzour | srce: a collaborative editing of scalable semantic stores on p2p networks[END_REF]. Existing approaches follow a total replication approach, i.e., full datasets or their full histories are completely replicated at each participant or they require coordination to maintain consistency.

In this paper, we propose Col-Graph, a new approach to solve the availability, scalability and writability problems of Linked Data. In Col-Graph, we define fragments as SPARQL CONSTRUCT federated queries, creating a collaboration network, propose a consistency criterion and define a coordination-free protocol to maintain fragments incrementally without reevaluating the query on the data source. The protocol counts the derivations of triples for data synchronization and keeps provenance information to make decisions in case of a conflict.

We analyze the protocol's complexity and evaluate experimentally its efficiency. The main factors that affect Col-Graph performance are the number of concurrent insertions of the same data, the connectivity of the collaboration network and the overlapping between the fragments. Experimentations show that the overhead of storing counters is less than 6% of the fragment size, whenever there are up to 1,000 concurrent insertions or up to 10 × 10 16 simple paths between the source and the dataset. Synchronization is faster than fragment reevaluation up to when 30% of the triples are updated. We also report better performance on synthetically generated social networks than on random ones.

Section 2 describes Col-Graph general approach and defines the correction criterion. Section 3 formalizes Col-Graph protocol. Section 4 details the complexity analysis. Section 5 details experimentations. Section 6 summarizes related work. Finally, section 7 presents the conclusions and outlines future work.

Col-Graph Approach and Model

In Col-Graph, consumers create fragments, i.e., partial copies of other datasets, based on simple federated CONSTRUCT queries, allowing them to perform intensive queries locally on the union of fragments and make updates to enhance data quality. In Figure 1, Consumer_1 copies fragments from DBPedia and DrugBank, Consumer_2 copies fragments from DBPedia and MusicBrainz and Consumer_3 copies fragments from Consumer_2 and Consumer_3.

Consumers publish the updated dataset, allowing others to also copy fragments from them. They can also contact their data sources to ask them to incorporate their updates, in the spirit of DVCS pull requests. Updates at the fragment's source are propagated to consumers using protocols like sparqlPuSH [START_REF] Passant | sparqlpush: Proactive notification of data updates in rdf stores using pubsubhubbub[END_REF] Fig. 1: Federation of Writable Linked Data or live feeds [START_REF] Morsey | Dbpedia and the live extraction of structured data from wikipedia[END_REF]. As replicated fragments could exist on several endpoints, adequate federated query engines could profit to improve general data availability and scalability [START_REF] Montoya | Fedra: Query Processing for SPARQL Federations with Divergence[END_REF][START_REF] Saleem | Daw: Duplicate-aware federated query processing over the web of data[END_REF]. Following this approach, data providers can share the query load and the data curation process with data consumers. Since data consumers become also data providers, they can gain knowledge of queries targeting their fragments.

We consider that each Linked Data participant holds one RDF-Graph and exposes a SPARQL endpoint. For simplicity, we use P to refer to the RDF-Graph, the SPARQL endpoint or the name of a participant when is not confusing. An RDF-Graph is defined as a set of triples (s, p, o), where s is the subject, p is the predicate and o is the object. We suppose that a participant wants to copy fragments of data from other participants, i.e., needs to copy a subset of their RDF-Graphs for a specific application [START_REF] Schandl | Replication and versioning of partial rdf graphs[END_REF] as in Figure 1.

Definition 1 (Fragment). Let S be a SPARQL endpoint of a participant, a fragment of the RDF-Graph published by S, F [S], is a SPARQL CONSTRUCT federated query [22] where all graph patterns are contained in a single SERVICE block with S as the remote endpoint. We denote as eval(F [S]) the RDF-Graph result of the evaluation of F [S].

A fragment F [S] enables a participant T to make a copy of the data of S that answers the query. We denote the result of the evaluation of F [S] materialized by a participant T as F [S]@T , i.e., a fragment of source S materialized at target T . A fragment is partial if F [S]@T ⊂ S or full if F [S]@T = S. The local data of a participant is composed of its own data union the fragments copied from other participants. We call the directed labeled graph where the nodes are the participants and the edges (S; T ) labeled with fragments a Collaboration Network, CN . A CN defines how data are shared between participants and how updates are propagated. Participants can query and update the fragments they materialize, e.g., Consumer_1 in figure 1 can modify the fragments copied from DBPedia and DrugBank using SPARQL 1.1 Update [23] When a source in a CN updates its data, the materialized fragments may become outdated. Fragments could be re-evaluated at the data source, but if the data source has a popular knowledge base, i.e., many other participants have defined fragments on it, the continuous execution of fragments would decrease the availability of the source's endpoint. To avoid this, a participant may synchronize its materialized fragment incrementally by using the updates published by the source. Some popular data providers such as DBpedia Live [START_REF] Morsey | Dbpedia and the live extraction of structured data from wikipedia[END_REF] and MusicBrainz3 publish live update feeds.

To track updates done by a participant, we consider an RDF-triple as the smallest directly manageable piece of knowledge [START_REF] Ognyanov | Tracking changes in rdf(s) repositories[END_REF] and the insertion and deletion of an RDF-triple as the two basic types of updates. Each update is globally uniquely identifiable and it turns the RDF-Graph into a new state. SPARQL 1.1 updates are considered as an ordered set of deleted and/or inserted triples. Each time we refer to an update, we implicitly refer to the inserted/deleted triple. Blank nodes are considered to be skolemized, i.e., also globally identifiable 4 .

Incrementally synchronizing a materialized fragment using only the updates published by a data source and the locally materialized fragment without reevaluating the fragment on the data source requires to exclude join conditions from fragments [START_REF] Gupta | Data integration using self-maintainable views[END_REF], therefore, we restrict to basic fragments [START_REF] Verborgh | Web-scale querying through linked data fragments[END_REF], i.e., fragments where the query has only one triple pattern.

Figure 2 illustrates a CN and how updates are propagated on it. P 1 starts with data about the nationality and KnownFor properties of M _P erey (prefixes are omitted for readability). P 2 materializes from P 1 all triples with the knownF or property. With this information and its current data, P 2 inserts the fact that M _P erey discovered Francium. On the other hand, P 3 materializes from P 1 all triples with the nationality property. P 3 detects a mistake (nationality should be F rench, not F rench_P eople) and promptly corrects it. P 4 constructed a dataset materializing from P 2 the fragment of triples with the property discoverer the fragment of triples with the property nationality from P 3. P 1 trusts P 4 about data related to M _P erey, so she materializes the relevant fragment, indirectly consuming updates done by P 2 and P 3.

Updates performed on materialized fragments are not necessarily integrated by the source, e.g, the deletion done by P 3 did not reach P 1, therefore, equivalence between source and materialized fragment cannot be used as consistency criterion for CN s. Intuitively, each materialized fragment must be equal to the evaluation of the fragment at the source after applying local updates, i.e., the ones executed by the participant itself and the ones executed during synchronization with other fragments. Definition 2 (Consistency Criterion). Let CN = (P, E) be a collaboration network. Assume each P i ∈ P maintains an ordered set of uniquely identified updates ∆ Pi with its local updates and the updates it has consumed from the sources of the fragments F [P j ]@P i it materializes. Given a ∆ P , let ∆ F [S] P be the ordered subset of ∆ P such that all updates concern F [S], i.e., that match the graph pattern in F [S]. Let apply(P i , ∆) be a function that applies an ordered set of updates ∆ on P i .

CN is consistent iff when the system is idle, i.e., no participant executes local updates or fragment synchronization, then:

(∀P i , P j ∈ P : F [P i ]@P j = apply(eval(F [P i ]), ∆ F [Pi] Pj \ ∆ Pi ) The ∆ F [Pi] Pj
\ ∆ Pi term formalises the intuition that we need to consider only local updates when evaluating the consistency of each fragment, i.e., from the updates concerning the fragment, remove the ones coming from the source.

Unfortunately, applying remote operations as they come does not always comply with Definition 2 as shown in Figure 3a: P 3 synchronizes with P 1, applying the updates identified as P 1#1 and P 1#2, then with P 2, applying the updates identified as P 2#1 and P 2#2, however, the fragment materialized from P 2 is not consistent. Notice that, had P 3 synchronized with P 2 before than with P 1, its final state would be different ((s, p, o) would exist) and the fragment materialized from P 1 would not be consistent.

P1: (s,p,o) (s,q,o) P2: (s,p,o) P1#1 Ins(s,p,o) P1#2 Ins(s,q,o) * P2#1 Ins(s,p,o) P2#2 Del(s,p,o) * v v P3: (s,p,o) (s,q,o) P1#1 Ins(s,p,o) P1#2 Ins(s,q,o) P2#1 Ins(s,p,o) P2#2 Del(s,p,o) F [P 1]@P 3 = apply({(s, p, o), (s, q, o)}, (P 2#1 Ins(s, p, o), P 2#2 Del(s, p, o))) F [P 2]@P 3 = apply(∅, (P 1#1 Ins(s, p, o))) P 1#2 Ins(s, q, o)))
(a) Applying updates as they come does not comply with the correction criterion.

P1: (s,p,o) ֒→ 1 (s,q,o) ֒→ 1 P2: (s,p,o) ֒→ 1 P1#1 (s,p,o) ֒→ 1 P1#2 (s,q,o) ֒→ 1 * P2#1 (s,p,o) ֒→ 1 P2#2 (s,p,o) ֒→ -1 * w w P3: (s,p,o) ֒→ 1 (s,q,o) ֒→ 1 P1#1 (s,p,o) ֒→ 1 P1#2 (s,q,o) ֒→ 1 P2#1 (s,p,o) ֒→ 1 P2#2 (s,p,o) ֒→ -1 F [P 1]@P 3 = apply({(s, p, o) ֒→ 1, (s, q, o) ֒→ 1}, (P 2#1 (s, p, o) ֒→ 1 (P 2#2 (s, p, o) ֒→ -1)) F [P 2]@P 3 = apply(∅, (P 1#1 (s, p, o) ֒→ 1, P 1#2 (s, q, o) ֒→ 1)) (b) The Annotated RDF-Graph enables a consistent Collaboration Network

A Protocol for Synchronization of Basic Fragments

To achieve consistency in every case, we propose, in the spirit of [START_REF] Green | Reconcilable differences[END_REF], to count the number of insertions and deletions of a triple, i.e., we annotate each RDF-triple with positive or negative integers, positive values indicate insertions and negative values deletions. This allows a uniform representation of data and updates, yielding a simple way to synchronize fragments. Definition 3 (Annotated RDF-triple, Graph and Update).

1. Let t an RDF-triple and z ∈ Z * . t ֒→ z is an annotated RDF-triple, with t being the triple and z the annotation. 2. An annotated RDF-Graph G A is a set of annotated RDF-triples such that (∀t, z|t ֒→ z ∈ G A : z > 0) 3. An annotated update u A is represented by an annotated RDF-triple. More precisely, t ֒→ 1 for insertion of t and t ֒→ -1 for deletion of t.

Annotations in RDF-Graphs count the number of derivations of a triple. An annotation value higher than one indicates that the triple exists in more than one source or there are several paths in CN leading from the source of the triple to the participant. Annotations in updates indicate, if positive, that z derivations of t were inserted; if negative, that z derivations of t were deleted. For example, an annotated RDF-triple t 1 ֒→ 2 means that either t 1 has been inserted by two different sources or the same insert arrived through two different paths in the CN . The annotated update t 2 ֒→ -1 means that t 2 was deleted at one source or by some participant in the path between the source and the target; t 3 ֒→ -2 means that either t 3 was deleted by two sources or by some participant in the path between two sources and the target.

To apply annotated updates to annotated RDF-Graphs, we define an Update Integration function: Definition 4 (Update Integration). Let A the set of all annotated RDF-Graphs and B the set of all annotated updates. Assume updates arrive from source to target in FIFO order. The Update Integration function ⊎ : A × B → A takes an annotated RDF-Graph G A ∈ A and an annotated update t ֒→ z ∈ B:

G A ⊎ t ֒→ z =      G A ∪ {t ֒→ z} if (∄w : t ֒→ w ∈ G A ) G A \ {t ֒→ w} if t ֒→ w ∈ G A ∧ w + z ≤ 0 (G A \ {t ֒→ w}) ∪ {t ֒→ w + z} if t ֒→ w ∈ G A ∧ w + z > 0
The first piece of the Update Integration function handles incoming updates of triples that are not in the current state. As we are assuming FIFO in the update propagation from source to target, insertions always arrive before corresponding deletions, therefore, this case only handles insertions. The second piece handles deletions, only if the incoming deletion makes the annotation zero the triple is deleted from the current state. The third piece handles deletions that do not make the annotation zero and insertions of already existing triples by simply updating the annotation value.

We now consider each participant has an annotated RDF-Graph G A and an ordered set of annotated updates U A . SPARQL queries are evaluated on the RDF-Graph {t | t ֒→ z ∈ G A }. SPARQL Updates are also evaluated this way, but their effect is translated to annotated RDF-Graphs as follows: the insertion of t to the insertion of t ֒→ 1 and the deletion of t to the deletion of the annotated triple having t as first coordinate. Specification 1.1 details the methods to insert/delete triples and synchronize materialized fragments. Figure 3b shows the fragment synchronization algorithm in action. A proof of correctness follows the same case-base analysis developed to prove [START_REF] Ibáñez | Live linked data: Synchronizing semantic stores with commutative replicated data types[END_REF].

Provenance for Conflict Resolution

In section 3 we solved the problem of consistent synchronization of basic fragments. However, our consistency criterion is based on the mere existence of triples, instead of on the possible conflicts between triples coming from different fragments and the ones locally inserted. Col-Graph's strategy in this case is that each participant is responsible for checking the semantic correctness of its dataset, as criteria often varies and what is semantically wrong for one participant, could be right for another. Participants can delete/insert triples to fix what they consider wrong. Participants that receive these updates can edit in turn if they do not agree with them.

In the event of two triples being semantically incompatible, the main criteria to choose which one of them delete is the provenance of the triples. With this

Annotated Graph G A , Ordered S e t ∆PID void insert(t) : pre : t / ∈ {t ′ |t ֒→ x ∈ G A } G A := G A ∪ t ֒→ 1 Append(∆PID, t ֒→ 1) void delete(t) : pre : t ∈ {t ′ |t ′ ֒→ x ∈ G A } G A := G A ⊎ t ֒→ -z Append(∆PID, t ֒→ -z) void sync(F [Px], ∆Px) : f o r t ֒→ z ∈ ∆Px : i f t ֒→ z / ∈ ∆PID : G A := G A ⊎ t ֒→ z Append(∆PID, t ֒→ z)
Specification 1.1: Class Participant when triples are annotated with elements of Z.

IRI PID , Annotated Graph G A , Ordered S e t ∆PID void insert(t) : pre : t / ∈ {t ′ |t ֒→ x ∈ G A } G A := G A ∪ t ֒→ PID Append(∆PID, t ֒→ PID) void delete(t) : pre : t ∈ {t ′ |t ′ ֒→ x ∈ G A } G A := G A ⊎ t ֒→ -m Append(∆PID, t ֒→ -m) void sync(F [Px], ∆Px) : f o r t ֒→ m ∈ ∆Px : i f t ֒→ m / ∈ ∆PID : G A := G A ⊎ t ֒→ m Append(∆PID, t ֒→ m)
Specification 1.2: Class Participant when triples are annotated with elements of the monoid M. information, the decision can be made based on the trust on its provenance. As in [START_REF] Karvounarakis | Collaborative data sharing via update exchange and provenance[END_REF], we propose to substitute the integer annotations of the triple by an element of a commutative monoid that embeds (Z, +, 0). We recall that a commutative monoid is an algebraic structure comprised by a set K, a binary, associative, commutative operation ⊕ and an identity element

0 K ∈ K such that (∀k ∈ K | k ⊕ 0 K = k; a monoid M = (K, ⊕, 0 K ) embeds another monoid M ′ = (K ′ , ⊘, 0 K ′ ) iff there is a map f : K → K ′ such that f (0 K ) = f (0 K ′ ) and (∀a, b ∈ K : f (a ⊕ b) = f (a) ⊘ f (b)).
If we annotate with a monoid that embeds (Z, +, 0), only a minor change is needed in our synchronization algorithm to achieve consistency. This monoid is used to encode extra provenance information. Definition 5. Assume each participant in the collaboration network has a unique ID, and let X be the set of all of them. Let M = (Z[X], ⊕, 0) be a monoid with:

1. The identity 0. 2. The set Z[X] of polynomials with coefficients in Z and indeterminates in X.

3. The polynomial sum ⊕, for each monomial with the same indeterminate:

aX ⊕ bX = (a + b)X 4. M embeds (Z, +, 0) through the function f (a 1 X 1 ⊕ • • • ⊕ a n X n ) = n 1 a i
Each time a participant inserts a triple, she annotates it with its ID with coefficient 1. The only change in definition 4 is the use of ⊕ instead of +. Speci- When annotating with Z, the only information encoded in triples is their number of derivations. M adds (i) Which participant is the author of the triple. A triple stored by a participant P with an annotation comprised by the sum of n monomials indicates that the triple was inserted concurrently by n participants from which there is a path in CN to P . (ii) The number of paths in the Collaboration Network in which all edges concern the triple, starting from the author(s) of the triple to this participant, indicated by the coefficient of the author's ID.

Figure 4 compares annotations with Z versus annotations with M . In the depicted collaboration network, the fact (s,p,o) is inserted concurrently by P1 and P3, (s,p,v) is inserted concurrently by P2 and P5 and (s,p,r) inserted only by P4. When the synchronization is finished, P5 notices that it has three triples with s and p as subject and predicate but different object values. If P5 wants to keep only one of such triples based on trust, the Z annotations (4a) do not give her enough information, while the M annotations (4b) give more information for P 5 to take the right decision. She can know that the triple (s, p, o) was inserted by two participants P 1 and P 3, while (s, p, r) was only inserted by P 4 and that (s, p, v) was inserted by P 2 and herself.

Complexity Analysis

In this section, we analyze the complexity in time, space and traffic of RDF-Graphs annotated with M and their synchronization, to answer the question: how much does it cost to guarantee the correctness of a collaboration network?.

Concerning time complexity, from specifications 1.1 and 1.2, we can see that for the insert and delete methods is constant. For the synchronization of a fragment F [P x ]@P y , the complexity is n(x 1 + x 2 ) where n is the number of incoming updates, x 1 the complexity of checking if an update is in ∆P y (which can be considered linear) and x 2 the complexity of the ⊎ function. For Z annotations, ⊎ is constant, for M is linear on the size of the largest polynomial.

Concerning space complexity, the overhead is the size of the annotations. For an annotated triple t at a participant P , the relevant factors are: (i) the set of participants that concurrently inserted t from which there is a path to P such that all edges concern t, that we will denote β t (ii) the number of paths to P in the collaboration network from the participants P 1 . . . P n that concurrently inserted t such that all edges concern t. For a participant P i , we denote this number as ρ t←Pi . Let sizeOf be a function that returns the space needed to store an object. Assume that the cost of storing ids is a constant ω. Then, for

t ֒→ z, z ∈ Z[x] we have sizeOf (z) = |β t |ω + Pi∈βt sizeOf (ρ t←Pi ). Therefore,
for each triple we need to keep a hash map from ids to integers of size |β t |. The worst case for |β t | is a strongly connected Collaboration Network CN where all participants insert t concurrently, yielding an array of size |CN | . The worst case for ρ t←Pi is a complete network, as the number of different simple paths is maximal and in the order of |CN |!

The size of the log at a participant P depends on two factors (i) the dynamics of P , i.e., the number of local updates it does. (ii) the dynamics of the fragments materialized by P , i.e., the amount of updates at the sources that concern them.

In terms of the number of messages exchanged our solution is optimal, only one contact with the update log of each source is needed. In terms of message size, the overhead is in principle the same as the space complexity. However, many compression techniques could be applied.

The solution described so far uses an update log that is never purged. Having the full update history of a participant has benefits like enabling historical queries and version control. However, when space is limited and/or updates occur often, keeping such a log could not be possible. To adapt our solution to data feeds we need to solve two issues: (i) How participants materialize fragments for the first time? (ii) How to check if an incoming update has been already received?

To solve the first issue, an SPARQL extension that allows to query the annotated RDF-Graph and return the triples and their annotations is needed, for example the one implemented in [START_REF] Wylot | Tripleprov: Efficient processing of lineage queries in a native rdf store[END_REF]. To solve the second issue, we propose to add a second annotation to updates, containing a set of participant identifiers φ u representing the participants that have already received and applied the update. When an update u is created, φ u is set to the singleton containing the ID of the author, when u is pushed downstream, the receiving participant checks if his ID is in φ u , if yes, u has already been received and is ignored, else, it is integrated, and before pushing it downstream it adds its ID to φ u . Of course, there is a price to pay in traffic, as the use of φ increases the size of the update. The length of φ u is bounded by the length of the longest simple path in the Collaboration-Network, which in turn is bounded by the number of participants.

To summarize, the performance of our solution is mainly affected by the following properties of the CN: (i) The probability of concurrent insertion of the same data by many participants. The higher this probability, the number of terms of the polynomials is potentially higher. (ii) Its connectivity. The more connected, the more paths between the participants and the potential values of ρ are higher. If the network is poorly connected, few updates will be consumed and the effects of concurrent insertion are minimized. (iii) The overlapping between the fragments. If all fragments are full, all incoming updates will be integrated by every participant, maximizing the effects of connectivity and concurrent insertion. If all fragments are disjoint, then all updates will be integrated only once and the effects of connectivity and concurrent insertion will be neutralized.

Experimentations

We implemented specification 1.2 on top of the SPARQL engine Corese5 v3.1.1. The update log was implemented as a list of updates stored in the file system. We also implemented the φ annotation described in section 4 to check for double reception. We constructed a test dataset of 49999 triples by querying the DBpedia 3.9 public endpoint for all triples having as object the resource http://dbpedia.org/resource/France. Implementation, test dataset, and instructions to repeat the experiments are freely available 6 .

Our first experiment studies the execution time of our synchronization algorithm. The goal is to confirm the linear complexity derived in section 4 and to check its cost w.r.t fragment re-evaluation. We defined a basic fragment with the triple pattern ?x :ontology/birthPlace ?z (7972 triples 15% of the test dataset's size). We loaded the test dataset in a source, materialized the fragment in a target and measured the execution time when inserting and when deleting 1, 5, 10, 20, 30, 40 and 50% of triples concerning the fragment. As baseline, we set up the same datasets on two RDF-Graphs and measured the time of clearing the target and re-evaluating the fragment. Both source and target were hosted on the same machine to abstract from latency.

We used the Java MicroBenchmark Harness7 v. 0.5.5 to measure the average time of 50 executions across 10 JVM forks with 50 warm-up rounds, for a total of 500 samples. Experiments were run on a server with 20 hyperthreaded cores with 128Gb of ram an Linux Debian Wheezy. Figure 5 shows a linear behaviour, consistent with the analysis in section 4. Synchronization is less expensive than re-evaluation up to approx. 30% of updates. We believe that a better implementation that takes full advantage of streaming, as Corese does by processing data in RDF/XML, could improve performance. Basic fragments are also very fast to evaluate, we expect than in future work, when we can support a broader class of fragments, update integration will be faster in most cases.

Our second experiment compares the impact on annotation's size produced by two of the factors analyzed in section 4: concurrent insertions and collaboration network connectivity, in order to determine which is more significant. We loaded the test dataset in: (i) An RDF-Graph. (ii) An annotated RDF-Graph, simulating n concurrent insertions of all triples, at n annotated RDF-Graphs with id http://participant.topdomain.org/$i$, with i ∈ [0, n] (iii) An annotated RDF-Graph, simulating the insertion of all triples in other graph with id "http://www.example.org/participant", arriving to this one through m different simple paths, and measured their size in memory on a Macbook Pro running MacOS Lion with java 1.7.0_10-ea-b13 and Java HotSpot(TM) 64-Bit Server VM (build 23.6-b04, mixed mode).

Figure 6 shows the results. Both cases represent nearly the same overhead, between 5 and 6 percent. Concurrency makes annotation's size grow sub-linearly. With respect to path number, annotation's size grows even slower , however, after 10×10 17 paths, the long type used in our implementation overflows, meaning that in scenarios with this level of connectivity, the implementation must use BigInt arithmetics. In conclusion, after paying the initial cost of putting annotations in place, Col-Graph can tolerate a high number of concurrent inserts and a high network connectivity.

The goal of our final experiment is to study the effect of network's topology on Col-Graph's annotation's size. We argue that the act of materializing fragments and sharing updates is socially-driven, therefore, we are interested in analyzing the behaviour of Col-Graph on social networks. We generated two sets of 40 networks with 50 participants each, all edges defining full fragments, one following the random Ërdos-Renyi model [START_REF] Erdös | On the evolution of random graphs[END_REF] and other following the social-network oriented Forest Fire model [START_REF] Leskovec | Graph evolution: Densification and shrinking diameters[END_REF]. Each networkset is composed of 4 subsets of 10 networks with densities {0.025, 0.05, 0.075, 0.1}. Table 1 shows the average of the average node connectivity of each network set. Social networks in are less connected than random ones, thus, we expect to have better performance.

We loaded the networks on the Grid5000 platform (https://www.grid5000. fr/) and made each participant insert the same triple to introduce full concurrency, thus, fixing the overlapping and concurrency parameter in their worst case. Then, we let them synchronize repeatedly until quiescence with a 1 hour timeout. To detect termination, we implemented the most naive algorithm: a central overlord controls the execution of the whole network . We measured the maximum and average coefficient values and the maximum and average number of terms of annotations.

Figure 7 shows the results for Forest Fire networks. The gap between the average and maximum values indicates that topology has an important effect: only few triples hit high values. From the Ërdos-Renyi dataset, only networks with density 0.025 and finished before timeout without having a significant difference with their ForestFire counterparts. These results suggest that high connectivity affects the time the network takes to converge, and, as the number of rounds to converge is much higher, the coefficient values should also be much higher. We leave the study of convergence time and the implementation of a better termination detection strategy for future work.

Related Work

Linked Data Fragments (LDF) [START_REF] Verborgh | Web-scale querying through linked data fragments[END_REF] proposes data fragmentation and replication as an alternative to SPARQL endpoints to improve availability. Instead of answering a complex query, the server publishes a set of fragments that corresponds to specific triple patterns in the query, offloading to the clients the responsibility of constructing the result from them. Col-Graph allows clients to define the 7: Performance of the synchronization algorithm when applied on networks generated with the Forest Fire model fragments based on their needs, offloading also the fragmentation. Our proposal also solves the problem of writability, that is not considered by LDF. [START_REF] Cassidy | Version control for rdf triple stores[END_REF][START_REF] Sande | R&wbase:git for triples[END_REF] adapt the Distributed Version Control Systems Darcs and Git principles and functionality to RDF data. Their main goal is to provide versioning to Linked Data, they do not consider any correctness criterion when networks of collaborators copy fragments from each other, and they do not allow fragmentation, i.e., the full repository needs to be copied each time. [START_REF] Ibáñez | Live linked data: Synchronizing semantic stores with commutative replicated data types[END_REF][START_REF] Zarzour | srce: a collaborative editing of scalable semantic stores on p2p networks[END_REF] use eventual consistency as correctness criterion. However, this requires that all updates to be eventually delivered to all participants, which is not compatible with fragmentation nor with socially-generated collaboration network. [START_REF] Schandl | Replication and versioning of partial rdf graphs[END_REF] proposes a partial replication of RDF graph for mobile devices using the same principles of SVN with a limited lifetime of local replica checkoutcommit cycle. Therefore, it is not possible to ensure synchronization of partial copies with the source since a data consumer has to checkout a new partial graph after committing changing to the data provider.

[9] formalizes an OWL-based syndication framework that uses description logic reasoning to match published information with subscription requests. Similar to us, they execute queries incrementally in response to changes in the published data. However, in their model consumers do not update data, and connection between consumers and publishers depends on syndication brokers.

Provenance models for Linked Data using annotations have been studied in [START_REF] Zimmermann | A general framework for representing, reasoning and querying with annotated semantic web data[END_REF][START_REF] Geerts | Algebraic structures for capturing the provenance of sparql queries[END_REF] and efficiently implemented in [START_REF] Wylot | Tripleprov: Efficient processing of lineage queries in a native rdf store[END_REF], showing several advantages with respect to named graphs or reification. The model in [START_REF] Geerts | Algebraic structures for capturing the provenance of sparql queries[END_REF] is based on provenance polynomials and is more general than the one we used, however, as basic fragments are a restricted class of queries, the M monoid suffices.

Collaborative Data Sharing Systems (CDSS) like Orchestra [START_REF] Karvounarakis | Collaborative data sharing via update exchange and provenance[END_REF] use Z-Relations and provenance to solve the data exchange problem in relational databases. CDSS have two requirements that we do not consider: support for full relational algebra in the fragment definition and strong consistency. However, the price to pay is limited scalability and the need of a global ordering on the synchronization operation, that becomes blocking [START_REF] Taylor | Reliable storage and querying for collaborative data sharing systems[END_REF]. Both drawbacks are not compatible with Linked Data requirements of scalability and participant's autonomy. Col-Graph uses the same tools to solve the different fragment synchronization problem, with an opposite trade-off: scalability and autonomy of participants in exchange of weaker consistency and limited expressiveness of fragment definitions.

Conclusions and Future Work

In this paper, we proposed to extend Linked Data federation to data consumers in order to improve its availability, scalability and data quality. Data consumers materialize fragments of data from data providers and put them at disposal of other consumers and clients. Adequate federated query engines can use these fragments to balance the query load among federation members. Fragments can be updated to fix errors, and these updates can be consumed by other members (including the original sources) to collaboratively improve data quality.

We defined a consistency criterion for networks of collaborators that copy fragments from each other and designed an algorithm based on annotated RDFtriples to synchronize them consistently. We analyzed the complexity of our algorithm in time, space and traffic, and determined that the main factors that affect performance are the probability of concurrent insertion, the connectivity of the collaboration network and the fragment overlapping.

We evaluated experimentally the incurred overhead using a 50k real dataset on our open source implementation, finding that in space, concurrency and connectivity represent approximately 6% of overhead each, and that it grows sublinearly; in time, our algorithm is faster than the reevaluation up to 30% of updated triples without taking in account latency. We also found that our algorithm performs better in socially generated networks than in random ones.

Future works include a large scale evaluation of Col-Graph focused on the effect of fragment overlapping, and using real dataset dynamics. We also plan to benchmark replication-aware federated query engines [START_REF] Montoya | Fedra: Query Processing for SPARQL Federations with Divergence[END_REF][START_REF] Saleem | Daw: Duplicate-aware federated query processing over the web of data[END_REF] on collaboration networks using Col-Graph to quantify the availability boost of our solution, and extend our model to handle dynamics on the fragment definitions themselves.

Fig. 2 :

 2 Fig. 2: Collaboration network with Basic Fragments. Underlined triples are the ones coming from fragments, triples preceded by a '+' are the ones locally inserted, struck-through triples are the ones locally deleted.

Fig. 3 :

 3 Fig. 3: Illustration of the consistency criterion. Rounded boxes represent the graphs, and shaded boxes the sequences of updates. * represents a full fragment.

Fig. 4 :

 4 Fig.4: Difference between annotating with Z (4a) versus annotating with M (4b). All fragments are full.

Fig. 5 :

 5 Fig. 5: Comparison of execution time (ms) between synchronization and fragment reevaluation. Error bars show the error at 95%.

  insertions (x × 100) (b) Simulation of concurrent insertions arriving through one path.

Fig. 6 :

 6 Fig. 6: Space Overhead of the Annotated Graph w.r.t a plain graph (PG). Both Concurrency and Connectivity represent approx. 6% of overhead each.

  Fig. 7: Performance of the synchronization algorithm when applied on networks generated with the Forest Fire model

Table 1 :

 1 Average node connectivities of the experimental network sets

	0.025 0.05 0.075 0.1
	Forest Fire 0.0863 0.2147 0.3887 0.5543
	Ërdos-Renyi 0.293 1.3808 2.5723 3.7378

http://musicbrainz.org/doc/MusicBrainz_Database#Live_Data_Feed

http://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/ #section-skolemization

http://wimmics.inria.fr/corese

https://code.google.com/p/live-linked-data/wiki/ColGraphExperiments

http://openjdk.java.net/projects/code-tools/jmh/

Acknowledgements: Some of the experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations. This work is supported by the French National Research agency (ANR) through the KolFlow project (code: ANR-10-CONTINT-025).


Meriam Chihi Bouaziz

Younes Boujelbene

Damien Bazin

The contagion of the subprime crisis to the U.S. Treasury bond Markets

Keywords: contagion, subprime CDOs, Treasury bond Markets, VAR model

The American Treasury bond markets have suffered catastrophic losses due to the subprime crisis, which erupted in 2007. We study in this paper the contagion of this crisis by examining the increase links between these markets and the U.S. subprime loan market. We use a VAR model considered most suitable for this purpose. Our study is based on the prices of subprime Asset-backed collateralized debt obligations (CDOs) and changes in U.S. Treasury bond yields. Our results support the hypothesis of contagion from the subprime crisis between the U.S. financial markets.

Introduction

The subprime crisis, born in the United States in 2007, paralyzed the structured credit market and resulted in catastrophic losses in the financial markets. Individuals and financial institutions in this country have been facing a severe credit crisis. This situation has resulted in a significant decrease in the liquidity of debt in almost all markets. In 2008, the subprime crisis has deepened and become the catalyst for a broader global financial crisis.

Federal Reserve has intervened repeatedly providing liquidity and financial guarantees for the markets. The massive intervention of the Treasury and the Federal Reserve in the financial markets had a goal to prevent a wider contagion of the crisis and the impact on other markets and sectors of the economy. Therefore, it was very important to understand the contagion phenomenon between financial markets. Extensive literature addressing the causes and effects of contagion has emerged since the 90s. We can cite as examples the work of [START_REF] Allen | Financial contagion[END_REF], [START_REF] Kyle | Contagion as a wealth effect[END_REF], [START_REF] Kodres | A rational expectations model of financial contagion[END_REF], Kiyotaki and Moore (2002), Kaminsky, Reinhart and Vegh (2003), [START_REF] Allen | Financial Intermediaries and Markets[END_REF], [START_REF] Brunnermeier | Market liquidity and funding liquidity[END_REF]Pedersen (2005, 2009), Longstaf. F (2008)(2009)(2010).

We discuss in this paper the financial contagion effects from the subprime crisis on the U.S. Treasury bond markets. We adopt an approach of testing whether an increase in inter-market links from one period to another between the subprime Asset-backed collateralized debt obligations (CDOs) market and Treasury bond markets during the subprime crisis. The choice of this approach is motivated by the standard definition in the literature on contagion as "a change in market linkages after a stressful period" [START_REF] Forbes | No contagion, only interdependence: Measuring stock market comovements[END_REF]). We use a VAR model for three sub-periods: a pre-crisis period (2006), a period representing the subprime crisis (2007) and a period representing the global crisis ( 2008)). This model allows us to directly examine whether cross-market linkages during the subprime crisis of 2007 differ from those in the other two sub-periods.

The remainder of this paper is organized as follows: the second section describes our econometric methodology. The third section summarizes our empirical results, and the fourth section is our conclusion.

II-Econometric Methodology

The VAR model is presented as follows:

1 p t k t k k t k t k Y Y ABX HE             (1.1)
where t ABXHE is the exogenous variable representing one of five sub-indices, t  is the vector of canonical residues, k  is the matrix of coefficients, k is the lags number chosen based on the information criteria AIC and the Schwartz and t Y is the dependent variable.

1-year Treasury bond market

1 1 1 k t k t k k t k t i yaerTY yaerTY ABXHA               1 1 1 k t k t k k t k t i yaerTY yaerTY ABXHAA               1 1 1 k t k t k k t k t i yaerTY yaerTY ABXHAAA               1 1 1 k t k t k k t k t i yaerTY yaerTY ABXHBBB               1 1 1 _ k t k t k k t k t i yaerTY yaerTY ABXHBBB              2. 10-year Treasury bond market 1 10 10 k t k t k k t k t i yaerTY yaerTY ABXHA              1 10 10 k t k t k k t k t i yaerTY yaerTY ABXHAA               1 10 10 k t k t k k t k t i yaerTY yaerTY ABXHAAA               1 10 10 k t k t k k t k t i yaerTY yaerTY ABXHBBB               1 10 10 k t k t k k t k t i yaerTY yaerTY ABXHBBB              III. Empirical results

Data and descriptive statistics

As return measures in the market for subprime Asset-backed security CDOs in trouble, we use the weekly variations of the ABX-HE. In total, we have five of the series, each representing a different credit rating, which is designated by: ABX-HE-AAA, ABX-HE-AA, ABX-HE-A, ABX-HE-BBB, and ABX -HE-BBB_. These are the closing prices of the ABX-HE index, obtained from the Markit Group Ltd, for the three years since the inception of the ABX-HE (the January 19, 2006 until December 31, 2008).

To detect the changes in U.S. Treasury bond markets, we use the weekly variations (over the same period for returns of ABX-HE) to a constant maturity of the one-and ten-year Treasury yields (obtained from the website of the Federal Reserve Board). According to table .1. our study shows that during the pre-crisis period, the average yield is generally low and positive for different sub-indexes. We note that all return series have negative average returns in 2007-2008 when they were positive in 2006. These series have a low yield and very high risk between 2007 and 2008. We conclude, therefore, that these markets are characterized by high volatility.

Figure.1. Evolution of ABX-HE index

Tableau.1. Descriptive statistics

The results of normality test allow us to reject the normality assumption regarding the Kurtosis and Skewness, which raises a problem with the asymmetric preferences of financial actors; the latters are naturally more concerned about their risk of loss as their chances of gain.

Results of the VAR models

Table .2. presents the results of the estimation of VAR models, where each VAR is estimated separately for the year indicated. We also report the P value for Fisher's test of the hypothesis that the coefficients are jointly equal to zero ( 1 2 3 4 0         ). In this specification, t Y refers to the variable representing the Treasury bond markets, which appear as dependent variables. The ABX-HE refers to variations in the ABX-HE indices; including its own lagged values appear as explanatory variables.

Table. 2. Estimation results of the VAR models

Our results reported in table .2. show that all of the coefficients k  , reflecting the predictive ability of the changes in the five sub-indices ABX-HE for the treasury bond yields markets, are not significant in 2006. This is expected since the CDOs market is much less liquid than the Treasury bond market. Thus, in ordinary circumstances, it is anticipated that there will be very little information useful in predicting changes in Treasury rates by ABX-HE indices returns. This factor becomes significant with a positive signs in 2007 for the subindices ABX-HE A, BBB and BBB_. This result indicates that changes in ABX HE indices have predictive power and guarantee a Granger causality in regard to changes in Treasury rates. In addition, all the five subindex of ABXHE have a significant predictive power in forecasting 10 years Treasury yields for about four weeks. The significant and positive signs of the coefficients k  in 2007 indicate that a negative shock to the ABX-HE returns translates a decline in Treasury yields, which in turn implies an increase in the value of Treasury bonds. These results are consistent with a flight to quality in the market for Treasury bond in response to subprime market shocks. Finally, the predictive ability of the ABX-HE returns for the Treasury bond yields largely disappears in 2008. The exception is that the Fisher statistic for the ABX-HE-BBB is significant at the 5% level for the 10-year Treasury bond market.

In summary, the beginning of the subprime crisis has led to a significant change in the relationship between ABX-HE returns and Treasury bond yields changes. During the crisis, the explanatory power of the Treasury yield becomes significant. Such a relationship was absent in pre-crisis period, when the Treasury bond markets was very liquid. Once the subprime crisis has evolved into another form, the CDOs represented by the ABX-HE index are no longer a vector of contagion and the relationship between the ABX-HE returns and the Treasury bond yields returned to its pre-crisis nature. Our results strongly support the idea that the subprime crisis of 2007 has been accompanied by financial contagion and that shocks in the market for CDOs were transmitted to the Treasury bond markets.

IV. Conclusion

The subprime crisis of 2007 provides an ideal opportunity to study the effects of contagion in financial markets. Motivated by the definition of contagion proposed by [START_REF] Forbes | No contagion, only interdependence: Measuring stock market comovements[END_REF] we estimated five VAR models for each of treasury-bond markets. We tested the changes in the relationship between the CDO market represented by the five sub-indices ABX-HE and the Treasury bond markets represented by the changes in the treasury bonds yields. To do this, we divided the full period into three sub-periods: a pre-crisis period (2006), a period representing the subprime crisis (2007) and a period representing the global crisis (2008).

Our results show a significant causal relationship between the ABX-HE returns and changes in the Treasury yields. This relationship is due to the subprime crisis of 2007. Indeed, Treasury bond prices rose in response to negative shocks to the subprime market, which supports the model of flight to quality. This effect is much stronger for long-term Treasury bonds than for those of short-term.

Our study resulted in strong evidence of contagion in financial markets during the subprime crisis in 2007. These links disappear in 2008 once this crisis is a global financial one. The perturbations appear to spread from the subprime market to the Treasury bond ones at the beginning of the crisis when losses of subprime loans were the main concern. However, after the collapse of major financial institutions and once the potential of a global depression has become widespread in 2008, the subprime market did not work as a vector of contagion of the other markets. This finding is consistent with the usual vision of contagion that is identified when there is a significant but temporary connection between the various financial markets after a negative shock is realized.

Figure. 1 .

 1 Figure.1. represents the time series of five sub-indices ABX-HE for the entire period. This figure shows that ABX-HE indices were generally almost constant over a large period of 2006, although the sub-indices ABXHE

Figure. 2 .Figure. 2 .

 22 Figure. 2. The weekly ABXHE returnsRABXHEA


Yves Décanini
email: decanini@univ-corse.fr

Antoine Folacci
email: folacci@univ-corse.fr

Mohamed Ould

El Hadj

Giant black hole ringings induced by massive gravity

Keywords: numbers: 04.70.Bw, 04.30.-w, 04.25.Nx, 04.50.Kd

A distorted black hole radiates gravitational waves in order to settle down in one of the geometries permitted by the no-hair theorem. During that relaxation phase, a characteristic damped ringing is generated. It can be theoretically constructed from the black hole quasinormal frequencies (which govern its oscillating behavior and its decay) and from the associated excitation factors (which determine intrinsically its amplitude) by carefully taking into account the source of the distortion. Here, by considering the Schwarzschild black hole in the framework of massive gravity, we show that the excitation factors have an unexpected strong resonant behavior leading to giant ringings which are, moreover, slowly decaying. Such extraordinary black hole ringings could be observed by the next generations of gravitational wave detectors and allow us to test the various massive gravity theories or their absence could be used to impose strong constraints on the graviton mass.

Introduction.-Gravitational waves, a major prediction of Einstein's general relativity, should be observed directly in a near future by the next generations of gravitational wave detectors. Another fascinating prediction of Einstein's theory, the existence of black holes (BHs), should be simultaneously confirmed. Indeed, if in its final stage the astrophysical process generating the observed gravitational radiation involves a distorted BH, the signal is then dominated, at intermediate time scales, by a characteristic damped ringing. It is due to the BH which radiates away all its distortions in the form of gravitational waves and relaxes toward a state permitted by the no-hair theorem. The frequencies and decay rates describing that ringing define the complex resonance spectrum of the BH. They are linked to its quasinormal modes (QNMs) [1][2][3][4], i.e., to those mode solutions of the wave equation which propagate inward at the horizon and outward at spatial infinity, and they can be considered as the BH fingerprint : they indicate beyond all doubt the existence of a horizon and they could be used to determine unambiguously the mass as well as the angular momentum of the BH.

These last years, generalizations of general relativity mediated by a massive spin-2 particle are the subject of intense activity (see Ref. [5] for a recent review). They have their source in the 70-year old Fierz-Pauli theory [6]. They are motivated by purely theoretical considerations (the study of the deformations of general relativity with the graviton mass as deformation parameter) but they also arise from field theories in spacetimes with extra dimensions. Furthermore, and this is surely the main raison of their success, they could explain, without dark energy, the accelerated expansion of the present Universe. Of course, a hypothetical massive graviton is surely an ultralight particle (see Ref. [7] for a description of the experimental constraints on the graviton mass but note that the mass limit strongly depends on the theory considered).

It is therefore natural to study BH perturbations and to reconsider gravitational radiation from BHs in massive gravity. It is only very recently that some works on this subject by Babichev and Fabbri [8] and by Brito, Cardoso and Pani [9,10] have been achieved. They mainly discuss the fundamental problem of BH stability and therefore the existence of BHs in massive gravity. Of course, this depends on the model of gravity considered but, once we assume stability, it becomes really interesting to work on the structure of the signal emitted by a distorted BH with in mind the possibility to test, in a near future, the various massive spin-2 field theories with gravitational wave detectors.

Since the seventies, an increasing number of frequencyand time-domain studies dealing with massive fields propagating in BH spacetimes have highlighted the important modifications induced by the mass parameter which concern more or less directly the signal emitted by a distorted BH : (i) the resonance spectrum is enriched by the complex frequencies corresponding to quasibound states (see Refs. [11][12][13][14] for important pioneering works and Ref. [9] for a recent study in massive gravity); (ii) as the mass parameter increases, the quasinormal frequencies migrate in the complex plane, a behavior observed numerically by various authors (see, e.g., Refs. [15,16] for pioneering works and Ref. [9] for a recent study in massive gravity) and analytically described recently [17,18]; (iii) at very late time (i.e., after the quasinormal ringing), the signal emitted by the relaxing BH is not described by the usual power-law tail behavior [19] but, roughly speaking, by oscillations with a slowly-decaying amplitude (see, e.g., Ref. [20] as well as Ref. [21] for a recent study in massive gravity).

In a future article [START_REF] Decanini | Work in preparation[END_REF], we intend to discuss as fully as possible a new effect with amazing consequences : for massive bosonic fields in the Schwarzschild spacetime, the excitation factors of the QNMs have a strong resonant behavior which induces giant ringings. It is a totally unexpected effect. Indeed, until now it was assumed that, for massive fields, quasinormal ringings are less easily excited (see the introduction of Ref. [START_REF] Rosa | [END_REF] and references therein). We shall describe this effect numerically and confirm it analytically from semiclassical considerations based on the properties of the unstable circular geodesics on which a massive particle can orbit the BH.

In this letter, we only consider the massive spin-2 field because of its theoretical importance and due to the fascinating observational consequences that our results predict for such a field. We limit our study to the Fierz-Pauli theory in the Schwarzschild spacetime [9] which can be obtained, e.g., by linearization of the ghost-free bimetric theory of Hassan, Schmidt-May and von Strauss discussed in Ref. [24] and which is inspired by the fundamental work of de Rham, Gabadadze and Tolley [25,26]. Furthermore, we mainly focus on the odd-parity ℓ = 1 mode of this field (similar results can be obtained for the other modes -see also Ref. [START_REF] Decanini | Work in preparation[END_REF]) and on the associated QNMs. Our letter is organized as follows. We first establish numerically the resonant behavior of the excitation factor of the (ℓ = 1, n = 0) QNM (and briefly discuss its overtones). It occurs in a large domain around a critical value of the mass parameter where the QNM is, in addition, weakly damped. As a consequence, it induces giant and slowly decaying ringings. These are constructed directly from the retarded Green function (an intrinsic point of view) and we compare them with the ringing generated by the odd-parity (ℓ = 2, n = 0) QNM of the massless theory which, in the context of Einstein gravity, provides one of the most important contribution to the BH ringing. With in mind observational considerations, it is necessary to check that a realistic perturbation describing the BH distortion does not neutralize the resonant effect previously discussed and to study ringings constructed from the quasinormal excitation coefficients (an extrinsic point of view) because they permit us to include the contribution of the perturbation into the BH response [27]. We then describe the perturbation by an initial value problem, an approach which has regularly provided interesting results [27][28][29]. We show that the excitation coefficient of the (ℓ = 1, n = 0) QNM also has a resonant behavior which still leads to giant and slowly decaying ringings. In a conclusion, we discuss some possible extensions of our work and its interest for gravitational wave astrophysics and theoretical physics.

Throughout this letter, we display our numerical results by using the dimensionless coupling constant α = 2M µ/m P 2 (here M , µ and m P = c/G denote respectively the mass of the BH, the rest mass of the graviton and the Planck mass). We adopt units such that = c = G = 1 and assume a harmonic time dependence exp(-iωt) for the spin-2 field. We describe the exterior of the Schwarzschild BH by using both the radial coordinate r ∈]2M, +∞[ and the so-called tortoise coordinate

r * ∈] -∞, +∞[ given by r * (r) = r + 2M ln[r/(2M ) -1].
Resonant behavior of the quasinormal excitation factors and associated "intrinsic" giant ringings.-In Schwarzschild spacetime, the partial amplitude φ(t, r) describing the odd-parity ℓ = 1 mode of the massive spin-2 field satisfies [9] (the angular momentum index ℓ = 1 will be, from now on, suppressed in all the formulas)

- ∂ 2 ∂t 2 + ∂ 2 ∂r 2 * -V (r) φ(t, r) = 0 (1)
with the effective potential V (r) given by

V (r) = 1 - 2M r µ 2 + 6 r 2 - 16M r 3 . ( 2
)
The associated retarded Green function can be written as

G ret (t; r, r ′ ) = - +∞+ic -∞+ic dω 2π φ in ω (r < )φ up ω (r > ) W (ω) e -iωt (3)
where c > 0, r < = min(r, r ′ ), r > = max(r, r ′ ) and with W (ω) denoting the Wronskian of the functions φ in ω and φ up ω . These two functions are linearly independent solutions of the Regge-Wheeler equation

d 2 φ ω dr 2 * + ω 2 -V (r) φ ω = 0. ( 4
)
When Im(ω) > 0, φ in ω is uniquely defined by its ingoing behavior at the event horizon, i.e., for r * → -∞ φ in ω (r) ∼ exp[-iωr * ] and, at spatial infinity, i.e., for r * → +∞, it has an asymptotic behavior of the form

φ ω (r) ∼ ω p(ω) A (-) (ω)e -i[p(ω)r * +[Mµ 2 /p(ω)] ln(r/M)] +A (+) (ω)e +i[p(ω)r * +[Mµ 2 /p(ω)] ln(r/M)] . (5)
Similarly, φ up ω is uniquely defined by its outgoing behavior at spatial infinity, i.e., for r * → +∞,

φ up ω (r) ∼ ω/p(ω) exp{+i[p(ω)r * + [M µ 2 /p(ω)] ln(r/M )]
} and, at the horizon, i.e., for r * → -∞ it has an asymptotic behavior of the form

φ up ω (r) ∼ B (-) (ω)e -iωr * + B (+) (ω)e +iωr * . (6)
Here p(ω) = ω 2 -µ 2 denotes the "wave number" while A (-) (ω), A (+) (ω), B (-) (ω) and B (+) (ω) are complex amplitudes which, like the in-and up-modes, can be defined by analytic continuation in the full complex ω-plane (or, more precisely, in a well-chosen multisheeted Riemann surface). By evaluating the Wronskian W (ω) at r * → -∞ and r * → +∞, we obtain W (ω) = 2iωA (-) (ω) = 2iωB (+) (ω).

If the Wronskian W (ω) vanishes, the functions φ in ω and φ up ω are linearly dependent and propagate inward at the horizon and outward at spatial infinity, a behavior which defines the QNMs. The zeros of the Wronskian lying in the lower part of the complex ω-plane are the frequencies of the ℓ = 1 QNMs. They are symmetrically distributed with respect to the imaginary ω-axis. The contour of integration in Eq. ( 3) may be deformed in order to capture them [28]. By Cauchy's Theorem, we can extract from the retarded Green function (3) a residue series over the quasinormal frequencies ω n lying in the fourth quadrant of the complex ω-plane. We then obtain the contribution describing the BH ringing. It is given by

G QNM ret (t; r, r ′ ) = 2 Re n B n φωn (r) φωn (r ′ ) × e -iωnt+ip(ωn)r * +ip(ωn)r ′ * +i[Mµ 2 /p(ωn)] ln(rr ′ /M 2 ) ( 7
)
where

B n = 1 2p(ω) A (+) (ω) dA (-) (ω) dω ω=ωn (8)
denotes the excitation factor corresponding to the complex frequency ω n . In Eq. ( 7), the modes φωn (r) are defined by normalizing the modes φ in ωn (r) so that φωn (r) ∼ 1 as r → +∞. In the sum, n = 0 corresponds to the fundamental QNM (i.e., the least damped one) and n = 1, 2, . . . to the overtones.

Quasinormal retarded Green functions such as (7) do not provide physically relevant results at "early times" due to their exponentially divergent behavior as t decreases. It is necessary to determine, from physical considerations, the time beyond which they can be used and such a time is the starting time t start of the BH ringing. t start can be "easily" obtained for massless fields (see, e.g., Ref. [27]). Indeed, we first note that the QNMs are semiclassically associated with the peak of the effective potential located close to r * ≈ 0. Then, by assuming that the source at r ′ * and the observer at r * are far from the BH (i.e., that r * , r ′ * ≫ 2M ) we have t start ≈ r * + r ′ * (it is approximatively the time taken for the signal to travel from the source to the peak of the potential and then to reach the observer). For massive fields, the previous considerations must be slightly modified. We take into account the dispersive behavior of the QNMs and define t start from group velocities. From the dispersion relation p(ω) = ω 2 -µ 2 , we can show that the group velocity corresponding to the quasinormal frequency ω n is given by v g = Re[p(ω n )]/Re[ω n ]. Because the peak of the effective potential still remains located close to r * ≈ 0, we then obtain t start ≈ (r * + r ′ * )Re[ω n ]/Re[p(ω n )] (here, we neglect the contribution of [M µ 2 /p(ω n )] ln(rr ′ /M 2 )).

In Fig. 1, we display the effect of the graviton mass on ω 0 (see also Fig. 2 in Ref. [9]) and in Fig. 2, we exhibit the strong resonant behavior of B 0 occurring around the critical value α ≈ 0.90. The same kind of resonant behavior exists for the excitation factors B n with n = 0 but the resonance amplitude decreases rapidly as the overtone index n increases. The resonant behavior of the excitation factor B 0 occurring for masses in a range where the QNM is a longlived mode (see Figs. 1 and2) induces giant ringings which are, moreover, slowly or even very slowly decaying. In Fig. 3, we plot, for two values of the graviton mass, the BH "intrinsic" ringings constructed from the quasinormal retarded Green function (7) and we compare them to the ringing generated by the odd-parity (ℓ = 2, n = 0) QNM of the massless spin-2 field with quasinormal frequency 2M ω 20 ≈ 0.74734337 -0.17792463i and with excitation factor B 20 ≈ 0.12690 + 0.02032i. Similar results can be obtained for various locations of the source and the observer. Giant BH ringings also exist for n = 0 but with less impressive characteristics. Resonant behavior of the quasinormal excitation coefficients and associated "extrinsic" giant ringings.-In the previous section, we focussed on "intrinsic" ringings, i.e., on ringings directly constructed from the quasinormal retarded Green function and therefore depending only on the BH properties. Of course, with in mind astrophysical applications, it is now necessary to check that giant ringings also exist in the presence of a realistic perturbation or, in other words, that the convolution of the source of the perturbation with the retarded Green function does not modify, in a fundamental way, our results. This is a complex problem and, in this letter, we just discuss some of its elementary aspects.

Some years ago, dealing with the observability of quasinormal ringings, Andersson and Glampedakis associated to each QNM an effective amplitude h eff achievable after matched filtering [30,31]. For the massive QNMs considered here, it reads

h eff ∼ Re 2 -Re(ω n )/Im(ω n ) p(ω n )B n . (9)
We can use it in order to determine the effective amplitude of the ringings generated by the odd-parity (ℓ = 1, n = 0) QNM of massive gravity; we obtain |h eff | ≈ 54.74 for α = 0.89 and |h eff | ≈ 13.02 for α = 1.05. For the ringing generated by the odd-parity (ℓ = 2, n = 0) QNM of Einstein gravity we have |h eff | ≈ 0.40. This is in perfect agreement with our previous results and suggests that giant BH ringings are astrophysically relevant and observable. However, it should be noted that Andersson-Glampedakis formula must be taken with a pinch of salt.

As noted in Ref. [27], it seems helpful only if the quasinormal ringing is excited by localized initial data. So, it is necessary to consider a more general approach. We now describe the BH perturbation by an initial value problem with Gaussian initial data. More precisely, we consider that, at t = 0, the partial amplitude φ(t, r) governed by (1) satisfies

φ(t = 0, r) = φ 0 (r) ≡ φ 0 exp - a 2 (2M ) 2 (r * -β) 2 (10)
and ∂ t φ(t = 0, r) = 0. By Green's Theorem, we can show that the time evolution of φ(t, r) is described, for t > 0, by φ(t, r) = ∂ t G ret (t; r, r ′ )φ 0 (r ′ )dr ′ * . We can insert (3) into this expression and deform again the contour of integration on ω in order to capture the contributions of the QNMs. We then isolate the BH ringing generated by the initial data: the role of the BH perturbation and is given by

φ QNM (t, r) = 2 Re
C n = B n φ 0 (r ′ )φ in ωn (r ′ ) ω n /p(ω n )A (+) (ω n ) dr ′ * . (12)
The excitation coefficients C n , like the excitation factors B n , have a resonant behavior but it is now more attenuated. Moreover, the maximum amplitude of the resonance is slightly shifted but still occurs for masses in a range where the QNM is a long-lived mode. In Fig. 4, we exhibit the strong resonant behavior of C 0 for particular values of the parameters defining the initial data (10). It occurs around the critical value α ≈ 0.89 and is rather similar to the behavior of the corresponding excitation factor B 0 . It should be noted that we have checked that it depends very little on the parameters defining the initial data (10) (see Ref. [START_REF] Decanini | Work in preparation[END_REF] for a detailed study). Of course, for overtones, the resonance is more and more attenuated as the overtone index n increases so, the ringings generated by the fundamental QNM are certainly the most interesting.

In Fig. 5, we plot, for the two values of the graviton mass considered in Fig. 3, the BH "extrinsic" ringings defined by (11) and we compare them to the ringing generated by the odd-parity (ℓ = 2, n = 0) QNM of the massless spin-2 field. This last one is constructed by noting that, for the same initial data, the excitation coefficient of the QNM is given by C 20 /(2M ) ≈ 0.50761 -0.29210i. Similar results as those displayed in Fig. 5 can be obtained for various values of the parameters defining the initial data (10) and for various locations of the observer. Even if the role of the perturbation is taken into account, extraordinary BH ringings exist.

Conclusion.-In this letter, by considering the massive spin-2 field in Schwarzschild spacetime, we have pointed out a new effect in BH physics : the existence around particular values of the mass parameter of a strong resonant behavior for the excitation factors of the QNMs with, as a consequence, the existence of giant and slowlydecaying ringings. Such results are, in fact, a general feature of massive field theories in the Schwarzschild BH [START_REF] Decanini | Work in preparation[END_REF]. It would be interesting to study more realistic perturbations than the distortion described here by an initial value problem (e.g., the excitation of the BH by a particle falling radially or plunging), to consider alternative massive gravity theories and to extend our study to the Kerr BH. Finally, we would like to note that :

(i) The Schwarzschild BH interacting with a massive spin-2 field is in general unstable [8,9] (see, however, Ref. [10]). In the context of the theory considered here, the instability is due to the behavior of the propagating ℓ = 0 mode [9]. It is a "low-mass" instability which disappears for α above the threshold value αc ≈ 0.86. So, the giant ringings predicted here occurring near and above the critical value α ≈ 0.89 are physically relevant.

(ii) Even if the graviton is an ultralight particle, when it interacts with a supermassive BH, values of the coupling constant α leading to giant ringings can be easily reached. Indeed, supermassive BHs have their masses lying approximately between 10 6 M ⊙ and 2 × 10 10 M ⊙ ; so, if we assume that µ ≈ 1.35 × 10 -55 kg (it seems to be the superior limit of the graviton mass in the framework of the ordinary Fierz-Pauli theory [32]), we have α lying approximately between 10 -3 and 20. As a consequence, due to the enormous number of supermassive BHs in the Universe, the extraordinary BH ringings discussed here could be observed by the next generations of gravitational wave detectors and used to test the various massive gravity theories or their absence could allow us to impose strong constraints on the graviton mass and to support, in a new way, Einstein's general relativity.

Acknowledgments.-We wish to thank Andrei Belokogne for discussions and the "Collectivité Territoriale de Corse" for its support through the COMPA project.

FIG. 1 .FIG. 2 .

 12 FIG. 1. Complex frequency ω0 of the odd-parity (ℓ = 1, n = 0) QNM.

25 FIG. 3 .

 253 FIG.3. Extraordinary "intrinsic" ringings induced by massive gravity and comparison with the ringing generated in Einstein gravity. The results are obtained from(7) with r = 50M and r ′ = 10M .

nFIG. 4 . 15 FIG. 5 .

 4155 FIG.4. Resonant behavior, in massive gravity, of the excitation coefficient C0 of the odd-parity (ℓ = 1, n = 0) QNM. It is obtained from(12) by using(10) with φ0 = 1, a = 1 and β = 10M . The maximum of |C0|/(2M ) occurs for the critical value α ≈ 0.88808; we then have 2M ω0 ≈ 0.85277076 -0.04084908i and C0/(2M ) ≈ -4.02613 -1.93037i.