George Giakkoupis

Rachid Guerraoui

Arnaud Jégou

Anne-Marie Kermarrec

Nupur Mittal

Catch Me If You Can Privacy-Preserving Dissemination in Micro-Blogging

Online micro-blogging services and social networks, as exemplified by Twitter and Facebook, have emerged as an important means of disseminating information quickly and at large scale. A standard mechanism in micro-blogging that allows for interesting content to reach a wider audience is that of reposting (i.e., retweeting in Twitter, or sharing in Facebook) of content initially posted by another user. Motivated by recent events in which users were prosecuted merely for reposting anti-government information, we present Riposte, a randomized reposting scheme that provides privacy guarantees against such charges.

The idea is that if the user likes a post, Riposte will repost it only with some (carefully chosen) probability; and if the user does not like it, Riposte may still repost it with a slightly smaller probability. These probabilities are computed for each user as a function of the number of connections of the user in the network, and the extent to which the post has already reached those connections. The choice of these probabilities is based on results for branching processes, and ensures that interesting posts (liked by a large fraction of users) are likely to disseminate widely, whereas uninteresting posts (or spam) do not spread. Riposte is executed locally at the user, thus the user's opinion on the post is not communicated to the micro-blogging server.

We quantify Riposte's ability to protect users in terms of differential privacy and provide analytical bounds on the dissemination of posts. We also report on experimental results based on topologies of real networks, including Twitter, Facebook, Renren, Google+ and LiveJournal.

2 http://newsfeed.time.com/

INTRODUCTION

Micro-blogging platforms and online social networks are becoming a main source of news dissemination in the world. The open nature of such platforms provides unique opportunities for so-called web activists to denounce despotic activities and corrupted regimes [START_REF] Al-Ani | The Egyptian blogosphere: A counter-narrative of the revolution[END_REF][START_REF] Lotan | The revolutions were tweeted: Information flows during the 2011 Tunisian and Egyptian revolutions[END_REF]. 1 Not surprisingly, secret (and not so secret) police 1 http://www.huffingtonpost.com/2011/02/11/ egypt-facebook-revolution-wael-ghonim_n_822078. html services have been carefully following Internet traffic, and there has been an increasing number of arrests of such web activists. In many of these cases, people have been convicted merely for contributing to the dissemination of a post initially posted by someone else, a.k.a. reposting the post. 2,3 The motivation of this work is to devise a dissemination protocol for a micro-blogging or other social networks that would protect its users from such charges and hence conviction. Consider, for example, the setting where the content to disseminate is an article or a video from a media edited in some country X, and a link to that content was posted to the social network. We then seek to protect the privacy of an activist who wishes to contribute to the spread of that post by reposting it to her followers/friends in a country Y , e.g., retweet it on Tweeter, or share it on Facebook. The attacker here is any individual/group/external agency trying to identify the users involved in the spread of a specific post, by observing the dissemination, or even accessing the servers of the network.

We present Riposte, 4 a privacy-preserving reposting protocol. Riposte achieves privacy by randomizing the 1 user's repost actions: If a user likes a post, Riposte will repost it with some (carefully chosen) probability; otherwise, Riposte may still repost it, but with a smaller probability, equally carefully chosen. This decision is made locally, i.e., by Riposte's code at the user's browser, and is not communicated to the central service (Figure 1). This way, it is ensured that when an attacker observes a repost action, she cannot know with certainty whether it reflects the user's opinion, or whether Riposte enforced that action, thus providing plausible deniability to the user.

The main challenge in our approach stems from the trade-off between guaranteeing privacy on one hand, and ensuring that the spread of a post reflects the overall opinion of users, on the other. The latter means that posts liked by many users should spread a lot, whereas non-interesting posts (or spam) should not spread. The requirement for privacy suggests that the two probabilities Riposte uses to decide for the repost when the user likes/does not like the post should be close to each other. Whereas the requirement that the size of dissemination should reflect users' opinion suggests the opposite: the two probabilities cannot be "too" close to each other, otherwise the user's opinion is not taken into account.

Riposte computes these probabilities, at each user for each post, based on the number of connections of the user in the micro-blogging network, and the extend to which the post has already reached those connections. Our choice of these probabilities draws from the theory of branching processes [START_REF] Athreya | Branching processes[END_REF] and ensures the following properties.

• Privacy: By observing the reposts of a user, an attacker cannot tell (with sufficient confidence) if that user likes the post or not.

• Dissemination: Posts liked by a large fraction of users are likely to disseminate to a large fraction of the network, whereas posts that only few people like (or spam posts) do not spread.

Riposte shall be seen as a novel dissemination scheme that seeks to protect its users with respect to the privacy of their repost actions. We should stress that Riposte diverges from the standard repost practice: A user may not repost all the content she would like to, and may repost content she does not like. This change in the dissemination semantics is the price to pay for users to see their privacy preserved. Also, we believe that the social nature of such platforms can be leveraged by users themselves. They can use their real relationship with followers or friends to implement a human filter on the reposting actions: Alice might realize that the reposting of X does not resemble Bob's habits and therefore be the consequence of running Riposte. 5 The recent success of social applications such as Snapchat or Whisper shows an increased concern of users for privacy and therefore their willingness to change their habits and adopt new privacy preserving schemes.

This paper makes the following contributions:

1. We present a simple yet powerful privacy-preserving reposting protocol, called Riposte.

2. We provide a theoretical analysis of Riposte. We express the privacy properties of Riposte in terms of ε-differential privacy [START_REF] Dwork | Differential privacy: A survey of results[END_REF]. For the dissemination, we provide analytical bounds on the spread of posts (under certain modeling assumptions).

3. We complement the analysis by extensive experimental results on real micro-blogging and social networks topologies, from Twitter, Facebook, Live-Journal, Google+ and Renren.

The rest of the paper is organized as follows. In Section 2 we describe Riposte and discuss its properties. In Section 3 we analyze Riposte's privacy guarantees. Section 4 provides an analysis of the dissemination of posts. In Section 5 we describe our experimental setup followed by the experimental results in Section 6. Section 7 discusses some implementation details. Section 8 gives an overview of related work, and Section 9 concludes the paper.

THE RIPOSTE PROTOCOL

In this section we describe Riposte and discuss its properties.

Protocol Description

Riposte is a randomized dissemination scheme with a repost mechanism.We assume that each user in this system has a set of followers (or friends), and when a user posts or reposts some content, this content is sent to all its followers.

Riposte decides for each post the user receives, whether to repost it or not. This decision is local to the user: it is made by Riposte's code at the user's machine. Riposte solicits the opinion of the user about the post, i.e., if the user likes it or not, and then decides whether or not to repost it. If it decides to repost, then a repost request is communicated to the system server. We stress that Riposte does not reveal the user's opinion on the post, to the server or to any other user.

Riposte does not repost every post that the user likes, and it may repost content that the user does not like. If the user likes a post then it is reposted with some carefully computed probability; and if the user does not like it, it is reposted with another carefully chosen probability, which is slightly smaller. These two probabilities for an attacker and second can never lead to a clear evidence.

are computed based on (1) the number of the user's followers that have not received the post yet; and (2) two global parameters of Riposte, λ and δ, called spreading and blocking factor respectively . These parameters are fixed and are the same for all users-they are not chosen by each user. The values of these parameters impact the dissemination of posts, and determine also the privacy guarantees the protocol provides, as explained in detail later. Both parameters are real numbers with 0 < δ < 1 and λ > 1.

Riposte decides whether or not to repost as follows: Consider a user u who receives a new post, and suppose that s > 0 of its followers have not yet received the post at the time. If u likes the post, it is reposted with probability

r like (s) := λ/s, if s ≥ λ + δ, 1 -δ(s-δ)
λs , if 0 < s < λ + δ; while if u does not like the post, it is reposted with probability r dis (s) := δ/s. These random decisions are independent for each user and for each post.

Remark 1. The second formula for r like (s), for the case of small s, will be justified when we analyse the privacy properties of the protocol, in Section 3. Until then we can assume the following simpler definition for all s, r like (s) := min{λ/s, 1}.

We assume that Riposte knows the number s of followers that have not yet received a given post. This information is available and can be easily obtained in many existing platforms, including Twitter. Nevertheless, at the end of this section we provide a simple variant of Riposte that uses the total number of followers in place of s; we show that this variant has very similar properties as the Riposte protocol presented above.

We give now an informal overview of Riposte's properties, and provide some intuitive explanation. The formal analysis will be provided in the next sections. First we discuss privacy properties, and then the guarantees provided with respect to the dissemination of posts.

Privacy Overview

With respect to privacy, our goal is that an attacker, who observes all the reposts of the users, cannot tell whether or not a particular user indeed likes a given post-unless the post originated at that user. 6More specifically, observing that the post was reposted (or not) from the user, may change only slightly the prior knowledge that the attacker has about the user's opinion on the post (e.g., by observing previous posts by that user). In other words, if before having observed reposting actions, the attacker believed that with probability q the user likes the post, then learning whether or not the post was reposted from the user may change this probability to q, such that this new probability q will be close to q.

How close these two probabilities are in Riposte depends on the choice of parameters δ and λ. Since r like (s) and r dis (s) are respectively (at most) λ/s and δ/s, it is intuitive that the closer the values of δ and λ, the less information the attacker gains about the user's opinion by observing his reposts, thus the better the privacy guarantee. Consider, for example, the extreme case in which δ = 0 and λ = n (n being the size of the network). I.e., every post that the user likes is reposted, and no other posts are reposted, as, e.g., in Twitter. In this case, if the post is reposted (resp. not reposted), an attacker can conclude with certainty that the user likes it (resp. does not like it). On the other hand, in the opposite extreme case in which δ = λ = 1, reposting reveals no information at all. However, choosing δ and λ to be equal is not very useful, as the dissemination is then independent of the user's opinion.

In Section 3, we show that our protocol ensures ǫdifferential privacy for ǫ = ln(λ/δ). Thus, the closer the ratio λ/δ to one, the better the achieved privacy. We will see that if q is the probability for a given user u to like the post, as perceived by the attacker, and q is the same probability after observing that the post was reposted from u then q = q q + (1 -q)δ/λ . E.g., for typical parameter values, δ = 3/4 and λ = 3, we have that if q = 0.01 then q ≈ 0.04; if q = 0.1 then q ≈ 0.3; and if q = 0.9 then q ≈ 0.97.

Dissemination Overview

With respect to dissemination, our goal is that the fraction of users reached by a post should reflect the user's overall opinion on the post. In particular, we want that interesting posts, i.e., posts many users like, to typically spread to a lot of users, while not interesting posts should not reach many users. The main difficulty in this goal lies in the fact that the users' opinions on a post are not known in advance, and thus we cannot tell beforehand if a post is interesting or not. Indeed Riposte does not rely on any prior knowledge of how interesting the post may be. Furthermore, we are constrained by the requirement that the users' opinions must remain private.

The idea behind Riposte's dissemination scheme is simple, and draws from the theory of branching processes [START_REF] Athreya | Branching processes[END_REF]. A branching process is a random process modeling a population, which starts with one or more individuals, and at each step a single individual produces zero of more offsprings and then dies. In the most basic model, the number of offsprings of an individual follows a fixed probability distribution that does not vary between individuals. Let µ be the expected number of offsprings of an individual. It is a well-known fact then that if µ < 1 the population dies quickly, while if µ > 1 it survives forever with some positive probability.

To see the connection of Riposte to branching processes, let us compute the expected number of new users that learn the post from a given user u who has received the post. Let s > 0 be the number of u's follower who have not already received the post from some other user before u'action is decided.

If u likes the post, then Riposte will repost it with probability r like (s), and thus, with this probability, s new users will learn the post. It follows that r like (s) • s users will learn it in expectation. Further, if s ≥ λ + δ, then r like (s) = λ/s and thus r like (s) • s = λ > 1 new users receive the post from u in expectation.

By a similar reasoning, if the user does not like the post, then Riposte forwards it to at most δ < 1 other users in expectation. Depending now on the popularity of the post, that is, the fraction of users who like it, 7 we have more than 1 new users in expectation that learn the post from the average user if the post is sufficiently popular, or fewer than 1 if the post is less popular. An analysis then, using standard results from branching processes, shows that if the expected number of users to receive the post from the average user is even slightly larger than 1 then the post is likely to reach a significant fraction of the network; while if this expectation is even slightly smaller than 1 then the post is unlikely to spread.

More precisely, in Section 4 we prove the following bounds on dissemination, under some independence assumption on the opinion of different users. For any parameters 0 < δ < 1 < λ, there is a popularity threshold

p * = 1 -δ λ -δ ,
such that:

(a) A post with popularity smaller than p * (unpopular post), spreads to an expected number of users that is at most a constant factor larger than the number of followers of the user who sent the original post. This result holds for any network topology.

(b) A post with popularity greater than p * (popular post), spreads to at least some constant fraction of the network, with at least a constant probability, provided that the number of followers of the user who sent the original post is not much smaller than the average. This result is shown for a specific random graph model for social networks.

DB-RISPOSTE: Counting All Followers

Riposte needs to know the number of the user's followers who have not yet received the post. In most platforms, this information is readily available, as the default setting is that a user can access the list of posts each of its followers has received. However, followers may have the option to hide that information.

DB-Riposte (Degree-Based Riposte) is a simple variant that accounts for these concerns. This protocol is identical to Riposte, except that in the definition of probabilities r like and r dis , we replace the number of followers s that have not already received the post, by the total number d of followers.

DB-Riposte provides the same privacy guarantees as Riposte, and similar dissemination guarantees except that the spread achieved for popular posts may be smaller by some small factor.

We will also provide an analysis and experimental evaluation of this variant of Riposte.

ANALYSIS OF PRIVACY

In this section we show that Riposte is ε-differentially private.

Differential Privacy

We start by recalling the definition of an ε-differentially private algorithm. Suppose we have a randomized algorithm A that takes as input a collection of m values, x 1 , . . . , x m from some domain D in , and returns a value from some domain D out . We denote by A(x 1 , . . . , x m ) the output value of the algorithm. Since the algorithm is randomized, it may give different outputs for the same input. Thus, for a fixed input x 1 , . . . , x m , the output A(x 1 , . . . , x m ) is a random variable, with some distribution over D out . Suppose now that the input to A is not known to us (is private), and by observing just the output of A we want to find out the value of some of the inputs. More generally, we may have some information about the input, i.e., a distribution over the possible combinations of input values, and we want, by observing A's output, to improve this information, i.e., obtain a distribution that is closer to the true input values. We can quantify the extend to which this is possible in terms of ε-differential privacy. Algorithm A is ε-differentially private if changing exactly one of it inputs x 1 , . . . , x m changes the distribution of the output only by at most an e ε factor.

Definition 1 (ε-differential privacy).

A randomized algorithm A with inputs x 1 , . . . , x m from some finite domain D in and output A(x 1 , . . . , x m ) on some domain D out , is ε-differentially private if for any two set of inputs x 1 , . . . , x m and x ′ 1 , . . . , x ′ m that differ in exactly one value, and for any subset of outputs S ⊆ D out ,

Pr A(x 1 , . . . , x m ) ∈ S ≤ e ε • Pr A(x ′ 1 , . . . x ′ m ) ∈ S .
In our setting, algorithm A is the reposting protocol, which takes a single binary input: the opinion of the user, and has a binary output: repost or not-repost.

Theorem 1. Both Riposte and DB-Riposte are εdifferentially private for ε = ln(λ/δ).

Proof. Below we use k to denote the number of followers of the user considered if DB-Riposte is used, or the number of followers that have not received the post yet if Riposte is used.

We must show that (1) the probability of reposting when the user likes the post is no larger than e ε = λ/δ times the probability of reposting when the user does not like the post, i.e.,

r like (k) ≤ (λ/δ) • r dis (k); (1)
and ( 2) the probability of not reposting when the user does not like the post is no larger than λ/δ times the probability of not reposting when the user likes the post,

1 -r dis (k) ≤ (λ/δ) • (1 -r like (k)). (2)
Ineq.

(1) holds because:

r like (k) = δ/k for all k > 0, r dis (k) = λ/k if k ≥ λ + δ, and r dis (k) < λ/k if 0 < k < λ + δ. For Ineq.
(2), we have for 0 < k < λ + δ,

(λ/δ) • (1 -r like (k)) = (λ/δ) • δ(k -δ) λk = 1 -r dis (k);
and for k ≥ λ + δ, we must show

(λ/δ)(1 -λ/k) ≥ 1 -δ/k ⇔ λ(1 -λ/k) ≥ δ(1 -δ/k) ⇔ λ -δ ≥ (λ 2 -δ 2 )/k ⇔ 1 ≥ (λ + δ)/k ⇔ k ≥ λ + δ,
which holds.

We explain now what this property implies for the information an attacker can gain for the opinion of a user, by learning whether or not it reposted a post.

Suppose the attacker has some prior knowledge on the opinion of the user on the post, i.e., the attacker believes that with some probability q the user likes the post. We argue that the new probability q with which the attacker believes that the user likes the post, after it has learned whether or not the user has reposted, is

q q + (1 -q)(λ/δ) ≤ q ≤ q q + (1 -q)(δ/λ) . (3)
Let L be the event that the user likes the post, and R the binary random variable that is 1 if the user reposts 3) that provides upper and lower bounds on q in terms of q. Probability q diverges more from q as λ increases or δ decreases. and 0 if it does not repost. Then the probabilities q and q can be expressed as q = Pr(L) and q = Pr(L | R). Suppose that the user has at least one follower who does not know the post yet and thus the probability of repost is not zero. From Bayes' Rule,

Pr(L | R) = Pr(R | L) • Pr(L) Pr(R | L) Pr(L) + Pr(R | ¬L) Pr(¬L) = Pr(L) Pr(L) + Pr(R|¬L) Pr(R|L) • Pr(¬L) . ( 4
)
Also from Theorem 1, we have δ/λ ≤ Pr(R|¬L) Pr(R|L) ≤ λ/δ. Applying this to the expression for Pr(L | R) above proves Ineq. (3).

Correlated Posts

We have seen that the observance of an individual post reposted by a user only marginally changes the attacker's confidence about the user's opinion on that post. However, if a user receives several correlated posts, e.g., posts supporting a particular anti-government view, then the reposts by the user can be used to compute an accurate estimate of whether the user supports the view. The larger the set of correlated posts, the higher the accuracy of the estimation. In this setting, we argue that the attacker cannot identify a large set of users such that with significant probability all the users in the set support the view.

Suppose there is a set of t posts on some anti-government view. Considering the attacker's point of view, we call a user guilty if she likes a post and innocent otherwise. The goal for the attacker is to identify the largest subset L of users that like at least one of those t posts, such that the probability that all users in L are guilty is at least 1/2. This goal makes sense if, for example, the government wants to charge the largest possible number of users, without charging innocent users. For simplicity we will assume that each user likes either all the t posts or none. We also assume that the expected fraction p of users that like the posts is known, but no additional information is available in advance about users. So, we can assume that each user likes the posts with probability p independently of the other users. We are interested in the size ℓ = |L| of L. For simplicity, we assume DB-Riposte is used, but similar reasoning applies also to Riposte.

We observe the dissemination of the t anti-government posts. For a user u with degree d, who has received i of those posts and has reposted r, the probability of disliking the posts can be computed similar to Equation 4, which gives the probability for liking, and is given by:

θ(i, r, d) := 1 -p (1 -p) + Pr(B(i,δ/d)=r) Pr(B(i,λ/d)=r) • p
, where B(i, q) is the binomial distribution counting the number of successes among i independent trials with success probability q. Substituting the definition for the binomial distribution yields:

θ(i, r, d) = 1 -p (1 -p) + λ δ r d-λ d-δ i-r • p .
It is easy to verify that the following strategy for choosing the elements of L maximizes the size of L. Let θ j be the value for the j-the user in a list of users with increasing values of θ. We choose L to be the set containing the first ℓ users in the list, for ℓ the largest index such that

1 - j≤ℓ (1 -θ j ) < 1/2.
The quantity on the left is the probability that not all users like the posts, and is approximately j≤ℓ θ j . We evaluate ℓ numerically in the following setting. We assume that the attacker fixes in advance a set of m users, then each of these users is given all the t posts, and the attacker must choose a subset L of these m users after it observes their reposts.

Table 1 shows the average (over 10000 runs) of the maximum number ℓ of users that can be identified as guilty. We chose the fraction p of guilty users to be 1%, 10% and 30%, the number of users to be m = 100, 1000, 10000, 100000, and the number of posts to be t = 5, 10, 20. We assume δ = 0.75, λ = 3 and d = 40. For example, in a group of 1000 users, 100 of which are guilty in expectation (p = 10%), and for a set of 10 correlated posts, an attacker can only identify a set of at most 3 guilty users on average.

As expected, the number of users that can be convicted increases with the number of correlated posts, as the more a user expresses her opinion about a topic, the easier it becomes to estimate her opinion and hence convict her. Overall, the number of users that can be convicted is very small with respect to the number of guilty users.

ANALYSIS OF DISSEMINATION

In this section we provide analytical bounds on the dissemination of posts using Riposte.

Preliminaries

Let G denote a directed network of users. A connection from user u to user v denotes that v follows u. Let n denote the total number of users.

For the analysis we make the assumption that all users are equally likely to like a given post, independently of their position in the network and the opinion of other users. Precisely, we assume the following probabilistic uniform opinion model.

Definition 2 (Uniform Opinion Model

). In this model, each post is associated with some probability p, called the popularity of the post (different posts may have different popularity). The probability that any given user u likes a post is equal to the post's popularity p, and is independent of the set of users v = u that like the post.

Suppose that user u receives a post of popularity p. Let s be the number of u's followers that have not received the post yet, and suppose s > 0. If we assume the uniform opinion model, then u has probability p of liking the post, and thus the probability of reposting for Riposte is

p • r like (s) + (1 -p) • r dis (s).
If s ≥ λ + δ then r like (s) = λ/s and the probability above is pλ + (1 -p)δ s .

Since s followers of u do not know the post yet, the expected number of users that will learn the post from u is

pλ + (1 -p)δ s • s = pλ + (1 -p)δ.
If this quantity is greater than 1, we say that the post is popular ; if it is smaller than 1, we say it is unpopular. The formal definition is as follows.

Definition 3 (Popular/Unpopular posts). For given λ and δ, we define the popularity threshold

p * := 1 -δ λ -δ ,
and we call a post popular if its popularity is p > p * , and unpopular if p < p * . 8We define now a simple random network model of a typical micro-blogging network, in which there is a large variation in the number of followers between users, while there is little variation in the number of followees (i.e., the users that one user follows). The model takes as a parameter a distribution φ on the number of followers.

Definition 4 (G φ network model). Let φ be a probability distribution on the integers 0, . . . , n -1. Then G φ is an n-user random network constructed as follows. Independently for each user u, we first choose the number d of followers that u will have, according to distribution φ; and then we choose d uniformly random users among all the other users (excluding u) to be u's followers.

Finally, we note that the probability functions r like (k) and r dis (k) have been defined only for k ≥ 1. To simplify notation, we define also r like (0) = r dis (0) = 0.

Bounds on Dissemination

We begin with the simple observation that Riposte achieves at least as large dissemination as DB-Riposte, in the following sense.

Observation 1. For a network G, consider the spread of a post when Riposte is used, and the spread of the same post (originated at the same user) if DB-Riposte is used instead. We assume that the opinion of each user is the same in both cases. Let N and N db denote the number of users that receive the post in each case. Then for any k, the probability that N ≥ k is at least equal to the probability that N db ≥ k.

The reason is that for a user u, the number of followers s that have not yet received the post is smaller or equal to the total number d of u's followers, and from this it follows that r like (s) ≥ r like (d) and r dis (s) ≥ r dis (s), if s > 0. The complete proof can be found in the appendix.

Remark 2. From Observation 1 it follows that any upper bound on the dissemination that holds for Riposte, applies also to DB-Riposte; and any lower bound for DB-Riposte applies also to Riposte.

Next we establish an upper bound on the spread of unpopular posts, and a lower bound on the spread of popular posts.

Unpopular posts. We present now an upper bound on the expected dissemination of unpopular posts. We show that the expected number of users who receive a given unpopular post is by at most a constant factor larger that the number of followers of the user who started the post. The constant factor depends on the popularity of the post and parameters δ and λ. This bound holds for any network G, assuming the uniform opinion model. Recall that a post is unpopular if its popularity is smaller than p * = (1 -δ)/(λ -δ).

Theorem 2 (Upper bound for unpopular posts). For any G, and under the uniform opinion model, both Riposte and DB-Riposte guarantee that a post with popularity p < p * started by a user with d followers is received by an expected total number of at most d/β users, where β = (p * -p)(λ -δ).

Observe that as p approaches the popularity threshold p * , factor β decreases, and thus the bound on the expected spread increases. Further, substituting the definition of p * gives β = 1-δ -p(λ-δ), which implies that increasing either λ or δ increases the expected spread. All these observations are consistent with the intuition.

From Remark 2, it follows that it suffices to prove the upper bound of Theorem 2 just for Riposte, as then the same bound holds for DB-Riposte. The proof for Riposte is a bit technical and can be found in the appendix. Instead, we provide below a simpler proof that holds only for DB-Riposte.

Proof of Theorem 2 for DB-Riposte. In DB-Riposte, the set of all users that receive the post does not depend on the order in which reposts take place. Thus we can assume that dissemination proceeds in rounds in a breadth-first manner, as follows: In round 0, the source user posts the content; then in each round t > 0, every user that learned the post in the previous round t -1, either reposts or decides it will not repost. (We say a user learns a post the first time it receives it.) Let Z t , for t ≥ 0, denote the number of users that learn the post in round t; so Z 0 = d. The total number T of users that learn the post (in any round) is then

T = t≥0 Z t .
We bound now the expectation of each Z t . The probability for a user u with k followers to repost when it receives the post, is

p • r like (k) + (1 -p) • r dis (k) ≤ pλ + (1 -p)δ k = 1 -β k ,
where the last equation is obtained using the equations β = (p * -p)(λ -δ) and p * = (1 -δ)/(λ -δ). Thus the expected number of users that receive the post from u is at most

1 -β k • k = 1 -β.
Some of these users may have already received the post from a different user, in the same or a previous round, thus 1 -β is just an upper bound on the expected number of users that learn the post from u. Given now the number of users that learned the post in round t -1, it follows from the linearity of expectation that the expected number of users that learned the post in round t is

E[Z t | Z t-1 ] ≤ Z t-1 • (1 -β).
Taking the unconditional expectation on both sides yields

E[Z t ] ≤ E[Z t-1 ] • (1 -β).
Applying this inequality iteratively and using that

E[Z 0 ] = Z 0 = d gives E[Z t ] ≤ (1 -β) t d.
Since T = t≥0 Z t , it follows from the linearity of expectation and the above bound that

E[T ] = t≥0 E[Z t ] ≤ t≥0 (1 -β) t d = d/β.
This completes the proof of Theorem 2 for DB-Riposte.

Popular posts. Next we study the dissemination of popular posts on the G φ network model, for an arbitrary distribution φ for the followers (under a mild constraint on the min number of followers). We establish a lower bound on the probability of a popular post to be received by a constant fraction of users. The probability and the size of the fraction grow respectively with the number d of followers of the source, and the popularity of the post. In particular, the probability converges to 1 for d sufficiently large relative to the average number of followers.

Theorem 3 (Lower bound for popular posts). Consider the network model G φ , for a distribution φ such that the minimum number of followers of any user is at least λ + δ, and the average number is µ. Let ǫ, ǫ ′ > 0 be arbitrary small constants. Suppose that a post with popularity p ≥ p * + ǫ is posted by a random user, and this user has d followers. Under the uniform opinion model, both Riposte and DB-Riposte guarantee that with probability at least 1 -e -Ω(d/µ) the total number of users that receive the post is at least

(1 -ǫ ′ ) • βn β + 1 , where β = (p -p * )(λ -δ).
Note that the same constant β = |p -p * | • (λ -δ) appears in both Theorems 2 and 3. Unlike the d/β bound of Theorem 2, the threshold spread of (1 -ǫ ′ ) • βn β+1 predicted by Theorem 2 is independent of d, and depends only on λ and δ: the larger their value the larger the spread. The independence from d is intuitively justified, because as soon as the the post reaches a "critical mass" of users it will almost surely spread to a constant fraction of the network. However, d determines the probability with which such a critical mass will be reached. For d close to the average number of followers, this probability is at least some constant.

The proof of Theorem 3 uses a coupling between the dissemination process and an appropriate branching process, to show that the probability of the event we are interested in, that at least a certain fraction of users receive the post, is lower-bounded by the survival probability of the branching process. Then we bound this survival probability using a basic result for branching processes. The proof can be found in the appendix.

EXPERIMENTAL SETUP

This section presents the experimental setup of Riposte on real topologies from micro-blogging platforms and social networks.

Data-sets

We use data-sets from several online services as the underlying topology for our experiments.

Twitter is arguably the most popular micro-blogging platform. We use a snapshot of the complete Twitter network from 2009 containing 42 million users and 1.5 billion edges [START_REF] Kwak | What is Twitter, a social network or a news media?[END_REF].

Facebook is the largest online social network, with more than a billion active users. We use a sample of Facebook from 2009 containing 3 million users and 28 million links [START_REF] Wilson | User interactions in social networks and their implications[END_REF].

Renren is an online social network similar to Facebook, that is is popular in China. We use a sample of Renren from 2013 containing 1 million users and 57 million links [START_REF] Ding | Crowd crawling: towards collaborative data collection for large-scale online social networks[END_REF].

LiveJournal is a combination of a blogging service and a social network. We use a sample of LiveJournal containing 4.8 million users and 69 million edges. 9 Google+ is another popular social network. We use a sample containing 107 thousands users and 14 millions edges. 10 A summary of these topologies is given in Table 2

User Opinion Model

While data on the topology of online services are available, access to the history of users about the posts they received or liked is severely restricted. Hence, we rely on synthetic models to generate the users opinions. We consider two user opinion models: the uniform model and the distance-threshold model.

Uniform model. In this model, every user has the same probability to like a given post. Precisely, each post is assigned a popularity in [0, 1], which is the probability with which any user will like this post. Under this model, the opinion of a user is independent of her position in the network. This model is the same as the one of Definition 2 on which our analysis of Riposte in Section 4 is based.

Distance-threshold model. This model accounts for the fact that in social networks, users are more likely to be interested in the same posts when they are closer to each other in the network. In the distance-threshold opinion model, the opinion of a user about a post depends on her shortest-path distance from the source of the post. If this distance is below some threshold h, which is a parameter of the model, the user likes the post with probability 1, whereas if the distance is larger than h then the user dislikes it with probability 1.

Evaluation metrics

We evaluate the dissemination properties of Riposte along the following metrics:

Fraction of users that receiving the post. This metric is the number of users who receive a post over the total number of users.

Recall.

Dissemination model

To evaluate the performances of Riposte, we simulate the dissemination of posts over several networks we selected and with the two user opinion models. For each simulation we select the source of the post at random among the users having at least 30 followers (30 is the average number of followers for different data-sets). To start, we add all the followers of the source to a receivers list and then we iterate over each of the user in this list. For each user, we decide if she likes the post according the opinion model, and then if she forwards the post to her followers according to the spreading algorithm. If the post is forwarded to the user's followers, all the followers that receive the post for the first time are added to the receivers list.

In addition to Riposte and DB-Riposte, we simulate the spreading with a third dissemination algorithm that we call Standard. Standard is a non-privacy preserving dissemination protocol that forwards with probability 1 when the user likes the post, and with probability 0 when the user dislikes the post (this is equivalent to DB-Riposte with δ = 0 and λ = n where n is the number of nodes in the network).

EXPERIMENTAL RESULTS

Our experimental evaluation shows that the dissemination patterns generated by Riposte match the theoretical analysis.

Fraction of users receiving the post

Figure 5 displays the fraction of users who received the disseminated posts with Riposte over different datasets. We see that Riposte behaves consistently with different data-sets. The posts with a popularity smaller than 0.2 never spread, while for the more popular posts the spreading increases with the popularity.

For space reasons, we consider only three data-sets. Given that Twitter, Facebook and Goggle+ have similar results, we keep only Twitter which is the largest one. Thus in the following we will only show the results for Twitter, LiveJournal and Renren.

Figure 3 displays the average fraction of users who received the posts in the considered data-sets under the uniform opinion model, for various popularity values. The straight line represents an ideal system, e.g., a post liked by 40% of the users reach nearly 40% users on an average.

We observe that the Standard algorithm is far from achieving this objective and clearly over-disseminates the posts. In particular, unpopular content is widely disseminated, for instance posts with a popularity of 0.1 reaches over 50% of the network in Twitter and over 80% in Renren. On the contrary, Riposte achieves a The popularity threshold p * , introduced in Definition 3, is displayed in Figure 3 by a vertical line. The experiments validate that, for both Riposte and DB-Riposte, posts with popularity below threshold spread to a very small fraction of users, whereas when popularity grows above the threshold, the posts are disseminated to a large fraction of the users.

Figure 4 presents the same experiments with the distancethreshold model. As expected, we observe similar results as for uniform model. Not only Riposte ensures privacy, but the spreading achieved by the protocol matches the expected spreading and clearly outperforms Standard in this respect.

Dissemination of unpopular posts

According to Theorem 2, the spreading of unpopular posts is bounded by: |users who like the post| source degree

≤ 1 β = 1 (p * -p) × (λ -δ)
Figure 6 depicts the spreading of unpopular posts achieved by Riposte and DB-Riposte when compared to this theoretical bound. We observe that the experiments match the analytical results: with both Riposte and DB-Riposte the spreading of unpopular posts is indeed lower than the theoretical bound.

Precision and recall of the spreading

We now do a qualitative evaluation of the spreading by comparing the sets of users receiving the posts and the sets of users interested in these posts.

Due to lack of space, we do not provide the results for all data-sets but only for LiveJournal in Figure 7. For this part of the evaluation we use only the distancethreshold model as the uniform model is irrelevant in this configuration. 11In Figure 7a we observe that the recall for the Standard protocol is always 1. This is because in the distance-threshold model for every user who likes the post there exists a path in the network between her and the source of the post containing only users who like the post. Thus, since in Standard the users always forward posts they like, all the users liking the post end up receiving it in the distance-threshold model. In contrast, since with Riposte, a posts is never reposted with probability 1, the recall is always less than 1. However Riposte still spreads the interesting posts to a very large fraction of the interested users (up to 80%) while DB-Riposte achieves at best a recall of 35%. In Figure 7b, we can see that Riposte achieves a better precision than Standard. It may seem surprising since because of the randomization performed by Riposte, many users could repost the posts they do not like which could strongly reduce the precision. However, we can see that this does not happen as the precision of Riposte is significantly larger than the one of Standard, especially for small values of h. We can draw the same conclusion from Figure 7c as it shows that Riposte spams spread much less than Standard.

Effect of λ and δ on spreading

In the experiments shown so far, we set the values of λ and δ to values that match a level of privacy that we believe is reasonable, with respect to the desired dissemination. Now we evaluate the effect of varying values of λ and δ on the dissemination. Results are shown only for LiveJournal for space reasons. To isolate the impact of each parameter, we first vary the value of δ with λ = 3 and then vary the value of λ with δ set to 0.75. Results are reported in Figure 8a and Figure 8b respectively. Figure 8a shows that varying the value of δ has a strong impact on the popularity threshold after which the posts start to spread, but has little effect on the spread of posts with a popularity greater than 0.4. Figure 8b, where the value of λ varies between 2 and 4, shows that λ strongly impacts both the popularity threshold after which the posts starts to spread and the number of users receiving the post.

IMPLEMENTATION DETAILS

In this section we discuss Riposte's underlying implementation issues and its interaction with the social network or the micro-blogging platform.

As we have mentioned earlier, Riposte does not require any involvement from the server: it fits within the user's web browser. In this case, the randomization of Riposte is done locally on the user's machine, and the only information accessible by the server is the output of Riposte, i.e., the randomized decision. Thus the users' privacy is protected not only against an attacker, but also against the service provider.

We should stress that Riposte diverges from the standard repost practice: A user may not repost all the content he would like to, and may repost content he does not like. The goal of our protocol, however, is to complement rather than replace the standard mechanism where each user reposts what he likes. Although not addressed in this paper, it is possible to have a hybrid version of Riposte where a user can choose to "force" a repost action on a specific post, if the user is not concerned about revealing its opinion on that post. However, we cannot allow a user to force that a post is not reposted, otherwise Riposte's privacy guarantees no longer hold. Indeed, in that situation a user could be convicted simply because she did not force the nonreposting of a post, whatever her true opinion is. The information of whether a repost was done by Riposte or forced by the user can be communicated to the other users. So, for example, a user may choose to ignore all reposts that were not forced, in which case the hybrid protocol behaves like a standard micro-blogging service.

However, for Riposte to achieve the desired dissemination, a user should always express her opinion for the posts she receives. In order to achieve this, we propose to display one post at a time to the user and let her take a decision to either repost it or to move to another post, which implicitly implies her decision not to repost it. Another solution to deal with this is to impose a time-out, after which the post cannot be disseminated using Riposte.

RELATED WORK

Dwyer et al. [START_REF] Dwyer | Trust and privacy concern within social networking sites: A comparison of Facebook and MySpace[END_REF] highlighted the weak privacy safeguards in micro-blogging and social-networking services. Not surprisingly, a lot of work has been devoted to the problem, including studies on how micro-blogging and social network services fail to give complete privacy guarantees to the user [START_REF] Zheleva | Privacy in social networks: A survey[END_REF], characterization of privacy threats to facilitate their intensive study [START_REF] Krishnamurthy | Characterizing privacy in online social networks[END_REF], as well as solutions dealing with individual threats [START_REF] Korolova | Link privacy in social networks[END_REF][START_REF] Tootoonchian | Lockr: Better privacy for social networks[END_REF][START_REF] Zhou | Preserving privacy in social networks against neighborhood attacks[END_REF].

Anonymization (i.e., replacing names with meaningless unique identifiers [START_REF] Backstrom | Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography[END_REF]) is one of the most studied privacy-preserving mechanisms for users in social networks, and for releasing data from these networks for analysis and research. Anonymization does not always suffice as the original data-sets can sometimes be reconstructed [START_REF] Backstrom | Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography[END_REF][START_REF] Hay | Resisting structural re-identification in anonymized social networks[END_REF][START_REF] Narayanan | De-anonymizing social networks[END_REF]. K-anonymity, introduced in [START_REF] Ullmann | An algorithm for subgraph isomorphism[END_REF], protects tabular micro-data against linking attacks. The concept has been extended for social network data-sets in [START_REF] Zhou | The k-anonymity and ℓ-diversity approaches for privacy preservation in social networks against neighborhood attacks[END_REF] . Clearly, there is an information loss that comes with anonymization in social-networks and there is a trade-off between the increased anonymity and the loss of information as a result of anonymization [START_REF] Hay | Resisting structural re-identification in anonymized social networks[END_REF].

The authors of [START_REF] Alves | Anonylikes: Anonymous quantitative feedback on social networks[END_REF] have recently proposed a system, anonyLikes, that keeps the actual like count of a post without revealing the names of the users who like it. The adoption of pseudonyms has also been a common practice by activists to hide their identity while contributing to the spread of sensitive information [START_REF] Wulf | on the ground' in Sidi Bouzid: Investigating social media use during the tunisian revolution[END_REF]. This promises privacy to the user's original identity at the cost of the trust that their followers would put in them should they knew the original identity of that user. A similar issue concerns the hiding of IP addresses [START_REF] Olaore | Politexting: Using mobile technology to connect the unconnected and expanding the scope of political communication[END_REF].

Riposte preserves the identity of the users while providing privacy guarantees that can be quantified in terms of differential privacy guarantees. Although there has been a considerable work to bringing the concept of differential-privacy to social-networks and micro-blogging systems [START_REF] Kasiviswanathan | Analyzing graphs with node differential privacy[END_REF][START_REF] Kifer | No free lunch in data privacy[END_REF][START_REF] Task | A guide to differential privacy theory in social network analysis[END_REF], to the best of our knowledge, our approach of disseminating information without anonymizing the users by giving differential privacy guarantees is novel.

CONCLUSION

Privacy is becoming a prominent and continuously raising concern in micro-blogging systems and is somewhat incompatible with the social nature of such platforms, e.g., the identities of followers as well as the information they reposted is known. These systems expect the interesting content to spread and spam to die quickly. In Riposte we take on this challenge and provide a privacy-preserving reposting protocol that ensures that an external attacker cannot tell with certainty whether a user contributed or not to the dissemination of some specific content. This is a powerful property as social platforms play a major role in many countries and may lead to actual arrests. Beyond privacy, Riposte also sustains the expected spreading patterns of posts in a micro-blogging system by achieving a wide spread dissemination of popular posts and limited spread of unpopular posts.

Riposte achieves this trade-off between privacy and dissemination by probabilistically switching the reposting actions of a user. We quantify the privacy property of Riposte analytically and provide bounds on the dissemination patterns. Our experimental results based on a wide range of real topologies (Twitter, Google+, Facebook, Renren and LiveJournal) show that the dissemination patterns indeed reflect the overall interests of posts in the system. We believe that such a protocol could lead to novel kinds of privacy-preserving micro-blogging platforms or be widely adopted by existing ones. Thus, the expected number of new users that learn the post at step t is at most 1 -β, and the expected change in n t is

E[n t -n t-1 | n t-1 ] ≤ (1 -β) -1 = -β, (5)
where the '-1' in the middle expression accounts for the removal of u from N t-1 .

It is now easy to understand the intuition behind the bound we must show: At each step, n t drops in expectation by at least β. If, instead, the actual drop were at least β, then it would follow that the number of steps until n t becomes zero would be at most n 0 /β = d/β, which is equal to the bound we must show.

The formal proof is by a standard martingale argument. For 0 ≤ t ≤ T , let X t = n t + βt. Then for 0 < t ≤ T , we have X t -X t-1 = n t -n t-1 + β, and

E[X t -X t-1 | X 0 . . . X t-1 ] = E[n t -n t-1 + β | X 0 . . . X t-1 ] (5) ≤ 0.
Thus the sequence X 0 , X 1 , . . . , X T is a super-martingale, and T is a stopping time for this sequence. Since the random variable T is bounded (it is at most equal to the total number n -1 of users, excluding the source), we can apply the martingale stopping theorem to obtain

E[X T ] ≤ E[X 0 ].
Substituting the values X T = n T +βT = βT , as n T = 0 by T 's definition, and

X 0 = n 0 = d, yields E[T ] ≤ d/β.
This completes the proof of Theorem 2 for Riposte.

A.3 Proof of Theorem 3

We consider just DB-Riposte; the claim for Riposte follows then from Remark 2.

The proof uses a standard coupling argument to show that the probability of the event we are interested in, that at least a certain fraction of users receive the post, is lower-bounded by the survival probability of an appropriate branching process. Then we bound this survival probability using a result for branching processes.

Recall that a (Galton-Watson) branching process is a random process starting with one or more individuals, and in each step of the process a single individual produces zero of more offsprings and then dies. The number of offsprings of an individual follows a fixed probability distribution that does not vary between individuals. The process either finishes after a finite number of steps, when there are no individuals left, or continues forever. The probabilities of these two complementary events are called extinction and survival probability, respectively.

We compare now the dissemination of a post in G φ , with a branching process we specify. First we compute the distribution of the number of new users that learn the post from a user u, at a point in time when fewer than ℓ users have learned the post, for some ℓ to be exposed later. We have that the probability of u having i followers is φ(i); and if u has i followers, then the probability it reposts is (pλ + (1 -p)δ)/i = (β + 1)/i. Further, if u decides to repost, we can assume that only then its i followers are chosen, and that they are chosen sequentially, one after the other. Then the probability that the j-th follower of u does not already know the post, and thus learns it from u, is at least 1 -ℓ/n, provided that at most ℓ users already know the post (including the first j -1 followers of u, and the source).

Consider now the branching process in which d individuals exist initially, and the number X of offsprings of an individual is chosen as follows. First we choose some integer i ≥ 0 from distribution φ. If i = 0 then X = 0. If i > 0 instead, then with probability (β + 1)/i we let again X = 0; while with the remaining probability, we let X be a binomial random variable B(i, q), counting the number of successes among i independent identical trials with success probability q := 1 -ℓ/n.

Consider now a coupling of the two processes above, the dissemination process and the branching process, until the earliest point in the dissemination process when (at least) ℓ users have received the post, or the dissemination has finished. The coupling is such that the number N t of new users that learn the post in a step t of the dissemination process is greater or equal to the number X t of offsprings produced in the corresponding step of the branching process, for all steps t after which the total number of users that have learned the post is still smaller than ℓ. Such a coupling exists since, by construction, N t dominates stochastically X t .

From the coupling above, the probability that at least ℓ := (1 -ǫ ′ ) • βn/(β + 1) users receive the post in total, is lower-bounded by the probability that the total progeny of the branching process (i.e., the total number of individuals that ever existed) is at least ℓ. Further, the latter probability is lower bounded by the survival probability of the branching process; we denote this by ζ d . Thus to prove the theorem it suffices to show that

ζ d = 1 -e -Ω(d/µ) .
We do so in the remainder of the proof.

By the definition of the branching process, the expected number of offsprings of an individual is

E[X] = i φ(i) • β + 1 i • E[B(i, q)] = i φ(i) β + 1 i • iq = i φ(i) • (β + 1) • q = (β + 1) • q.
We observe that E[X] > 1, as

(β + 1) • q = (β + 1) • 1 - (1 -ǫ ′ )β β + 1 = 1 + ǫ ′ β. (6)
Further, we have

E[X 2 ] = i φ(i) • β + 1 i • E[(B(i, q)) 2 ] = i φ(i) • β + 1 i • (i 2 q 2 + iq(1 -q)) = i φ(i) • (β + 1) • (iq 2 + q(1 -q))
= (β + 1) • (µq 2 + q(1 -q)),

where µ = i φ(i) • i is the mean of φ. We will use the following standard lower bound on the survival probability ζ 1 , when there is just one individual initially (see, e.g., in [8, Section 5.6.1]),

ζ 1 ≥ 2(E[X] -1) E[X 2 ] -E[X]
.

Substituting the values for E[X] and E[X 2 ] computed above yields ζ 1 ≥ 2(q(β + 1) -1) (β + 1)(µq 2 + q(1 -q)) -q(β + 1) = 2(q(β + 1) -1) q 2 (β + 1)(µ -1) = 2(q(β + 1) -1)(β + 1) q 2 (β + 1) 2 (µ -1) This completes the proof of Theorem 3.

Figure 1 :

 1 Figure 1: In Riposte, the user's opinion is locally randomized, and only the output of Riposte is exposed to the online service. The ¬Repost arrow is represented for illustration purposes and is not an explicit action of Riposte.

Figure 2 :

 2 Figure 2: Illustration of Ineq. (3) that provides upper and lower bounds on q in terms of q. Probability q diverges more from q as λ increases or δ decreases.

Figure 3 :

 3 Figure 3: Spreading patterns under Riposte, DB-Riposte and Standard protocols (Uniform opinion model)

Figure 4 :

 4 Figure 4: Spreading patterns under Riposte, DB-Riposte and Standard protocols (Distance-threshold opinion model)

  recall = |users who like the post ∩ users who receive the post| |users who like the post| This metric measures how well the dissemination algorithm is able to disseminate the post among users who like it. Precision. precision = |users who like the post ∩ users who receive the post| |users who receive the post| This is an indication of how many users receive posts they are not interested in. Spam rate. spam = |users who dislike the post ∩ users who receive the post| |users who dislike the post|

Figure 5 :

 5 Figure 5: Spreading patterns under Riposte, all datasets (Uniform opinion model)

Figure 6 :

 6 Figure 6: Spreading patterns of unpopular posts in Riposte and DB-Riposte when compared to the theoretical bound (Uniform opinion model)

Figure 7 :

 7 Figure 7: Spreading characteristics under Riposte, DB-Riposte and the Standard protocol, LiveJournal data-set (Distance-threshold model)

  (b) δ = 0.75, variation of λ

Figure 8 :

 8 Figure 8: Effect of the variations of λ and δ, LiveJournal (Uniform model)

=

  2ǫ ′ β(β + 1) (1 + ǫ ′ β) 2 (µ -1) = Ω(1/µ),where the last equation holds becauseβ = (p -p * )(λδ) ≥ ǫ(λ -δ) = Ω(1).We can now express ζ d in terms of ζ 1 , by observing that the branching process starting with d individuals can be viewed as d independent branching processes starting with a single individual each. The former branching process survives if and only if at least one of the latter ones survives, thus,ζ d = 1 -(1 -ζ 1 ) d ≥ 1 -e ζ1d = 1 -e Ω(d/µ) .

Table 1 :

 1 Number of users convicted such that the probability to convict a innocent user is at most 0.5.

	p	users	guilty	convicted 5 posts 10 posts 20 posts
		100	1	0.0	0.0	0.1
	0.01	1,000 10,000	10 100	0.0 0.0	0.1 0.5	0.7 1.8
		100,000	1,000	0.2	1.5	5.0
		100	10	0.6	1.1	1.8
	0.1	1,000 10,000	100 1,000	1.4 3.5	3.0 6.8	6.5 19
		100,000 10,000	5.3	17	54.1
		100	30	1.9	3.7	6.2
	0.3	1,000 10,000	300 3,000	4.9 12.7	10.8 23.3	21.1 63.9
		100,000 30,000	20.2	63.4	190.9

  .

	Name	# Users # Links Average	#
				Followers
	Twitter	42M	1468M	35
	Renren	1M	58M	58
	LiveJournal 4.8M	69M	14
	Facebook	3M	47M	16
	Google+	107K	14M	130

Table 2 :

 2 Data-Sets characteristics

	Fraction of users receiving the post	0 0.2 0.4 0.6 0.8 1	0	0.2 Standard Popularity of the post 0.4 0.6 λ=3 and δ=0.75 Riposte DB-Riposte	0.8	1

9

http://snap.stanford.edu/data/soc-LiveJournal1. html 10 http://snap.stanford.edu/data/egonets-Gplus.html

Note that such a human filter is first difficult to reproduce

Riposte does not protect the privacy of the source of a post. This is a reasonable assumption since a lot of posts originate from media.

We stress that the popularity of posts is not known in advance.

For the asymptotic bounds we show later, we assume for a popular post that p > p * + ǫ, and for an unpopular post that p < p * -ǫ, for some arbitrary small constant ǫ > 0.

In the uniform model, the opinion of the user is independent from her position in the network, thus the precision depends only on the popularity of the post, and not on the spreading algorithm

The source user belongs to set D.

APPENDIX A. OMITTED PROOFS A.1 Proof of Observation 1

If a user u likes the post it is reposted with probability r like (d) by DB-Riposte, and with probability r like (s) by Riposte, where d is the total number of u's followers and s is the number of those followers that do not know the rumor yet. Since s ≤ d it follows that r like (s) ≥ r like (d), if s > 0. Similarly, if u does not like the post it is reposted with probabilities r dis (s) and r dis (d), respectively, and r dis (s) ≥ r dis (d). The claim now follows by a standard coupling argument. Since each user has the same opinion in both cases, we can couple the random choices of the two protocols so that DB-Riposte does a reposts from u only if Riposte also reposts from u. This coupling ensures that the set of users who receive the post when DB-Riposte is used is a subset of those who receive the post with DB-Riposte. This implies that Pr(N ≥ k) ≥ Pr(N db ≥ k), for all k.

A.2 Proof of Theorem 2 for RIPOSTE

We consider the following representation of the random process underlying the dissemination of the post. At each point in time users are divided into three sets: (1) the set D of those who have received the post and either have reposted it, or it has been decided they will not repost; (2) the set N of users who have received the post but it has not yet been decided whether they will repost or not; and (3) the set S of the remaining users, who have not received the post yet. 12 We assume that dissemination proceeds in steps: At each step, a single user u from set N is considered, and this user either reposts the post or it is decided to not repost. As a result, u is moved from set N to set D, and if u reposts then all its followers from set S are moved to N . The dissemination is completed when the set N becomes empty. For our analysis, the order in which the users from N are considered can be arbitrary.

We denote by D t and N t the values of the corresponding sets defined above after the first t steps; we assume that D 0 contains just the source of the post, and N 0 contains the d followers of the source.

Let n t = |N t |. The total number T of users that receive the post (excluding the source) is then T = min{t : n t = 0}. Suppose that t ≤ T (and thus n t-1 > 0), and consider the expected change on n t in round t: If the user u considered in step t has s followers that have not received the post yet, then the probability u reposts is p • r like (s) + (1 -p) • r dis (s) ≤ pλ + (1 -p)δ s = 1 -β s .


Rabah Rabah

Grigory Sklyar

Observability and controllability for linear neutral type systems

For a large class of linear neutral type systems which include distributed delays we give the duality relation between exact controllability and exact observability. The characterization of exact observability is given.

I. INTRODUCTION

Our purpose is to study the problem of exact observability of a large class of linear neutral type system. The cases of approximate and spectral controllability and the corresponding dual notions of observability were widely investigated at the end of the last century (see books by [START_REF] Bensoussan | Representation and control of infinite-dimensional systems[END_REF] and [START_REF] Salamon | Control and observation of neutral systems[END_REF] and references therein). The duality between these notions is not so simple. The main reason is that the dual or adjoint system is not obtained directly by simple transposition. It is necessary to consider the duality using some hereditary product proposed first for retarded systems and later for neutral type systems (see [START_REF] Delfour | The structural operator F and its role in the theory of retarded systems. II[END_REF], [START_REF] Delfour | The structural operator F and its role in the theory of retarded systems. I[END_REF], [START_REF] Salamon | On controllability and observability of time delay systems[END_REF] and [START_REF] Salamon | Control and observation of neutral systems[END_REF] for example). An important tool in this context is the structural operator. It enables some explicit expression for duality between approximate controllability, spectral controllability and approximate observability. Moreover, there are several interesting results concerning these notions of observability and controllability and about duality.

The cases of exact controllability and exact observability for neutral type systems are less developed. The infinite dimensional setting has been developed essentially for exact controllability and often for neutral type systems without distributed delays. In [START_REF] Metel | Criteria for the constructive identifiability and complete controllability of linear time-independent systems of neutral type[END_REF], [START_REF] Khartovskiȋ | The complete controllability problem and its generalization for linear autonomous systems of neutral type[END_REF] and [START_REF] Khartovskiȋ | Complete controllability and controllability for linear autonomous systems of neutral type[END_REF] an approach is described based on the reconstruction of a part of the state for the case of a neutral type system with discrete delays. A duality condition with null controllability is given. The time of controllability (or of possible reconstruction of a part of the state) is estimated "sufficiently large".

The present paper is concerned with exact observability which is related to the notion of exact controllability developed in [START_REF] Rabah | The analysis of exact controllability of neutral-type systems by the moment problem approach[END_REF]. The semigroup approach used there is based on the model introduced in [START_REF] Burns | Linear functionaldifferential equations as semigroups on product spaces[END_REF]. In the infinite dimensional setting described in [START_REF] Rabah | The analysis of exact controllability of neutral-type systems by the moment problem approach[END_REF], exact controllability means reachability of the state space operator domain because reachability of all the state space is not possible by finite dimensional control. Hence, the dual notion of observability is also adapted. The approach using the structural operator is not used. Considering the adjoint systems in the infinite dimensional framework, we construct a transposed neutral type system corresponding to this adjoint system. This relation between the semigroup and the neutral type system is different from that of the model given in [START_REF] Burns | Linear functionaldifferential equations as semigroups on product spaces[END_REF]. These notions are important because they imply exponential stabilizability or exponential convergences for possible estimators.

The approach developed in [START_REF] Rabah | The analysis of exact controllability of neutral-type systems by the moment problem approach[END_REF] uses the theory of moments problem and allows the minimal time of exact controllability to be determinated. We specify here how duality may be used and then we give not only the conditions for exact observability but also the minimal time of observability.

We consider the following neutral type system

ż(t ) = A -1 ż(t -1)+ 0 -1 [A 2 (θ) ż(t + θ) + A 3 (θ)z(t + θ)] dθ (1)
where A -1 is a constant n ×n-matrix, and A 2 , A 3 are n ×nmatrices whose elements belong to L 2 (-1, 0). If we introduce the linear operator L defined by

L f = 0 -1 A 2 (θ) f ′ (θ) + A 3 (θ) f (θ)dθ (2)
then the system may be written concisely as

ż(t ) = A -1 ż(t -1) + Lz t , z t (θ) = z(t + θ).
This system may be represented, following the approach developed in [START_REF] Burns | Linear functionaldifferential equations as semigroups on product spaces[END_REF], by an operator model in Hilbert space given by the equation

ẋ = A x, x(t ) = v(t ) z t (•) , ( 3
)
where A is the infinitesimal generator of a C 0 -semigroup given in the product space

M 2 = M 2 (-1, 0; R n ) def = R n × L 2 (-1, 0; R n )
and defined by

A x(t ) = A v(t ) z t (•) = Lz t (•) dz t (θ)/dθ , (4)
with the domain

D(A ) ⊂ M 2 given by v ϕ(•) : ϕ(•) ∈ H 1 , v = ϕ(0) -A -1 ϕ(-1) , (5)
where

H 1 = H 1 ([-1, 0]; R n ).
The output of the system. We consider the finite dimensional observation

y(t ) = C x(t ) (6)
where C is a linear operator and y(t ) ∈ R p is a finite dimensional output. There are several ways to design the output operator C [START_REF] Salamon | Neutral functional differential equations and semigroups of operators[END_REF], [START_REF] Salamon | Control and observation of neutral systems[END_REF], [START_REF] Metel | Criteria for the constructive identifiability and complete controllability of linear time-independent systems of neutral type[END_REF]. One of our goal in this paper is to investigate how to design a minimal output operator like

C x(t ) = C z(t ) or C x(t ) = C z(t -1), ( 7
)
where C is a p × n matrix. More general output, for example with several and/or distributed delays are not considered in this paper. We want to use some result on exact controllability in order to analyze, by duality, the exact observability property in the infinite dimensional setting like, for example, in [START_REF] Tucsnak | Observation and control for operator semigroups[END_REF].

The operator C defined in ( 7) is linear but not bounded in M 2 . However, in both cases it is admissible in the following sense:

T 0 C S(t )x 0 2 R n dt ≤ κ 2 x 0 2 M 2 , ∀x 0 ∈ D(A ),
because it is bounded on D(A ). We recall that if x 0 ∈ D(A ) then S(t )x 0 ∈ D(A ), t ≥ 0 (see for example [START_REF] Pazy | Semigroups of linear operators and applications to partial differential equations[END_REF]).

In fact, C is admissible in the resolvent norm:

x 0 -1 = (λI -A ) -1 x 0 = R(λ, A )x 0 , λ ∈ ρ(A )
. This is a consequence of the fact that C is a closed operator and takes value in a finite dimensional space (see [START_REF] Tucsnak | Observation and control for operator semigroups[END_REF]Definition 4.3.1] and comments on this Definition). Definition 1.1: Let K be the output operator

K : M 2 -→ L 2 (0, T ; R p ), x 0 -→ K x 0 = C S(t )x 0 .
The system (1) is said to be observable (or approximately observable) if ker K = {0} and exactly observable if

T 0 C S(t )x 0 2 R p dt ≥ δ 2 x 0 2 , (8)
for some constant δ. This is the classic definition. In the case of a neutral type system with a finite dimensional output [START_REF] Khartovskiȋ | The complete controllability problem and its generalization for linear autonomous systems of neutral type[END_REF] the exact observability in this sense is not possible. It may be possible if we consider another topology for the initial states x 0 . Unlike approximate observability, which does not depend on the topology, exact observability depends essentially on the topology in the space. We can show that, the given neutral type system is not exactly observable if we consider x 0 ∈ D(A ), with the norm of the graph and no longer in the topology of M 2 . Moreover, in our case the relation (8) must be changed by taking a weaker norm for x 0 , namely the resolvent norm R(λ, A )x 0 and considering the extension of the operator K to the completion of the space with this norm.

Exact observability can be investigated directly, but another way is to use the duality between exact observability and exact controllability. In [START_REF] Rabah | The analysis of exact controllability of neutral-type systems by the moment problem approach[END_REF] the conditions of exact controllability were given for the controlled system (33). In order to use the duality between observability and controllability, we need to compute the adjoint operator K * in the duality with respect to the pivot space M 2 in the embedding

X 1 ⊂ X = M 2 ⊂ X -1 , (9)
where X 1 = D(A ) with the graph norm noted x 1 and X -1 is the completion of the space M 2 with respect to the resolvent norm x -1 = (λI -A ) -1 x . The duality relation is

〈K x 0 , u(•)〉 L 2 (0,T ;R p ) = x 0 , K * u(•) X 1 ,X d -1 , ( 10
)
where X d -1 is constructed as X -1 with A * instead of A (see [START_REF] Tucsnak | Observation and control for operator semigroups[END_REF] for example). Our purpose is to compute the adjoint operator

K * : L 2 (0, T ; R p ) → X d -1 .
The abstract formulation is well known. Exact controllability is dual with exact observability in the corresponding spaces with the corresponding topologies. It is expected that the operator K * corresponds to a control operator for some adjoint system.

We then need to calculate the adjoint state operator A * and the corresponding adjoint system in the same class: the class of neutral type systems. We shall see that the situation is not so simple.

This paper is organized as follows. First we give the duality relation in Section 2. Section 3 is concerned with the calculation of the adjoint system of neutral type . Then we return to the duality relation with the explicit expression of the adjoint system after formulation of exact controllability results. As the adjoint neutral type system has a slghtly different structure, we give an explicit relation between the new neutral type system and the original one. After that we can give the expression of duality between exact controllability and exact observability.

II. THE ADJOINT OPERATOR A *

We now give the expression of the adjoint operator for A obtained by [START_REF] Rabah | On strong regular stabilizability for linear neutral type systems[END_REF]. Of special interest is the characterization of the eigenvectors of A * to be used in the next sections.

Theorem 2.1: The adjoint operator A * is given by

A * w ψ(•) = (A * 2 (0)w + ψ(0) - d[ψ(θ)+A * 2 (θ)w] dθ + A * 3 (θ)w , ( 11
)
with the domain D(A * ):

w, ψ(•) : ψ(θ) + A * 2 (θ)w ∈ H 1 , A * -1 A * 2 (0)w + ψ(0) = ψ(-1) + A * 2 (-1)w . ( 12
)
The eigenvectors of A * are given by

w E * (λ, θ)w , w ∈ Ker∆ * (λ) ( 13
)
where E * (λ, θ) and ∆ * (λ) are the matrices

E * (λ, θ) = λe -λθ -A * 2 (θ) + θ 0 e λ(s-θ) A * 3 (s) + λA * 2 (s) ds, ∆ * (λ) = λI -λe -λ A * -1 - 0 -1 e λs A * 3 (s) + λA * 2 (s) ds.
The eigenvalues are the roots of the equation det ∆ * (λ) = 0.

III. THE ADJOINT SYSTEM

In this section we give the expression of the adjoint system corresponding to the adjoint operator A * as the operator A corresponds to the system (1).

Theorem 3.1: Let x be a solution of the abstract equation

ẋ = A * x, x(t ) = w(t ) ψ t (θ) . ( 14
)
Then the function w(t ) is the solution of the neutral type equation

ẇ(t + 1) = A * -1 ẇ(t )+ 0 -1 A * 2 (τ) ẇ(t + 1 + τ) + A * 3 (τ)w(t + 1 + τ) dτ. ( 15
)
We want to find the corresponding neutral type equation in R n . Equation ( 14) may be written as

∂ ∂t w(t ) ψ t (θ)) = A * 2 (0)w(t ) + ψ t (0) - ∂[ψ t (θ)+A * 2 (θ)w(t )] ∂θ + A * 3 (θ)w(t ) Let us denote by r (θ) = A * 2 (θ)w + ψ(θ) and r (t , θ) = A * 2 (θ)w(t ) + ψ t (θ) = A * 2 (θ)w(t ) + ψ t (θ). (16)
Then A * may be rewritten as

A * w r (θ) -A * 2 (θ)w = r (0) -dr (θ) dθ + A * 3 (θ)w , ( 17
)
and the system ẋ = A * x as

∂ ∂t w(t ) r (t , θ) -A * 2 (θ)w(t ) = r (t , 0) -∂r (t ,θ) ∂θ + A * 3 (θ)w(t ) . ( 18
)
The second line of this equation gives

∂ ∂t r (t , θ) + ∂ ∂θ r (t , θ) = A * 2 (θ) ẇ(t ) + A * 3 (θ)w(t ). ( 19
)
The general solution of this partial differential equation is

r (t , θ) = f (t -θ)+ θ 0 A * 2 (τ) ẇ(t -θ + τ) + A * 3 (τ)w(t -θ + τ) dτ, ( 20
)
where f (t -θ) is the solution of the homogenous equation obtained from (19):

∂ ∂t r (t , θ) + ∂ ∂θ r (t , θ) = 0.
and the second term is a particular solution of (19). The first line of the equation (18) gives

ẇ(t ) = r (t , 0). ( 21
)
From (20) (obtained from the second line), putting θ = 0, we get with ( 21)

ẇ(t ) = r (t , 0) = f (t ). ( 22
)
Then ( 20) and ( 22) allow r (t , θ) to be written as follows:

r (t , θ) = ẇ(t -θ)+ θ 0 A * 2 (τ) ẇ(t -θ + τ) + A * 3 (τ)w(t -θ + τ) dτ. ( 23
)
From the definition of the domain D(A * ) we obtain A * -1 r (0) = r (-1), or A * -1 r (0)r (-1) = 0. For the function r (t , θ), this condition reads

r (t , -1) = A * -1 r (t , 0) = A * -1 ẇ(t ) (24)
and by (23) we have

r (t , -1) = ẇ(t + 1)- 0 -1 A * 2 (τ) ẇ(t + 1 + τ) + A * 3 (τ)w(t + 1 + τ) dτ. ( 25
)
Finally, from ( 24) and (25), we obtain the dual equation

ẇ(t + 1) = A * -1 ẇ(t )+ 0 -1 A * 2 (τ) ẇ(t + 1 + τ) + A * 3 (τ)w(t + 1 + τ) dτ. ( 26
)
On the other hand the solution of equation ( 18) is

e A * t x 0 = w(t ) ψ t (θ) = w(t ) r (t , θ) -A * 2 (θ)w(t ) , (27)
where w(t ) is the solution of equation ( 26). If x 0 ∈ X then it is a mild solution. This result may also be formulated in the following way. Theorem 3.2: Let x be a solution of the abstract equation

ẋ = Ã x, x(t ) = w(t ) ψ t (θ) ,
where the operator à is defined by

à w ψ(•) = A 2 (0)y + ψ(0) - d[ψ(θ)+A 2 (θ)y] dθ + A 3 (θ)w ,
with the domain

D( Ã ) = w, ψ(•) : ψ(θ) + A 2 (θ)w ∈ H 1 , (A -1 A 2 (0) -A 2 (-1)) w = ψ(-1) -A -1 ψ(0) .
Then the function w(t ) is the solution of the neutral type equation

ẇ(t + 1) = A -1 ẇ(t )+ 0 -1 [A 2 (τ) ẇ(t + 1 + τ) + A 3 (τ)w(t + 1 + τ)] dτ. ( 28
)
Let us now specify the relation between the solutions of neutral type equations ( 28) and (1). Let us put

w(t ) ψ t (θ) = e à t x0 = e à t w(0) ψ 0 (θ) , and
v(t ) z t (θ) = w(t + 1) -A -1 w(t ) w(t + 1 + θ) = e A t v(0) z 0 (θ) = e A t ξ 0 ,
where z 0 (θ) = w(t + 1) and v(0) = z 0 (0) -A -1 z 0 (-1). Our purpose is to give the explicit relation between the initial conditions x0 and ξ 0 :

x0 = w(0) ψ 0 (θ) , ξ 0 = v(0) z 0 (θ) .
The formal relation between these vectors is

x0 = w(0) ψ 0 (θ) ) = F ξ 0 = F w(1) -A -1 w(0) w(θ + 1) .
Let us calculate the explicit expression for the linear operator F . From ( 23) and ( 16) we obtain

r (0, θ) = ψ 0 (θ) + A 2 (θ)w(0) = ẇ(-θ) + θ 0 [A 2 (τ) ẇ(τ -θ) + A 3 (τ)w(τ -θ)] dτ, (29)
which can be written as

r (0, θ) = ẇ(-θ) + θ 0 [A 2 (θ -s) ẇ(-s) + A 3 (θ -s)w(-s)] ds.
Putting w(-s) = s 0 ẇ(-σ)dσ + w(0), we get r (0, θ) -

θ 0 A 3 (θ -s)ds • w(0) = ẇ(-θ)+ θ 0 A 2 (θ -s) ẇ(-s) + A 3 (θ -s) s 0 ẇ(-σ)dσ ds. ( 30
)
This may be represented by the expression r (0, θ) -

θ 0 A 3 (θ -s)ds • w(0) = (I + V ) ẇ(-s), ( 31
)
where V is the Volterra operator defined by

V µ(•) = θ 0 A 2 (θ -s)µ(s) + A 3 (θ -s) s 0 µ(σ)dσ ds.
The operator V is a compact linear operator from L 2 (-1, 0; R n ) to L 2 (-1, 0; R n ) with a spectrum σ(V ) = {0}. This implies that the operator

I + V is bounded invertible on L 2 (-1, 0; R n ).
Let us now represent the operator F as a composition of operators according to the following commutative diagram v(0) z 0 (θ)

F P / / w(0) ẇ(-θ) Q w(0) ψ 0 (θ) R o o w(0) (I + V ) ẇ(-s)
where, as explained above, v(0) z 0 (θ) = w(1) -A -1 w(0) w(θ + 1) and

(I + V ) ẇ(-s) = r (0, θ) + -θ 0 A 3 (θ + s)ds • w(0).
The operators P : X 1 → M 2 and R : M 2 → M 2 are bounded invertible. Moreover, as

I + V : L 2 (-1, 0; R n ) → L 2 (-1, 0; R n ) is bounded invertible, then Q : M 2 → M 2 is also bounded invertible.
We can summarize these considerations in the following theorem. 28) is linear bounded and bounded invertible from X 1 to M 2 . We also need the following property of the bounded operator F -1 . Proposition 3.4: For λ = σ( Ã ), the operator

Theorem 3.3: The operator F representing the relation between initial conditions x0 and ξ 0 corresponding to the neutral type systems (1) and (

F -a = F -1 (λI -Ã )
can be extended to a bounded (and bounded invertible) operator from M 2 to M 2 .

Proof: We need to prove that

F -1 (λI -Ã ) x0 ≤ C x0 , x0 ∈ D( Ã ),C > 0, ( 32
)
where • is the initial norm in M 2 . Let L 0 and D 0 be the subspaces

L 0 = {(0, ψ(•) : ψ(•) ∈ L 2 (-1, 0; R n )}, D 0 = L 0 ∩ D( Ã ).
It is clear that D 0 is of finite co-dimension n, and this implies that it is enough to prove the relation (32) for x0 ∈ D 0 . Let x0 = (0, ψ 0 (•) ∈ D 0 . The action of the operator F -a = F -1 (λI -Ã ) may be decomposed according to the following diagram

0 ψ 0 (•) (λI -Ã ) -→ ψ 0 (0) λψ 0 (•) -ψ0 (•) R -1 -→ R -1 ψ 0 (0) λψ 0 (•) -ψ0 (•) ↓ F -a ↓ Q -1
w(1) -A -1 ψ 0 (0) w(θ + 1)

P -1 o o ψ 0 (0) ẇ(-θ)
where

R -1 ψ 0 (0) λψ 0 (•) -ψ0 (•) =   ψ 0 (0) λψ 0 (•) -ψ0 (•) + -θ 0 A 3 (θ + s)dsψ 0 (0)  
and the function w(•) is determinated from the equation (obtained from (29))

λψ 0 (θ) -ψ0 (θ) + A 2 (θ)ψ 0 (0) = ẇ(-θ) + θ 0 [A 2 (τ) ẇ(τ -θ) + A 3 (τ)w(τ -θ)] dτ
with the initial condition w(0) = ψ 0 (0). Integrating the last equation from 0 to -1-θ and taking in account the initial condition, we obtain

-ψ(-1 -θ) -λ -1-θ 0 ψ(τ)dτ + -1-θ 0 A 2 (τ)dτ • ψ 0 (0) = -w(1 + θ) + -1-θ 0 τ 0 A 2 (s) ẇ(s -τ) + A 3 (s)w(s -τ)ds dτ.
After a transformation in the double integration, and with the initial condition, we get

ψ(-1 -θ) + λ -1-θ 0 ψ(τ)dτ = -1-θ 0 A 2 (s) ẇ(1 + θ + τ) - τ 0 A 3 (s)w(s -τ)ds dτ,
and this can be written as

(I + V 1 )ψ 0 (-1 -θ) = (I + V 2 )w(1 + θ), θ ∈ [-1, 0],
where V 1 and V 2 are Volterra operators from L 2 (-1, 0; R n to L 2 (-1, 0; R n . Both operators have spectra concentrated at {0}. Then

w(1 + θ) = (I + V 2 ) -1 (I + V 1 )ψ 0 (-1 -θ) = W ψ 0 (-1 -θ),
where W is a bounded invertible operator. Putting θ = -1 in the relation between ψ 0 and w we get ψ 0 (-1) = w( 1). This enables the final expression for the operator F -a = F -1 (λI -Ã ) on the set D 0 to be obtained:

F -a 0 ψ 0 (θ) = ψ 0 (-1) -A -1 ψ 0 (0) W ψ 0 (-1 -θ) = 0 W ψ 0 (-1 -θ) ,
because, by the definition of D 0 = L 0 ∩ D( Ã ) we have

ψ 0 (-1) -A -1 ψ 0 (0) = 0.
This means that the operator F -1 (λI -Ã ) is continuous with continuous inverse from L 0 to L 0 (in the norm of M 2 ). Hence, F -1 (λI -Ã ) may be extended as a bi-continuous operator on all M 2 because

F -1 (λI -Ã )D( Ã ) = D(A ).
The proof of the proposition is complete.

A direct consequence of this proposition is the following corollary.

Corollary 3.5: For all x ∈ D( Ã ), for λ = σ(A ), we have

c x ≤ (λI -Ã ) -1 F x ≤ C x .

IV. THE CONTROL SYSTEM AND DUALITY

Consider the controlled neutral type system

ż(t ) = A -1 ż(t -1) + Lz t + Bu(t ), (33)
where u(t ) ∈ L 2 (0, T ; R m ) is a m-dimensional control vector-function. This system may be represented by an operator model in Hilbert space given by the equation

ẋ = A x + Bu(t ), x(t ) = v(t ) z t (•) , (34)
where Bu = (Bu, 0) is linear and bounded from R to M 2 . We can note that B is not bounded from M 2 to X 1 (M 2 with the norm of the graph of A ) because Bu = (Bu, 0) ∉ D(A ) if Bu = 0.

A. Exact controllability

Let us denote by R T ⊂ M 2 the reachable subspace of the system (34):

R T = R T u(•) = T 0 e A t Bu(t )dt : u(t ) ∈ L 2 (0, T ; R m ) ,
where R T : L 2 → M 2 is a linear bounded operator.

As was pointed out in [START_REF] Ito | A linear quadratic optimal control for neutral systems[END_REF] and [START_REF] Rabah | The analysis of exact controllability of neutral-type systems by the moment problem approach[END_REF], R T ⊂ D(A ) for all T > 0. This implies that exact controllability may be defined as follows.

Definition 4.1: The system (34) is exactly controllable if R T = D(A ). The abstract condition of exact controllability is (see [START_REF] Rudin | Functional analysis[END_REF] for example)

T 0 B * e A * t x 2 R m dt ≥ δ 2 x 2 X d -1 , ∀x ∈ D(A * ), (35)
which means that the operator R T : L 2 → X 1 is onto. Here the space X d -1 is the completion of the space X = M 2 with respect to the norm

x X d -1 = (λI -A * ) -1 x , λ ∉ σ(A * ).
For the system (33) the condition of exact controllability is given by the following theorem (see [START_REF] Rabah | The analysis of exact controllability of neutral-type systems by the moment problem approach[END_REF]).

Theorem 4.2: The system (33) is exactly controllable at time T if and only if, for all λ ∈ C, the following two conditions are verified i) There is no vector z = 0 such that B * z = 0 and

∆ * (λ)z = 0,
ii) There is no eigenvector z of the matrix A * -1 such that B * z = 0.

The time of controllability is T > n

1 (A -1 , B ).
The integer n 1 (A -1 , B ) is the controllability index of the pair (A -1 , B ) (see [START_REF] Wonham | Linear multivariable control[END_REF]). If the delay is h, then the critical time is n 1 h.

Let us now consider the dual notion of observability for the adjoint system. The condition (39) is equivalent to the exact observability of the observable system

ẋ = A * x, y = B * x (36)
and the corresponding neutral type system is the system [START_REF] Ito | A linear quadratic optimal control for neutral systems[END_REF]. Then the conditions (i)-(ii) of Theorem 4.2 are necessary and sufficient for the exact controllability of the adjoint system (36). But what is the corresponding property for the associate neutral type system (26)? This will be shown in the following paragraph.

B. Duality

Consider the transposed controlled neutral type system

ż(t ) = A * -1 ż(t -1) + L * z t +C * u(t ), (37)
where L * f = 0 because this operator does not correspond directly to this system as the generator of the semigroup of solutions. The domain D(A † ) of the operator A † is given by

v z(•) : z ∈ H 1 ([-1, 0]; C n ), v = z(0) -A * -1 z(-1) . The spectrum of A † is σ(A † ) = {λ : ∆ * (λ) = 0} = σ(A * ).
Let X † 1 be D(A † ) with the norm

x X † 1 = (λI -A † )x , λ ∉ σ(A † ),
which is equivalent to the graph norm. Consider now the reachability operator for this system

R † T u(t ) = T 0 e A † t C * 0 u(t )dt .
From the properties of the operator R T , we can deduce that R † T is linear, bounded from L 2 (0, T ; R ) to X † 1 . The exact controllabilty for the system (37) can be formulated as

R † T = Im R † T = X † 1 .
The conditions of exact controllability for this system (37) may be obtained directly from Theorem 4.2.

Let us now consider the corresponding space X † -1 of linear functionals on X † 1 as a the completion of the space X = M 2 with respect to the norm

x X † -1 = (λI -A † ) -1 x , λ ∉ σ(A † ).
We then have the embedding

X † 1 ⊂ X = M 2 ⊂ X † -1 . (38)
Then, for x ∈ X † 1 and y ∈ X † -1 , the functional acts as

x, y X † 1 ,X †d -1 = (λI -A † ) -1 x, (λI -A † * ) -1 y X ,
where A † * is the adjoint of the operator A † in M 2 , and the space X †d -1 is constructed as X †d -1 with A † * instead of A † (see [START_REF] Tucsnak | Observation and control for operator semigroups[END_REF] for example).

Let us note that the operator A † * is in fact the operator à defined in Section III (see Theorem 3.2 and later). We shall use the properties obtained for this operator.

Let us now consider the adjoint R † * T of R † T with respect to the duality induced by X † 1 and X †d -1 with the pivot space

X = M 2 . Let x 0 ∈ X , then R † T u(•), x 0 X 1 ,X d -1 = R † T u(•), x 0 X = T 0 e A † t C * 0 u(t )dt , x 0 X = T 0 C * 0 u(t ), e A † * t x 0 X dt . Suppose now that x 0 = w(0) ψ 0 (θ) ∈ D(A † * ).
Then, as a consequence of the results in Section III, namely from (27) but for the operator A † * = Ã , we obtain

e A † * t x 0 = w(t ) ψ t (θ) = w(t ) r (t , θ -A 2 (θ)w(t ) , t ≥ 0. Hence, R † T u(•), x 0 X = T 0 〈u(t ),C w(t )〉 R p dt = u(•), R † * T x 0 L 2 .
On the other hand, we can write x 0 = F ξ 0 (cf. Proposition 3.4), where

ξ 0 = v(0) z 0 (θ) = z 0 (0) -A -1 z 0 (-1) z 0 (θ) = w(1) -A -1 w(0) w(θ + 1) ,
and then

e A t ξ O = w(t + 1) -A -1 w(t ) w(t + 1 + θ) .
Let K be the output operator introduced in Definition 1.1. Then

〈u(•), K ξ 0 〉 L 2 = u(•), C e A t ξ 0 L 2 = T 0 〈u(t ),C w(t )〉 R p dt if C x(t ) = C z(t -1) T 0 〈u(t ),C w(t + 1)〉 R p dt if C x(t ) = C z(t )
, which implies for all x 0 ∈ X :

K F -1 x 0 = R † * T x 0 if C x(t ) = C z(t -1), e A † * R † * T x 0 if C x(t ) = C z(t ).
We can now formulate our main result on duality. Theorem 4.3: 1. The system [START_REF] Bensoussan | Representation and control of infinite-dimensional systems[END_REF] with the output

y(t ) = C x(t ) = C z(t -1)
is exactly observable in the interval [0, T ], i.e.

K x 0 2 = T 0 C e A t x 0 2 ≥ δ 2 x 0 2
if and only if the adjoint system (37) is exactly controllable a time T , i.e.

R T = R T (L 2 (0, T ; R p ) = X † 1 = D(A † ).

If det

A -1 = 0, assertion 1 of the theorem is verified for the output y(t ) = C x(t ) = C z(t ),
and for the same time T . Proof: The condition of exact controllability is (see [START_REF] Rudin | Functional analysis[END_REF] for example)

R † * T x 0 L 2 ≥ δ (λI -A † * ) -1 x 0 , ∀x ∈ X . ( 39
)
Let ξ 0 = F -1 x 0 ∈ D(A ), where F : D(A ) → M 2 is the bounded invertible operator defined in Section III. Let us remember that

R † * T x 0 = K F -1 x 0 = K ξ 0 . Then the inequality (39) is equivalent to K ξ 0 L 2 ≥ δ (λI -A † * ) -1 F ξ 0 , ξ 0 ∈ D(A ). ( 40
)
Suppose now that the relation ( 40) is verified for all ξ 0 ∈ D(A ), then from Corollary 3.5 we obtain

K ξ 0 L 2 ≥ δ (λI -A † * ) -1 F ξ 0 ≥ δc =δ 1 ξ 0 , ξ 0 ∈ D(A ).
This inequality can be extended by continuity to ξ 0 ∈ M 2 :

K ξ 0 L 2 ≥ δ 1 ξ 0 , ∀ξ 0 ∈ M 2
Conversely, suppose that the preceding relation is verified. For ξ 0 ∈ D(A ), and from Corollary 3.5, we get

ξ 0 ≥ 1 C λI -A † * -1 F ξ 0 ,
and then

K ξ 0 L 2 ≥ δ 1 C λI -A † * -1 F ξ 0 .
This is the relation (40) with δ = δ 1 /C . As the relations (39) and ( 40) are equivalent, the first assertion of the theorem is proved.

To prove item 2 of the theorem, it is sufficient to remark that the condition det A -1 = 0 is equivalent to the fact that the operator e A is bounded invertible (e A t is a group), and then the relations (39) and (40) are equivalent.

From this result and from Theorem 4.2 we can formulate the condition of exact observability. The conditions of observability are verified, and the system is exactly observable for the output y 0 or y 1 .

Example 2. Consider the system ż(t ) = 0, where z(t ) ∈ R n , n > 1, with two possible output y 0 (t ) = C 0 x(t ) = z(t ), y 0 (t ) = C 1 x(t ) = z(t -1).

The system with the output y 1 is exactly observable for the time T > 1 and not observable for T = 1. The system with the output y 0 is not observable for any time T > 0.

VI. CONCLUSION

Duality between exact controllability and observability for a wide class of neutral type systems is analyzed by an infinite dimensional approach. We give an explicit neutral type system wich corresponds to the abstract adjoint system.

  Theorem 4.4: 1. The system[START_REF] Bensoussan | Representation and control of infinite-dimensional systems[END_REF] with the output y = C z(t -1) is exactly observable over [0, T ] if and only if i) For all λ ∈ C, rank ∆ * (λ) C * = n, ii) For all λ ∈ C, rank λI -A * -1 C * = n, iii) T > n 1 (A * -1 ,C * ),where n 1 is the first index of controllability for the par (A * -1 ,C * ). 2. If det A -1 = 0, then assertion 1 is verified for the output y(t ) = C z(t ).V. EXAMPLESLet us give some simple examples to illustrate our results. Example 1. Consider the system ż(t ) = ż(t -1), where z(t ) ∈ R n , n > 1, with two possible outputs y 0 (t ) = C 0 x(t ) = z(t ), y 1 (t ) = C 1 x(t ) = z(t -1).

(θ) f ′ (θ) + A *

(θ) f (θ)dθ. Let A † be the generator of the semigroup e A † t generated by this equation (37). We cannot consider A * for this system