Iheb Ben Amor
email: iheb.ben-amor@etu.parisdescartes.fr

Mourad Ouziri

Soror Sahri

Naouel Karam
email: naouel.karam@fu-berlin.de

Be a Collaborator and a Competitor in Crowdsourcing System

Crowdsourcing is emerging as a powerful paradigm to solve a wide range of tedious and complex problems in various enterprise applications. It spawns the issue of finding the unknown collaborative and competitive group of solvers. The formation of collaborative team should provide the best solution and treat that solution as a trade secret avoiding data leak between competitive teams due to reward behind the outsourcing of the issue. The formation of effective competitive teams not only requires adequate skills between members of each team, but also good team connectivity through social network and to provide the best solution and treat that solution as a trade secret avoiding data leak between teams due to reward behind the outsourcing of the issue. In this paper, we propose a data leak aware crowdsourcing system called SocialCrowd. We introduce a clustering algorithm that uses social relationships between crowd workers to discover all possible teams while avoiding inter-team data leakage.

I. INTRODUCTION

A new trend of teamwork has been emerged unconstrained by local geography, available skill set, networking and deep relationships the crowdsourcing. It is the action of outsourcing tasks, traditionally performed by an employee or contractor, to an undefined group of people through an open call [START_REF] Brabham | Crowdsourcing as a model for problem solving: An introduction and cases[END_REF]. Crowdsourcing applications should be enable to seek for people crowd on demand to perform a wide range of complex and difficult tasks. Thousands human actors will provide their skills and capabilities in response to the call.

We introduce a type of crowdsourcing called SocialCrowd based on the efficiency of social network to outsource a task to be performed by people on demand instead of an open world as Mechanical Turk is doing. In fact, the interactions between people involved to answer a query become complex more and more and the collaboration leads to the emergence of social relations and a social network can be weaved for human-task environment.

The goal of SocialCrowd system is to let people collaborating on a joint task in the crowd environment where they may seek for other members towards social crowd relationships for achieving a business goal. Thus, many competitive teams can provide a set of answers to the call. However, as the crowd task is competitive between teams, it is important to group people in a manner there is no inter-teams leaking. Such mechanism will avoid the information leak between crowd people in different teams. Hence, the issues and challenges considered in our system, include:

(i) how to build up and discover teams answering the query towards the social relationships.

(ii) how to avoid the solution disclosure of the problem during the teams construction between competitive groups.

In fact, people on demand collaborating to a task may share sensitive information (part of the problem solution)that may be propagated or forwarded to other crowd members in the social network.

Few works dealing with crowdsourcing are provided. In [START_REF] Deutch | Using markov chain monte carlo to play trivia[END_REF], the Trivia Master system generates a very large Database of facts in a variety of topics, cleans it towards a game mechanism and uses it for question answering. In [START_REF] Skopik | Towards social crowd environments using serviceoriented architectures[END_REF] is proposed a novel approach for integrating human capabilities in crowd process flows.

In [START_REF] Michael | Crowddb: answering queries with crowdsourcing[END_REF]is introduced an answering queries with Crowdsourcing. The authors explain their challenges and present an initial solution to the problems of finding new data and comparing data. For this, they propose a simple SQL schema and query extensions that enable the integration of crowdsourced data and processing, they present also the design of croudDB including new crowdsourced query operators and plan generation techniques that combine crowdsourced and traditional query operators. After that, they describe methods for automatically generating effective user interfaces for crowdsourced tasks, and present the result of micro-benchmarks of performance of individual crowdsourced query operators on the ATM platform and demonstrate that CrowdDB in indeed able to answer queries that traditional DBMS cannot.

In [START_REF] Fang | A privacy recommendation wizard for users of social networking sites[END_REF] designed a wizard that may automatically configure a user's privacy settings with minimal effort from the user to aim policy preferences learning, to classify users and an automatic access rules affectation to new user. They developed a tool, an easy to use and provides very simple user interactions, it leveraging the machine learning paradigm of active learning, it interactively asks the user to assign privacy labels to specific, carefully selected, friends. As the user provides more input, the quality of the classifier improves.

[17] models the relationship strength in on-line social networks, the authors develop an unsupervised model to estimate relationship strength from interaction activity and user similarity. Them model can represent the full spectrum of relationship strength and propose an unsupervised method to infer a continuous-valued relation-ship strength links since the relationship strength directly impact the nature and frequency of on-line interactions between a pair of users so impact the privacy policies of each user.

In [START_REF] Talukder | Privometer: Privacy protection in social networks[END_REF], the authors introduced privacy protection tool that measures the amount of sensitive information leakage in a user profile and suggest self-sanitization action to regulate the amount of leakage. The protection tool determines the probability of individual sensitive attribute inference in a user profile based on her/his friendship relations and friend's attribute values.

In [START_REF] Carminati | Enforcing access control in web-based social networks[END_REF] has concluded the need of more flexible mechanisms of protection, making a user able to decide which network participants are authorized to access his/her resources and personal information to enforce privacy policies. Hence, they focused their work on relationship protection by proposing a strategy exploiting cryptographic techniques to enforce a selective dissemination of information concerning relationships across a social networks.

In [START_REF] Yan | Crowdsearch: Exploiting crowds for accurate real-time image search on mobile phones[END_REF] the authors introduce the problem of image search. Even when we have to deal with variations in lighting, texture, image quality, the search should be precise and return very few erroneous results. They wish to return one validate image before deadline, while minimizing the money. To do this, they propose a solution named CrowdSearch, in order to provide an accurate image search system for mobile devices by combining an automated Image search and then a human validation based on crowdsourcing that increases search result accuracy. The combination presents a complex set of trade-offs involving delay, accuracy and cost.

In [START_REF] Wang | Crowder: Crowdsourcing entity resolution[END_REF] they are interested in the problems of finding all duplicate records. They propose an hybrid human machine system for entity resolution. They uses machine based techniques to discard those pair of records that look very dissimilar and only asks the world to verify the remaining pairs which need human insight. They combine the efficiency of the machine based approaches with the answer quality obtained from people. They uses heuristics approach to fight against the problem of processing time.

In [START_REF] Demartini | Zencrowd: leveraging probabilistic reasoning and crowdsourcing techniques for large-scale entity linking[END_REF] are interested in the problems of linking entity from text to the linked open data cloud. They linked definitions to words in texts. To do this, they propose the ZenCrowd allowing linking definitions to words in texts. They combine both algorithmic and manual linking, automate manual linking via crowdsourcing and dynamically assess human workers with a probabilistic reasoning framework.

In [START_REF] Demartini | Crowdq: Crowdsourced query understanding[END_REF], the authors present an hybrid human machine pipeline, a novel system used for answering complex keyword queries. Using the crowd to understand the query (gain knowledge of query structure and entity relationships). They develop a new language to answer the queries.

[2] develops how to exploit the unique capabilities of the crowd to mine data from the crowd. They define a method of accessing personal databases based on association rules. The definitions of support and confidence are used as a measure for the significance of a rule per user.

The work in [START_REF] Djellel Eddine Difallah | Pick-a-crowd: tell me what you like, and i'll tell you what to do[END_REF] is based on the social networks where the proposed systems searches the most suitable worker to answer the task. It is proposed a model based on the workers' profiles using information on social network platforms. The authors developed a native Facebook application named Open Turk implementing tasks assignment.

In [START_REF] Basu | Optimization in knowledgeintensive crowdsourcing[END_REF] it is introduced the problem of the Interactive Crowdsourcing, they present the smartcrowd a framework for harnessing the crowd to approximate ground truth effectively and efficiently, while taking into account the innate uncertainty of human behavior. They formulate task assignment as an optimization problem, and rely on pre-indexing workers and maintain the indexes adaptively, in such a way that the task assignment process gets optimized both qualitatively, and computation time-wise. They present rigorous theoretical analyses of the optimization problem and propose optimal and approximation algorithms.

Privacy and data leaking are not at all discussed in these works.

Contributions:

We address the aforementioned challenges by proposing the SocialCrowd framework to discover competitive and collaborative composition teams answering the query through a social network while prohibit data leak between those teams.

The discovering method (DLTD) is a clustering algorithm to classify the potential crowd people from the social network that are close to collaborate in the same team. The system will not group them in the competitive clusters, thus, avoid inter-teams data leaking.

To handle such leak, the HDPD algorithm, a Markov chainbased algorithm, is proposed to discover the implicit social relationships between crowd people.

The rest of the paper is organized as follows: section 2 provides an overview of our SocialCrowd system. The propagation process is described in section 3. In section 4 is discussed the clustering based approach to discover competitive clusters in the social network answering a business call. We discuss our experiments in Section V.

II. SocialCrowd: AN OVERVIEW

The SocialCrowd architecture is composed of three main components as depicted in Fig. 1: In order to compose data leak free teams, the data propagation component computes the propagation of data in the social network. The component uses the collected (inputs) and shared (outputs) information of each social member. The proposed data propagation algorithm HDPD (High Data Propagation Discovery) deals with the dynamic aspects of the network.

Data Propagation Process(DPP)
It first computes the probabilities of data propagation from each member to direct friends in the social network. Then, it calculates data propagation probabilities from each member to indirect friends.It is a based Markov Chain model detailed in next section.

• Clustering component:

Given the data propagation probabilities provided in the previous step, the clustering component groups crowd workers1 into competing clusters (or teams) free of data leak. For that purpose, we define a distance to capture data leaks.

Crowd workers with higher propagation probability are part of the same cluster. The proposed clustering algorithm DLTD (Data Leak free Team Discovery) returns all potential data leak free teams. Details about the DLTD algorithm are given in Section IV.

• Team Constitution:

The module will constitute the different team based on the provided result from the clustering process (CP). It will use the user profile information provided from the social network. It will notify the users about the team discovering results.

III. A MARKOV CHAIN-BASED APPROACH FOR DATA

PROPAGATION

The aim of our approach is to build up teams from the social networks, all the while avoiding propagation of data between competitive clusters. For that, the clustering algorithm needs all the possible interactions between members of a social network.

A Social Network is set of direct relationships between members. These direct relationships allow us to compute the probability of data propagation (and consequently any data leak) between only direct friends. However, to discover competitive teams that are data leak aware, one needs to know all possible data propagations from friend-to-friend in the whole social network.

The Markov chain model is used, because

• in real world the data propagation depends only of the present state and not the past one.

• The discovering of the maximum data propagation between members is probabilistic.

The data share is an imminent information to identify competitive teams (by prohibiting leakage between discovered clusters) and collaborative teams (by ensuring that the members in the cluster interact well).

In real social network, data are shared from friend to friend and so on, so the friendship relation is a good indicator of data share in our case.

As example, the social network of Fig. 2 shows that Alice shares 90% of his data with Mickael. This rate is considered as probability of data propagations between direct friends noted by p (Alice,M ickael) = 0.9. However, the data propagation to indirect friends (to friends-of-friends) are implicit. They depend on data propagation probabilities between direct friends. In the Fig. 2, the probability of data propagation from Alice to indirect member David is computed by the expression:

p (Alice,David) = p (Alice,M ickael) × p (M ickael,David) = 0.9 × 0.5 = 0.45.
All the possible paths in the social network have to be explored to compute data propagation between two members. This is a hard computing task as real social networks are quite complex.

In this section, we present a Markov chain-based approach for handling the implicit/indirect relations between members. We present a model and an algorithm of data propagation across the entire social network.

A. A graph-based model of data sharing relationships

In this paper, we model the relationships in the social network without focusing on their nature (e.g., friendship, sharing, etc.). We only need to reason on the quantity of data propagated between members in the social network. Thus, We model the network as a labeled directed graph G M, A, P where :

• M = {m i }: set of nodes where each node represents a social network member.

• A = {a ij = (m i , m j )/(m i , m j ) ∈ M }: set of edges where each edge represents a relationship between two members.

• P = {p ij /∀i, j p ij ∈ [0, 1]}: is a set of labels where each label p ij of the edge a ij represents the rate/probability of data shared by the member m i ∈ M with his friend member m j ∈ M .

In the given graph model, the friend relationship is represented using edge A labeled with the real probability of shared data P . We calculate the probability p ij that the member m i shares his data with member m j by the simple formula:

p ij =
quantity of data that mi shared with mj quantity of data held by mi where we consider the data held by the member m i as only the data that m i received from other direct members in the social network. For instance in Fig. 2, the arc (Alice, M ickael) indicates that Alice has a relationship with M ickael, and shares with him 90% of his data and the arc (Alice, George) indicates that Alice has a relationship with George but she never shares any data with him.

In the following, we present the Markov propagation model to compute the implicit probability of data propagation between indirect friends (e.g., the propagation probability from Alice to David in Fig. 2 ).

B. Markov chain-based model for data propagation

Given an owned data of a known member, the aim of this section is to compute the propagation probabilities to all the possible members of the social network. The premise is that in social networks data is propagated from one friend to another and so on. This observation about propagation of owned data from friend to friend corresponds to the well known Markov chain [START_REF] Hggstrm | Finite markov chains and algorithmic applications[END_REF].

Definition 1: (Markov chain)

A Markov chain is a sequence of random variables X 1 , ..., X n with the Markov property; that the future state depends only on the the present state, and not on the past states. Formally,

P (X n+1 = x|X 1 = x 1 , X 2 = x 2 , . . . , X n = x n ) = P (X n+1 = x|X n = x n )
From this formal definition, the probability that a given member gets some data depends on the probability to get it from only his direct friends (and not from indirect friends).

We represent the probability of data propagation between direct friends as a Propagation Matrix (defined as follows).

Definition 2: (Propagation matrix)

The Propagation Matrix of a social network G M, A, P is a matrix that gives the probability p ij of propagating data between each couple of friend members (m i , m j ), where

p ij =  
 quantity of data that mi shared with mj quantity of data held by mi

if (m i , m j ) ∈ A 1 for i = j 0 else
This propagation matrix has the following properties:

• p ii = 1 means that member m i does not lose the owned due to sharing.

• k∈ [1,n] (p ik ) = 1, as data may be propagated to several members at the same time.

• p ij = p ji , which means that a member m i may share data with a friend m j in a quantity that is different from what his friend m j may share with him.

• (m i , m j ) ∈ A p ij = 0, which means that members do not necessarily share their data with their friends.

• (m i , m j ) / ∈ A ⇒ p ij = 0, to express that data propagation to indirect friends in the social network is unknown.

Based on the above mentioned definitions, the propagation matrix of the social network of Fig. 2 is given as follows:

       Bob Alice John David M ickael George Bob 1 0 0 0.1 0.1 0.7 Alice 0 1 0 0 0.9 0 John 0 0 1 0.2 0 0 David 0 0 0.2 1 0, 5 0 M ickael 0 0.9 0.3 0.5 1 0.2 George 0.7 0.3 0.1 0 0 1       

C. A Markov chain-based algorithm of data propagation

The propagation matrix of Section III-A gives only the probability of data propagation between direct friends. But the matrix is not sufficient to compute the probability that data is propagated from one member to other indirect-friend(s) because:

1) The propagation probability between direct friends is not optimal. Following different paths in the graph of the social network, we can calculate different probabilities of propagating data between two members.

In Fig. 2, the direct friend relationship from Alice to George indicates that Alice's data is not propagated to George as p (Alice,George) = 0. However, through M ickael, Alice's data may be propagated to George with probability 0.9 × 0.2 = 0.18.

2) Propagation to indirect-friends is not given in the propagation matrix and is set to zero. The probability of sharing data with indirect friends is zero in the propagation matrix because members share their data only with direct friends. However, data may be propagated from direct friends to indirect-friends.

In the propagation matrix corresponding to Fig. 2, probability that George's data will be propagated to indirect-friend David is zero because George is not a direct friend. However, George's data may be propagated to David through Bob with probability 0.7 × 0.1 = 0.07.

3) Computing propagation to indirect-friends is hard.

The probability that Alice's data may be propagated to David (probability of dotted red arrow in Fig. 2) is hard to compute because it requires exploring all the propagation paths from Alice to David (dotted green arrows in Fig. 2 -although the graph of Fig. 2 is small, there are seven paths).

All the possible paths in the social network have to be explored to compute data propagation between two members. This process is not straight-forward as real social networks are quite complex.

In this regard, we propose an algorithm to calculate the optimal probability of data propagation from a given member to all the members of the social network. This algorithm is based on an energy function we define as follows:

Definition 3: (Energy function)
The energy function p i is the probability that data is propagated to the member m i . Since in our model data is propagated following a Markov chain:

p i = M ax m k ∈Nm i (p k × p ki ) (1)
where, N mi is a set of direct friends of m i , p k is the energy function of m k and p ki is the probability of propagating data from m k to m i .

The maximum function is the suitable aggregation function as the aim of the approach is to estimate the maximum risk of data propagation. The aim is to compute the data probability propagation p ij and p ji of all the pairs of members (m i , m j ). This requires the use of an iterative algorithm. The proposed HDPD algorithm computes the optimal energy functions P o * = (p o1 , p o2 , ..., p on ), which represent probabilities of data propagation from the member m o to members {m i } i∈ [1,n] . It processes as follows:

• Initialisation:p owner = 1, ∀i = owner p i = 0. That is only the owner has the data.

• Iterations: At each iteration, the algorithm computes p i for m i ∈ N mi using the energy function.

• Stops: The algorithm stops when the maximum probability of each member is reached.

The algorithm is recursive, the complexity of the algorithm is the main call. Given, n the number of registered members, m the number of relations and f (n) the main call propagation function complexity. This function is composed of a test of complexity O (n) and it makes n recursive call. Then, the complexity of this function is : O(n * m) × n.

Our algorithm is presented as follows:

Algorithm for each members m i = m o do 8:

ps i = M ax m k ∈Nm i (p k × p ki )) 9:
end for 10:

if P = PS then 11: This graph shows that:

p i ← M ax (ps i , p i ) 12:
• For indirect friend relationships such as (Alice, David) and (Alice, John), the algorithm calculated data propagation probabilities that do not exist in the initial graph of Fig. 2.

• For some direct friend relationships such as (Alice, George) and (Bob, M ickael), the algorithm updates the data propagation probabilities from 0 and 0.1 to the optimal values 0.18 and 0.19 respectively. These optimal probabilities are calculated using the paths (Alice, M ickael, George) and (Bob, George, Alice, M ickael), respectively.

IV. DATA LEAK AWARE CLUSTERING

In this section, we provide details on the clustering process that groups crowd members into data leak free clusters, based on the data propagation technique defined in the previous section. In order, to give chance to every registered member in the competition, the clustering process discover all possible solutions including each member only to one cluster. In contrast to existing clustering algorithms (such as k-means [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] and our previous presented algorithm [START_REF] Ben Amor | Data leak aware crowdsourcing in social network[END_REF]) that generate a single clustering solution, our proposed approach generates all possible clustering solutions while preserving their respective data.

Before presenting the algorithm details, we give the following definitions:

∀m i ∈ C k , ∀m j ∈ C s , p ij ≤ η ∧ p ji ≤ η
In definition 5, we consider there is a risk of data leak between two clusters C k and C s if the propagation rate between all the members of the two clusters is less than a threshold η. The clustering algorithm uses the following definition (of distance) to generate data leak free clusters:

Definition 6: (Distance)
The data propagation between a member m i and a cluster C k is measured by the distance Ω(C k , m i ), defined as follows :

Ω(C k , m i ) = M ax mj ∈C k p ij
It follows from definitions 5 and 6 that there is a data leak from a cluster C k to member m i if: Ω(C k , m i ) > η. Note that a solution is incomplete if it does not contain all the members, and complete otherwise.

Using definition 5, we transform the propagation matrix, computed by the HDPD algorithm, into a symmetric matrix as follows: ∀i, j, p ij = M ax(p ij , p ji )

The propagation matrix will be modified such as considering now an undirected graph and update the relationships between two users with the high value of their propagation. The maximum will be the criteria used to avoid data leaking between clusters.

As mentioned earlier, the Data Leak free Team Discovery algorithm (DLTD) will generate all the possible clustering solutions based on the defined symmetric matrix. The processes are as follows: Initialization:

• A random member m 0 is selected, and made the member of a new cluster

C 1 . That is, C 1 = {m 0 } • The initial partial solution is created as S 1 = {C 1 }.
Using the partial solution(s) S i = {C 1 , ..., C n } n≥1 (i is the number of clustered members in S i ), the algorithm clusters a new member m i according to the following rules:

Rule 1: If m i has data leak with only one cluster C k in S i (i.e., ∃C k ∈ S i Ω(C k , m i ) > η and ∀C jj =k ∈ S i , Ω(C j , m i ) ≤ η), then the member m i is clustered into C k . The partial solution S i is increased to S i+1 such that S i+1 = S i where C k = C k ∪ {m i }.
Rule 2: If m i has no data leak with any cluster in S i (i.e., ∀C j ∈ S i , Ω(C j , m i ) > η), then the member is clustered in each cluster while creating a new solution for each instance.

That is, S i increases to n possible partial solutions

S α i+1 : S α i+1 = S i ∪ {C α } where C α = C α ∪ {m i } for α ∈ [1, n].
Rule 3: If m i has data leak with two or more clusters in S i , i.e., for

SC i in S i , SC i = {C 1 , ...C k } 2≤k≤n such that ∀C j ∈ SC i , Ω(C j , m i ) > η,
S 2 i+1 = S i C g call FreeLeakClustering(S 2 i+1 , M -m i ); end if
As example, Fig. 4 shows the resolution graph generated by DLTD clustering algorithm when running on the graph of Fig. 2. Internal nodes (S * i , i ≤ 5) are partial solutions and leaf nodes (S * 6 ) are final solutions as all members are clustered (there are 6 members to be clustered for this example).

The graph shows five solutions of clustering. In each solution, members of the social network are grouped into data leak free clusters, which can be easily checked using symmetric propagation matrix given at the beginning of this section. The algorithm is recursive and consists of three main rules: Rule 1, Rule 2 and Rule 3. The complexity of the algorithm is the main call. Given, n the number of members to be classified, and f (n) the main call clustering function complexity. Then, the complexity of this rule is :

Then, f (n) = M ax(O(Rule1(n)), O(Rules2(n)), O(Rule3(n)).
O(n) + O(f (n -1)) = n + (n -1) + O(f (n -2)) = n + (n -1) + . . . + O(1) = O(n 2 ).
2) Complexity of rule 2 : This rule makes k recursive call where k is the number of clusters in a solution.

Then, the complexity of this rule is :

O(n)+k ×O(f (n-1)) = n+k ×(k -1)×. . .×1 = O(n + k!).
If we consider the theoretical worst case k = n, then complexity of rule 2 is O(n!).

3) Complexity of rule 3 : This rule is composed of a test of complexity O (n), and two recursive calls.

Then, the complexity of this rule is:

O(n)+2×O(f (n-1)) = n+2(n-1)+O(f (n-2)) = n + 2(n -1) + . . . + 2 = O(n 2 ).
Hence, the overall complexity of the algorithm is O(n!). This is a theoretical complexity in the worst case. In practice, the number of clusters k are usually much smaller than n.

V. EXPERIMENTS

The experiment environment consists of a Mac OS X 10.5.8 machine with a 2.13 GHz Intel Core 2 Duo processor, and 2 GB of ram.

Coding is JAVA-based, and we have followed Metcalfe's law2 for creating the social network.

Metcalfe's law characterizes many of the network effects of communication technologies and networks such as the Internet, social networking, and the World Wide Web. Former Chairman of the U.S. Federal Communications Commission, Reed Hundt, said that this law gives the most understanding to the workings of the Internet.

Metcalfe's Law is related to the fact that the number of unique connections in a network of a number of nodes (n) can be expressed mathematically as the triangular number n(n -1)/2, which is proportional to n2 asymptotically.

The law is abundant and existent due to the ability of Internet users to link together. Websites and blogs such as Twitter, Facebook, and Myspace are the center of this law taking effect.

We conduct experiments on effectiveness of the proposed approach in terms of data leak comparing to K-means. K-means clustering is a well known partitioning method. In this objects are classified as belonging to one of K-groups.

The results of partitioning method are a set of K clusters, each object of data set belonging to one cluster. In each cluster there may be a centroid or a cluster representative.

A. k-means and DLTD clustering based on Ω

We present the evaluation of the proposed DLTD algorithm and compare it to the k-means clustering algorithm, based on the Ω distance.

The data leakage is calculated based on the results returned by the two algorithms. We explored each cluster in order to identify the data propagation upper than η between two members in different clusters. To do this, we developed a script computing the leakage after the classification step.

The results are depicted in Fig. 5 (where the leakage threshold (η) is set to 40%). The figure shows that with the DLTD algorithm, the clusters are free data leak, even if, the size of the social network increases. These results are sound because the algorithm groups members leading to the data leak in the same group. In contrast, the k-means algorithm results in a higher percentage of data leaks with increasing social network size. This result is valid with varying number of clusters (k).

For instance, with 20 clusters we can see that data leak increases from 2.9% to 4.4% when the size of the social network grows from 500 to 5000 members. These results confirm that the k-means algorithm is not a good solution for handling data leaks in social networks.

In fact, even if there is high data propagation between two network members, the k-means algorithm may cluster them into different clusters due to their respective closeness in terms of the used distance.

B. Execution time comparison

We analysed the execution time of both DLTD en Kmeans algorithm using Ω distance. The analysis uses between 1000 and 5000 users. We computed the execution time of around 12497500 relationships in social network. We note that, the DLTD algorithm has no data leakage, however, its computational time is upper than the K-means.

In the figure 6, the execution time is between 153 and 1653 seconds for the k-means algorithm and it's between 172 and 2631 for the DLTD. Then, the K-means algorithm is better than the DLTD in computational time. The execution time of the DLTD algorithm is important than the K-means, because, the DLTD discover all possible clustering solutions, or the K-means discover only one.

Furthermore, the k-means results represent an important data leakage (data propagation upper than η) between the different clusters while using Ω distance, because, the classification mechanism group members in the nearest cluster. This means that, k-means classify the member to the cluster with which he has the highest data propagation, even if, he has other propagations upper than the threshold with other clusters.

The execution time of the k-means algorithm is caused by the convergence process. The k-means repeating the same classification phase until convergence. The number of repetition is variable, in our case, it depends on the number of members and their propagation to classify data.

The convergence of k-means is reached when comparing the last two iterations shows that members no longer move between teams, then, the calculation of the k-means reaches its stability and no iteration is required. In addition, the convergence to a local minimum can produce a bad result.

The convergence criterion of DLTD algorithm is reached when there is no crowd member to classify.

C. Solution generation scalability

In this experiment, we shows that the DLTD algorithm returns different solutions generation depending on the number of registered member and the data propagation values and not depending on social network size.

The figure displays that more the of registered member grows more the number of generated solutions increases except from 1500 to 2000 members, because, members that has a data propagation upper than the threshold with two or more clusters generates merging those clusters. Hence, there will be less solutions. Using the same social network architecture and evolving the number of registered member, the fig 7 shows that, with 500 registered member, the DLTD algorithm return around 33 possible solutions, and for 3000 members the algorithm generate around 125 solutions.

VI. CONCLUSION AND FUTURE WORK

In this paper, we proposed a data leak aware crowdsourcing system providing a collaborative environment between crowdexperts organized in various teams that compete against each other to achieve certain tasks. The system prevents data leaks between teams to protect each team competitive advantage.

For that, we designed a clustering algorithm that discovers all possible teams of crowd workers while minimizing data leakage. Where the leakage is expressed by propagation of data between crowd workers via social relationships. However, the theoretical complexity of the clustering algorithm is hard. To face with this complexity, we plan to improve algorithm by adding heuristics.

Fig. 1 .

 1 Fig. 1. SocialCrowd architecture

Fig. 2 .

 2 Fig. 2. A simple data propagation

  end while 16: return P Running the algorithm on the propagation matrix of previous subsection III-B results in the following graph (but only some links are shown for readability):

Fig. 3 .

 3 Fig. 3. Data propagation graph with implicit relationships

Definition 4 :

 4 (Cluster) A cluster C is set of crowd members (having propagation, or no strong propagation): C = {m i } such that ∀m i , m j ∈ C, p ij ∈ [0, 1], p ji ∈ [0, 1] Definition 5: (Data leak free clusters) Two clusters C k and C s are data leak free iff:

Definition 7 :

 7 (Clustering solution) A solution S = {C 1 , ..., C n } n≥1 is set of clusters such that: ∀i, j ∈ [1, n] C i and C j are data leak free.

then there are two possible solutions (S 1 i+1 and S 2 i+1 ): ( 1 ) 1 i+1( 2 )

 112 Merge the clusters {C 1 , ...C k } and m i into one cluster i=1,k C i ∪ {m i } and The partial solution S i is increased to S Compute the subset L ⊆ Ci∈SCi C i such that members of L ∪ {m i } have direct or indirect data leak between them and Create a new cluster C g = L∪{m i } and remove members of L from their respective cluster finally the partial solution S i increased to S 2 i+1 S 2 i+1 = S i ∪ {C g }. The DLTD clustering algorithm applies the above mentioned defined rules until all members are clustered in all possible solutions. The algorithm is traced as follows: Algorithm 2 DATA LEAK FREE TEAM DISCOVERY Input: The symmetric propagation matrix, M : set of all crowd members to be clustered. Output: All possible solutions S i of data free clustering. {I}nitializations randomly select m 0 from M; create the cluster C 1 = m 0 ; S 1 = C 1 call FreeLeakClustering (S

Fig. 4 .

 4 Fig. 4. Resolution graph generated by the clustering algorithm

1 )

 1 Complexity of rule 1 : This rule is composed of a test of complexity O(n), and a recursive call.

  Fig. 5. Leakage comparison

Fig. 6 .

 6 Fig. 6. DLTD and K-means execution time

Fig. 7 .

 7 Fig. 7. Solution generation scalability

  1 HIGH DATA PROPAGATION DISCOVERY (HDPD) Require: G M, A, P M -labeled directed graph of the social network where P M is the propagation matrix m o -owner of the data Ensure: P -all the implicit data propagation from m o 1: P = (p 1 , . . . , p o , . . . , p n ) -Energy function at the current step. 2: PS = (ps 1 , . . . , ps o , . . . , ps n ) -Energy function at the next step. 3: continue: boolean value indicating if the optimal probabilities are reached. {I}nitializations 4: p o = 1 and ∀i = o, p i = 0 5: continue ← true {I}terations 6: while continue do

	7:

  1 , M -m 0 ); Clustering function Function FreeLeakClustering(Solution S i , Members M); if M = ∅ then Return S i ; \S i is a final solution as there are no remaining members to cluster end if if Rule1: m i has data leak with only one clusterC k in S i then C k = C k ∪ m i S j i+1 = S i call FreeLeakClustering(S i+1 , M -m i ); end if if Rule2: m i has no data leak with any cluster in S i then for each cluster C j in S i do C j = C j ∪ m i Rule3: m i has data leak with two or more cluster SC i in S i , SC i = C 1 , . . . , C k2≤k≤n ⊆ S i then \ First alternative solution Merge all the clusters of SC i with m i into the new cluster C g . that is,C g = C 1 ∪ . . . ∪ C k ∪ m i ; call FreeLeakClustering(S 1 i+1 , M -m i ); \ Second alternative solution compute the subset L ⊆ Ci ∈ SC i C i ofmembers having direct or indirect data leak between them 'see Rule3.2); Create a new cluster C g = L m i ; for m j in L do Delete m j from its cluster in S i ; end for

	S j i+1 = S i call FreeLeakClustering(S j i+1 , M -m i ); end for
	end if
	if

In the rest of the paper, we use the terms "member" and "crowd worker" interchangeably.

Bob Metcalfe, personal communication, June 2007.


Iheb Ben Amor
email: iheb.ben-amor@etu.parisdescartes.fr

Salima Benbernou

Mourad Ouziri

Tell me what you Need, I Can Manage the Competition in Crowdsourcing systems

Keywords: Crowdsourcing, Social network, privacy

Crowdsourcing is a practice of allowing enterprise to use the creativity and the imagination of Internet users to provide a solution of an issue i.e. web content. However, the task to be accomplished is more and more complex and therefore it needs to find unknown collaborative and competitive group of solvers. In this paper,we propose a crowdsourcing system called SocialCrowd allowing the composition of collaborative team that should provide the best solution and treat that solution as a trade secret avoiding data leak between competitive teams due to reward behind the outsourcing of the complex task

INTRODUCTION

Crowdsourcing is emerging as a powerful paradigm in human problem solving techniques to the Open World. It helps to solve a wide range of tedious and complex problems in various enterprise applications. It allows enterprise to use the creativity and the imagination of Internet users to provide a solution for an issue. We introduce a type of crowdsourcing called Socialcrowd based on the efficiency of social network to outsource a task to be performed by people on demand on the social/professional network instead of an open world as Mechanical Turk is doing. As related work one can cite [START_REF] Davidson | Using the crowd for top-k and group-by queries[END_REF] which studies the max/top-k and grouping database problems in the crowd sourcing setting. where the criteria used for grouping and ordering are difficult to evaluate by machines but much easier to evaluate by the crowd. In [START_REF] Amor | Data leak aware crowdsourcing in social network[END_REF], we developed an approach discovering hidden relationships between crowd members in social network and building only one team that may solve the outsourced problem, in [START_REF] Amor | Be a collaborator and a competitor in crowdsourcing system[END_REF], we extended our previous work in order to discover a set of collaborative et competitive team compositions answering the business call. In this paper we propose to discuss a data leak free team composition method which is based on heuristics.

SOCIALCROWD: AN OVERVIEW

The SocialCrowd architecture is composed of three main components as depicted in Fig. 1: • PMTD Clustering Model: To discover competitive and collaborative teams, we provide PMTD algorithm based on a specific distance representing the propagation for clustering crowd workers that capture data leaks.

Propagation Model Best Solution

PMTD Clustering Model

• Ranking Solutions Model: Based on the possible team compositions provided by the PMTD model, this module will use the requester preferences to choose the best solution, it will combine the preferences in order to find the solutions that satisfy the majority of them.

PROBABILISTIC METAHEURISTIC BASED TEAM COMPOSITION

In this section we introduce our approach SocialCrowd by detailing the Data propagation component and the PMTD Clustering Model.

A Markov chain-based approach for data propagation

We propose an algorithm to calculate the optimal probability of data propagation from a given member to all the members of the social network in order to capture the possible data leak between crowd members. This algorithm is based on an energy function we define as follows:

Definition 1. (Energy function). The energy function pi is the probability that data is propagated to the member mi. Since in our model data is propagated following a Markov chain:pi = M ax

m k ∈Nm i (p k × p ki ),
where, Nm i is a set of direct friends of mi, p k is the energy function of m k and p ki is the probability of propagating data from m k to mi.

The maximum function is the suitable aggregation function as the purpose of the approach is to estimate the maximum risk of data propagation. The aim is to compute the data probability propagation pij and pji of all the pairs of members (mi, mj). The proposed algorithm computes the optimal energy functions Po * = (po1, po2, ..., pon), which represent probabilities of data propagation from the member mo to members {mi} i∈ [1,n] . It processes as follows:

• Initialisation:powner = 1, ∀i = owner pi = 0. That is only the owner has the data.

• Iterations: At each iteration, the algorithm computes pi for mi ∈ Nm i using the energy function.

• Stops: The algorithm stops when the maximum probability of each member is reached.

Data leak aware heuristic-based composition

The composition model is based on data propagation technique defined in the previous section. In contrast to existing clustering algorithms (such as k-means [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] which generates a single clustering solution, our proposed approach generates all possible compostion solutions while preserving their respective data. As this is a hard problem, we use the Simulated annealing (SA) algorithm to compute near optimal solutions within a reasonable computation time [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]. The PMTD starts at a high temperature T0 and the temperature is slightly lowered under a certain mechanism which is called cooling schedule when the procedure proceeds. In this paper, we use the exponential cooling schedule,ti = α × ti-1 ,where α ∈ (0, 1) is the temperature decreasing rate. The fundamental idea is to generate a new user sequence λ a random rule from the neighbourhood of incumbent sequence x.

The new solution λ is assessed by a mechanism called acceptance criterion to decide whether accept the λ or reject it. The neighbourhood generating function provide new solutions neighbour to the latest accepted solution. The main core of the function is to check the admissibility of the new neighbour solution by checking it's occurrence and validate that is respecting hard preferences of the caller, that means, the mandatory criterion of the solution accepted by the requester. As mentioned before, in the single-objective SA, the variation is calculated ∆C = f (λ)f (x). If ∆C ≤ 0, solution λ is accepted. Otherwise, solution λ is accepted with a probability equal to Pr = exp {-∆C ÷ ti} . Last but not least, ti an operator is employed to generate a neighbour solution λ from the current candidate solution x by making a slight change in it. This operator performs so as to avoid producing infeasible solutions. In this paper, we take into consideration three different move operators :Swap,Single relocation or New Team creation.The objective function of the PMTD algorithm is based on the privacy, the homogeneous competency and promoting teamwork. T (Φ) = V ar(Connected M ember in each team) + V ar(Competency) + P rivacy Computation

SOLUTION RANKING

According to the large number of solutions returned by the PMTD algorithm, in this section, we use Soft Constraint Satisfaction Problem (SCSP) to rank the provided solutions using preferences. In order to answer a crowdsourcing request, the clustering operations to discover teams aware dara leak may give many solutions that fulfil the privacy conditions. In this case, we integrate the preferences of the requester (how launched the call) to choose the suitable solution based on the privacy criterion and the preferences. Let CS = S, D, V be a constraint system and P = def, con be the problem to be resolved, where V = con = {TeamPropagationThreshold (tpt), TeamSnPropagation (tsp), ExpertLevel (el), Competency (com)}, D = {{tpt1, tpt2, tpt3, tpt4}, {tsp1, tsp2, tsp3, tsp4}, {el1, el2, el3, el4}, {com1, com2, com3}}, Sp = [0, 1] , max, min, 0, 1 , C = c1, c2, c3, c4}. For simplicity, variables and their domains have been written in the same order. The solution with highest rank is chosen first.

Figure 1 :

 1 Figure 1: SocialCrowd architecture

CONCLUSIONS

In this paper, we discussed the data propagation approach for the problem of friendship propagation of crowd members in social/professional networks. We also proposed a composition algorithm using simulated annealing heuristic model for team discovering process while avoiding data leaks between composed teams.


Christine Bernardi

JAD DAKROUB † ‡ , GIHANE MANSOUR ‡ Toni Sayah

A POSTERIORI ANALYSIS OF AN ITERATIVE ALGORITHM FOR NAVIER-STOKES PROBLEM

Keywords: A posteriori error estimation, Navier-Stokes problem, iterative method

This work deals with a posteriori error estimates for the Navier-Stokes equations. We propose a finite element discretization relying on the Galerkin method and we solve the discrete problem using an iterative method. Two sources of error appear, the discretization error and the linearization error. Balancing these two errors is very important to avoid performing an excessive number of iterations. Several numerical tests are provided to evaluate the efficiency of our indicators.

Introduction

The a posteriori analysis controls the overall discretization error of a problem by providing error indicators easy to compute. Once these error indicators are constructed, we prove their efficiency by bounding each indicator by the local error. This analysis was first introduced by I. Babuška [START_REF] Babuška | Error estimates for adaptive finite element computations[END_REF], and developed by R. Verfürth [START_REF] Verfürth | A Posteriori Error Estimation Techniques For Finite Element Methods[END_REF]. The present work investigates a posteriori error estimates of the finite element discretization of the Navier-Stokes equations in polygonal domains. In fact, many works have been carried out in this field. In [START_REF] Bernardi | A finite element discretization of the three-dimensional Navier-Stokes equations with mixed boundary conditions[END_REF], C. Bernardi, F. Hecht and R. Verfürth considered a variational formulation of the three-dimensional Navier-Stokes equations with mixed boundary conditions and they proved that it admits a solution if the domain satisfies a suitable regularity assumption. In addition, they established the a priori and the a posteriori error estimates. As well, in [START_REF] Ervin | A posteriori error estimators for a two-level finite element method for the Navier-Stokes equations[END_REF], V. Ervin, W. Layton and J. Maubach present locally calculable a posteriori error estimators for the basic two-level discretization of the Navier-Stokes equations. In this work, we propose a finite element discretization of the Navier-Stokes equations relying on the Galerkin method. In order to solve the discrete problem we propose an iterative method. Therefore two sources of error appear, due to the discretization and the algorithm. Balancing these two errors leads to important computational savings. We apply this strategy on the following Navier-Stokes equations:

Let Ω be a connected open domain in IR d , d = 2, 3, with a Lipschitz continuous boundary ∂Ω. We consider, for a positive constant viscosity ν, the following system:

-ν∆u + (u.∇)u + ∇p = f in Ω div u = 0 in Ω u = 0 on ∂Ω, (1.1)
where the unknowns are the velocity u and the pressure p of the fluid. The right-hand side f belongs to H -1 (Ω) d , the dual of the Sobolev space H 1 0 (Ω) d . Using P 1 Lagrange finite elements for the pressure and P 1 -bubble Lagrange finite elements for the velocity, the discrete variational problem amounts to a system of nonlinear equations. In order to solve it we propose an iterative algorithm which consists at each iteration to solve a linearized problem. We establish the corresponding a posteriori error estimates. Thus, two sources of error appear, namely linearization and discretization. The main goal of this work is to balance these two sources of error. In fact, if the September 10, 2014. † CNRS, UMR 7598, Laboratoire Jacques-Louis Lions, F-75005, Paris, France Sorbonne Universits, UPMC Univ Paris 06, UMR 7598, Laboratoire Jacques-Louis Lions, F-75005, Paris, France ‡ Unité de recherche EGFEM, Faculté des sciences, Université Saint-Joseph, Lebanon. bernardi@ann.jussieu.fr, jad.dakroub@usj.edu.lb, gihane.mansour@usj.edu.lb, toni.sayah@usj.edu.lb. discretization error dominates then the nonlinear solver iterations are reduced. Therefore, our objective is to calculate a posteriori error estimates distinguishing linearization and discretization errors in the context of an adaptive procedure. This type of analysis was introduced by A.-L. Chaillou and M. Suri [START_REF] Chaillou | Computable error estimators for the approximation of nonlinear problems by linearized models[END_REF][START_REF] Chaillou | A posteriori estimation of the linearization error for strongly monotone nonlinear operators[END_REF] for a general class of problems characterized by strongly monotone operators. It had been developed by L. El Alaoui, A. Ern and M. Vohralík [START_REF] Alaoui | Guaranteed and robust a posteriori error estimate and balancing discretization and linearization errors for monotone non linear problems[END_REF] for a class of second-order monotone quasi-linear diffusion-type problems approximated by piecewise affine, continuous finite elements.

In this work we present a strategy for the linearization process. This strategy is iterative and can be outlined as follows:

(1) On the given mesh, perform an iterative linearization until a stopping criterion is satisfied.

(2) If the error is less than the desired precision, then stop, else refine the mesh adaptively and go to step [START_REF] Adams | Sobolev Spaces[END_REF].

An outline of the paper is as follows. In Section 2, we present the variational formulation of Navier-Stokes problem (1.1). We introduce in Section 3 the discrete variational problem with the a priori error estimate. The a posteriori analysis of the discretization of the iterative algorithm is performed in Section 4. Section 5 is devoted to the numerical experiments.

Analysis of Navier-Stokes equations

We describe in this section the Navier-Stokes problem (1.1) together with its variational formulation. First of all, we recall the main notion and results which we use later on. For the domain Ω, denote by L p (Ω) the space of measurable functions v such that |v| p is integrable. For v ∈ L p (Ω), the norm is defined by

v L p (Ω) = Ω |v(x)| p dx 1/p .
Throughout this paper, we constantly use the classical Sobolev space

W m,r (Ω) = v ∈ L r (Ω); ∀|k| ≤ m, ∂ k v ∈ L r (Ω) ,
where k = (k 1 , ..., k d ) is a d-tuple of positive integers such that |k| = k 1 + ... + k d and

∂ k v = ∂ |k| v ∂x k1 1 ...∂x k d d . W m,r (Ω) is equipped with the semi-norm |v| m,r,Ω =   |k|=m Ω |∂ k v| r dx   1/r
, and the norm

v m,r,Ω = m ℓ=0 |v| r ℓ,r,Ω dx 1/r
.

For r = 2, we define the Hilbert space H m (Ω) = W m,2 (Ω). In particular, we consider the following space

X = H 1 0 (Ω) d = v ∈ H 1 (Ω) d , v | ∂Ω = 0 ,
and its dual space

H -1 (Ω) d .
We denote by L 2 0 (Ω) the space of functions in L 2 (Ω) with zero mean-value on Ω.

M = L 2 0 (Ω) = q ∈ L 2 (Ω); Ω q dx = 0 .
We recall the Sobolev imbeddings (see Adams [START_REF] Adams | Sobolev Spaces[END_REF], Chapter 3).

Lemma 2.1. For all j ≤ 6 and d = 2, 3, there exists a positive constant S j such that

∀v ∈ H 1 0 (Ω), v L j (Ω) ≤ S j |v| 1,Ω . (2.1)
We now assume that the data f belongs to H -1 (Ω) d . Then system (1.1) is equivalent to the following variational problem:

Find u ∈ X, p ∈ M such that ∀v ∈ X, a(u, v) + c(u; u, v) + b(v, p) = f, v , ∀q ∈ M, b(u, q) = 0, (2.2)
where the bilinear forms a(., .) and b(., .) and the trilinear form c(., ., .) are defined by

a(u, v) = ν Ω ∇u∇v dx, b(v, q) = - Ω q div v dx, c(w; u, v) = Ω (w.∇)uv dx.
(2.3) Furthermore, the bilinear form b(., .) satisfies the following inf-sup condition (see [START_REF] Girault | Finite Element Methods for Navier-Stokes Equations[END_REF], Chapter I, Equation (5.14) for instance)

inf q∈M,q =0 sup v∈X b(v, q) v X q M = β > 0. (2.4)
Now we recall the following space

V = v ∈ X; div v = 0 .
Then, problem (2.2) has the following form:

Find u ∈ V such that ∀v ∈ V, ν Ω ∇u∇vdx + Ω (u.∇)uvdx = f, v . (2.5)
The existence and the conditional uniqueness of the solution (u, p) of problem (2.2) is given in [START_REF] Girault | Finite Element Methods for Navier-Stokes Equations[END_REF] (Chapter IV, Section 2).

In order to calculate the a posteriori error estimate, we introduce the Stokes equations which are defined as follows:

-ν∆u + ∇p = f in Ω div u = 0 in Ω u = 0 on ∂Ω.
(2.6)

Using the previous notation, the Stokes problem amounts to the following variational form:

Find u ∈ X, p ∈ M such that ∀v ∈ X, a(u, v) + b(v, p) = f, v , ∀q ∈ M, b(u, q) = 0. (2.7)
The existence and the uniqueness of the solution (u, p) ∈ X × M of problem (2.7) is given in [START_REF] Girault | Finite Element Methods for Navier-Stokes Equations[END_REF], Chapter I, Section 5.1.

Remark 2.2. In the sequel, we denote by C, a generic constant that can vary from line to line but is always independent of all discretization parameters.

In what follows, for simplicity reasons, we suppose d = 2. In fact, the end of this work can easily be extended to d = 3 but requires some more technicalities that we prefer to avoid here.

Finite element discretization and the a priori estimate

This section collects some useful notation concerning the discrete setting and the a priori estimate.

Let (T h ) h be a regular family of triangulations of the polygonal domain Ω, in the sense that, for each h:

• The union of all elements of T h is equal to Ω.

• The intersection of two different elements of T h , if not empty, is a vertex or a whole edge of both triangles.

• The ratio of the diameter h K of any element K of T h to the diameter of its inscribed circle is smaller than a constant independent of h.

As usual, h stands for the maximum of the diameters h K , K ∈ T h .

Let (X h , M h ) be the couple of discrete spaces corresponding to (X, M ) defined as follow :

M h = q h ∈ M, ∀K ∈ T h , q h |K ∈ P 1 (K) and X h = v h ∈ X, ∀K ∈ T h , v h |K ∈ (P 1 (K)-bubble) 2
where P 1 (K) stands for the space of restrictions to K of affine functions. P 1 (K)-bubble is defined by adding one extra degree of freedom to the barycenter of every simplex of the triangulation T h of the domain Ω. We have the following inf-sup condition (see [START_REF] Girault | Finite Element Methods for Navier-Stokes Equations[END_REF], Chapter II, Lemma 2.6) :

inf q h ∈M h ,q h =0 sup v h ∈X h - Ω q h div v h dx q h L 2 (Ω) ∇v h L 2 (Ω) = β * > 0. (3.1)
We then consider the following finite element discretization of Navier-Stokes problem (2.2), obtained by the Galerkin method:

Find u h ∈ X h , p h ∈ M h such that ∀v h ∈ X h , ν Ω ∇u h ∇v h dx + Ω (u h .∇)u h v h dx - Ω p h div v h dx = f, v h , ∀q h ∈ M h , Ω q h div u h dx = 0. (3.2)
In order to solve the discrete problem (3.2), we introduce the following space

V h = v h ∈ X h ; ∀q h ∈ M h , - Ω q h div v h dx = 0 . Problem (3.
2) is then equivalent to the problem:

Find u h ∈ V h such that ∀v h ∈ V h , ν Ω ∇u h ∇v h dx + Ω (u h .∇)u h v h dx = f, v h , (3.3)
and admits at least one solution

(u h , p h ) ∈ X h × M h ([9], Chapter IV, Theorem 4.1) such that |u h | 1,Ω ≤ c ν f -1,Ω . (3.4)
In addition, if u ∈ H 2 (Ω) 2 and p ∈ H 1 (Ω), the a priori estimate can be proved by following the approach in [START_REF] Brezzi | Finite dimensional approximation of nonlinear problems, Part I: Branches of nonsingular solutions[END_REF]. Under some further assumptions, it reads ([9], Chapter IV, Theorem 4.1)

|u -u h | 1,Ω + p -p h 0,Ω ≤ Ch.

Iterative algorithm

In order to solve the Navier-Stokes discrete problem, we propose in this section a very simple iterative algorithm. In fact, we linearize the discrete problem and we set an initial guess u 0 h . We will see later on that under suitable conditions, the solution of the iterative algorithm (u i+1 h , p i+1 h ) converges to the solution of the discrete problem (u h , p h ).

Iterative algorithm. Let u 0 h be an initial guess. We introduce, for i ≥ 0, the following algorithm:

Find u i+1 h ∈ X h , p i+1 h ∈ M h such that ∀v h ∈ X h , ν Ω ∇u i+1 h ∇v h dx + Ω (u i h .∇)u i+1 h v h dx - Ω p i+1 h div v h dx = f, v h , ∀q h ∈ M h , Ω q h div u i+1 h dx = 0. (4.1)
We clearly see that problem (4.1) has the following form:

Find u i+1 h ∈ V h , such that ∀ v h ∈ V h , ν Ω ∇u i+1 h ∇v h dx + Ω (u i h .∇)u i+1 h v h dx = f, v h . (4.2) Theorem 4.1. (The convergence Theorem). Let (u i+1 h , p i+1 h ) ∈ X h × M h and (u h , p h ) ∈ X h × M h be
the solutions of the iterative problem (4.1) and the discrete problem (3.2), respectively. Then, for ν > S 4

f -1,Ω , we have

|u i+1 h -u h | 1,Ω ≤ C 1 C -1 2 |u i h -u h | 1,Ω , (4.3)
p i+1 h -p h L 2 (Ω) ≤ C 3 |u i h -u h | 1,Ω , (4.4
) with

C 1 = S 2 4 ν f -1,Ω , C 2 = ν -C 1 , C 3 = α -1 (1 + C 1 C 1 C -1 2 + C 1 . Moreover, the sequence (u i h ) i converges to the solution u h of problem (3.2) if C -1 1 C 2 < 1. Proof. (i)
We start by estimate (4.3). We have (see once more [START_REF] Girault | Finite Element Methods for Navier-Stokes Equations[END_REF], Chapter IV, Theorem 4.1)

|u i+1 h | 1,Ω ≤ c ν f -1,Ω . (4.5)
We now subtract

(3.3) from (4.2) to obtain, for all v h ∈ X h , ν Ω ∇(u i+1 h -u h )∇v h dx + Ω (u i h .∇)u i+1 h -(u h .∇)u h v h dx = 0. (4.6) Intercalating ± Ω (u i h .∇)u h v h dx and taking v h = u i+1 h -u h in (4.6)
, we obtain by applying the Cauchy-Schwarz inequality the following estimate

ν|u i+1 h -u h | 1,Ω ≤ S 2 4 ν f -1,Ω |u i h -u h | 1,Ω + S 2 4 ν f -1,Ω |u i+1 h -u h | 1,Ω . (4.7)
(ii) We now prove the second estimate (4.4). By subtracting (3.3) from (4.1) we obtain

Ω p i+1 h -p h div v h dx = Ω ∇(u i+1 h -u h )∇v h dx + Ω (u i h .∇)u i+1 h -(u h .∇)u h )v h dx. (4.8)
Intercalating ± Ω (u i h .∇)u h v h dx, using (3.1), (3.4), (4.5) and the Cauchy-Schwarz inequality we obtain

α p i+1 h -p h L 2 (Ω) ≤ 1 + C 1 |u i+1 h -u h | 1,Ω + C 1 |u i h -u h | 1,Ω . (4.9)
Finally, combining (4.7) and (4.9) yields the desired estimates and convergence property.

A posteriori error analysis

We start this section by introducing some additional notation needed for constructing and analyzing the error indicators in the sequel.

For any element K ∈ T h we denote by E(K) the set of its edges and we set

E h = K∈T h E(K).
With any edge e ∈ E h we associate a unit vector n such that n is orthogonal to e. We split E(K) in the form

E(K) = E K,∂Ω ∪ E K,Ω
, where E K,∂Ω is the set of edges in E(K) that lie on ∂Ω and E K,Ω = E(K) \ E K,∂Ω . Furthermore, for K ∈ T h and e ∈ E h , let h K and h e be their diameter and length respectively. An important tool in the construction of bounds for the total error is Clément's interpolation operator R h with values in X h . The operator R h satisfies, for all v ∈ H 1 0 (Ω), the following local approximation properties (see R. Verfürth, [START_REF] Verfürth | A Posteriori Error Estimation Techniques For Finite Element Methods[END_REF], Chapter 1):

v -R h v L 2 (K) ≤ Ch K |v| 1,∆ K , v -R h v L 2 (e) ≤ Ch 1/2
e |v| 1,∆e , where ∆ K and ∆ e are the following sets:

∆ K = K ′ ∈ T h ; K ′ ∩ K = ∅ and ∆ e = K ′ ∈ T h ; K ′ ∩ e = ∅ .
We now recall the following properties (see R. Verfürth, [START_REF] Verfürth | A Posteriori Error Estimation Techniques For Finite Element Methods[END_REF], Chapter 1):

Proposition 5.1. Let r be a positive integer. For all v ∈ P r (K), the following properties hold

C v L 2 (K) ≤ vψ 1/2 K L 2 (K) ≤ v L 2 (K) , (5.1
)

|v| 1,K ≤ Ch -1 K v L 2 (K) . (5.2)
where ψ K is the triangle-bubble function (equal to the product of the barycentric coordinates associated with the nodes of K).

Finally, we denote by [v h ] the jump of v h across the common edge e of two adjacent elements K, K ′ ∈ T h .

We have now provided all prerequisites to establish bounds for the total error.

We start the a posteriori analysis of the iterative algorithm. In order to prove an upper bound of the error, we first introduce an approximation f h of the data f which is constant on each element K of T h . Then, we distinguish the discretization and linearization errors. We first write the residual equation

ν Ω ∇u∇v dx + Ω (u.∇)uv dx - Ω p div v dx -ν Ω ∇u i+1 h ∇v dx - Ω (u i h .∇)u i+1 h v dx + Ω p i+1 h div v dx = f, v -v h -ν Ω ∇u i+1 h ∇(v -v h ) dx - Ω (u i h .∇)u i+1 h (v -v h ) dx + Ω p i+1 h div (v -v h ) dx.
(5.3)

Adding and subtracting Ω (u i+1 h .∇)u i+1 h v dx and using the Green formula, give

ν Ω ∇u∇v dx + Ω (u.∇)uv dx - Ω p div v dx -ν Ω ∇u i+1 h ∇v dx - Ω (u i+1 h .∇)u i+1 h v dx + Ω p i+1 h div v dx = K∈T h K (f -f h )(v -v h ) dx + K∈T h K (f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h )(v -v h ) dx - 1 2 e∈E K,Ω e [ ∂u i+1 h ∂n -p i+1 h n].(v -v h ) dτ + Ω (u i h -u i+1 h ).∇ u i+1 h v dx, (5.4)
where τ denotes the tangential coordinate on ∂K.

On the other hand, for all q ∈ L 2 (Ω) K,i , corresponding to an element K ∈ T h , by: η

b(u -u i+1 h , q) = Ω q div u i+1 h dx. ( 5
(L) K,i = |u i+1 h -u i h | 1,K , (5.6)
η (D) K,i = h K f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h L 2 (K) + 1 2 e∈E K,Ω h 1/2 e [ ∂u i+1 h ∂n -p i+1 h n] L 2 (e) + div u i+1 h L 2 (K) .
(5.7)

In order to calculate the a posteriori error estimates, we denote by S the operator which associates with any f in H -1 (Ω) d the part w = u of the solution (u, p) of the Stokes problem (2.6),

S : H -1 (Ω) d → X f → Sf = w.
We consider now the following mapping

G : X → H -1 (Ω) d w → G(w) = (w.∇)w -f.
and we observe that problem (2.2) can equivalently be written as

F (u) = u + SG(u) = 0.
(5.8) Lemma 5.2. Let (u, p) be the solution of problem (2.2). There exists a real number L > 0, such that the following Lipschitz property holds ∀w ∈ X, S DG(u) -DG(w) L(H 1 (Ω)) ≤ L|u -w| 1,Ω .

Proof. We have, for all w, z ∈ X S DG(u).z -DG(w).z 1,Ω ≤ 1 ν DG(u).z -DG(w).z -1,Ω .

(5.9)

We observe that DG(u).z -DG(w).z = z.∇(uw) + (uw).∇z, (5.10) whence

DG(u) -DG(w) .z -1,Ω ≤ 2S 2 4 |u -w| 1,Ω |z| 1,Ω .
(5.11) Thus, combining (5.9) with (5.10) and (5.11) yields the desired property.

Assumption 5.3. The solution (u, p) ∈ X × M of problem (2.2) is such that the operator Id + SDG(u) is an isomorphism of X.

Remark 5.4. Assumption 5.3 implies that the solution u is locally unique, which is more weaker than the global uniqueness of the solution.

We can now state the first result of this section:

Theorem 5.5. Let (u i+1 h , p i+1 h ) ∈ X h × M h and (u h , p h ) ∈ X h × M h be
|u -u i+1 h | 1,Ω + p -p i+1 h L 2 (Ω) ≤ C K∈T h ( η (D) K,i 2 + h 2 K f -f h 2 L 2 (K) ) 1/2 + C ′ K∈T h η (L) K,i 2 1/2
.

Proof. (i) Owing to Lemma 5.2 and Assumption 5.3, it follows from [START_REF] Pousin | Consistency, stability, a priori and a posteriori errors for Petrov-Galerkin methods applied to nonlinear problems[END_REF] that, for any

u i+1 h in a appropriate neighborhood O of u |u -u i+1 h | 1,Ω ≤ C u i+1 h + SG(u i+1 h ) -1,Ω . (5.12)
Introducing F (u) in (5.12) (see equation (5.8)), and from equation (5.4), we obtain for all

v h ∈ X h |u -u i+1 h | 1,Ω ≤ C sup v∈X v =0 f -f h , v -v h + J , v -v h |v| 1,Ω + sup v∈X v =0 Ω (u i h -u i+1 h ).∇ u i+1 h v dx |v| 1,Ω + sup q∈M q =0 Ω q div u i+1 h dx q L 2 (Ω) , (5.13)
where

J , v -v h = K∈T h K (f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h )(v -v h ) dx - 1 2 e∈E K,Ω e [ ∂u i+1 h ∂n -p i+1 h n].(v -v h ) dτ .
Taking v h equal to the image R h v of v by the Clément operator in (5.13), we obtain the desired estimate for |uu i+1 h | 1,Ω .

(ii) Computing b(v, pp i+1 h ) from (5.4) and adding and subtracting

Ω (u i+1 h .∇)uv dx we obtain b(v, p -p i+1 h ) = ν Ω ∇(u i+1 h -u)∇v dx + Ω (u i+1 h .∇)(u i+1 h -u)v dx + Ω (u i+1 h -u)∇uv dx + K∈T h K (f -f h )(v -v h ) dx + K∈T h K (f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h )(v -v h ) dx (5.14) - 1 2 e∈E K,Ω e [ ∂u i+1 h ∂n -p i+1 h n].(v -v h ) dτ + Ω (u i h -u i+1 h ).∇ u i+1 h v dx.
Using Cauchy-Shwarz inequality and the fact that u and u i+1 h are bounded independently of h, we derive the following estimate

b(v, p -p i+1 h ) ≤ K∈T h f -f h L 2 (K) + f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h L 2 (K) v -v h L 2 (K) + 1 2 e∈E K,Ω [ ∂u i+1 h ∂n -p i+1 h n] L 2 (e) v -v h L 2 (K) + S 2 4 ν f 0,Ω |u i+1 h -u i h | 1,Ω |v| 1,Ω (5.15)
+ 2 S 2 4 ν f 0,Ω +ν |u i+1 h -u| 1,Ω |v| 1,Ω .
Taking v h equal R h v in (5.15) and using the inf-sup condition (2.4), we obtain the desired estimate for pp i+1 h L 2 (Ω) . We address now the efficiency of the previous indicators.

Theorem 5.6. For each K ∈ T h , the following estimates hold for the indicators η

(L) K,i defined in (5.6) η (L) K,i ≤ u -u i+1 h 1,K + u -u i h 1,K , (5.16)
and for the indicators η

(D) K,i defined in (5.7) η (D) K,i ≤ C u -u i+1 h 1,ω K + u -u i h 1,ω K + p i+1 h -p L 2 (ω K ) + κ⊂ω K h κ f -f h L 2 (κ) , (5.17)
where ω K is the union of the elements sharing at least one edge with K.

Proof. The estimation of the linearization indicator follows easily from the triangle inequality by introducing u in η (L) K,i . We now estimate the discretization indicator η (D) K,i . We proceed in two steps:

(i) We start by adding and subtracting Ω (u i+1 h .∇)uv dx in (5.3). Taking v h = 0, we obtain

K∈T h K (f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h )v dx = ν Ω ∇(u -u i+1 h )∇v dx + Ω (u -u i+1 h ).∇ uv dx - K∈T h K (f -f h )v dx (5.18) + 1 2 e∈E K,Ω e [ ∂u i+1 h ∂n -p i+1 h n].v dτ + Ω u i+1 h .∇ (u -u i+1 h )v dx + Ω (u i+1 h -u i h ).∇ u i+1 h v dx + Ω (p i+1 h -p) div v dx. We choose v = v K such that v K = (f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h )ψ K on K 0 on Ω \ K,
where ψ K is the triangle-bubble function of the element K.

Using Cauchy-Schwarz inequality, (5.1) and (5.2) we obtain

h K f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h 2 L 2 (K) ≤ (ν + 2C ν f 0,Ω ) u -u i+1 h 1,K v K L 2 (K) +h K f -f h L 2 (K) v K L 2 (K) (5.19) + p i+1 h -p L 2 (Ω) v K L 2 (K) + C ν f 0,Ω u i h -u i+1 h 1,K v K L 2 (K) .
Therefore, we obtain the following estimate of the first term of the local discretization estimator η

(D) K,i h K f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h L 2 (K) ≤ C u -u i+1 h 1,K + u -u i h 1,K +h K f -f h L 2 (K) + p i+1 h -p L 2 (Ω) + η (L) K,i .
(5.20) (ii) We now estimate the second term of η (D) K,i . Similarly, taking v h = 0 in (5.4) we infer

1 2 e∈E K,Ω e [ ∂u i+1 h ∂n -p i+1 h n].v dτ = K (f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h )v dx +ν Ω ∇(u i+1 h -u)∇v dx + Ω (u i+1 h -u).∇ uv dx + K∈T h K (f -f h )v dx (5.21) + Ω (u i+1 h .∇)(u i+1 h -u)v dx + Ω (u i h -u i+1 h ).∇ u i+1 h v dx + Ω (p -p i+1 h ) div v dx. We choose v = v e such that v e =      L e,κ ∂u i+1 h ∂n -p i+1 h n ψ e κ ∈ {K, K ′ } 0 on Ω \ (K ∪ K ′ )
where ψ e is the edge-bubble function, K ′ denotes the other element of T h that share e with K and L e,κ is a lifting operator from e into κ mapping polynomials vanishing on ∂e into polynomials vanishing in ∂\e and constructed from a fixed operator on the reference element.

Using Cauchy-Schwarz inequality, (5.1) and (5.2) we get

h 1/2 e ∂u i+1 h ∂n -p i+1 h n 2 L 2 (e) ≤ (ν + 2C ν f 0,Ω ) u -u i+1 h 1,K∪K ′ v e L 2 (e) +h e f -f h L 2 (K∪K ′ ) v e L 2 (e) +h e f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h L 2 (K∪K ′ ) v e L 2 (e) (5.22)
+ p i+1 h -p L 2 (K∪K ′ ) v e L 2 (e) + C ν f 0,Ω η (L) K,i v e L 2 (e) ,
with

v e L 2 (e) , ≤ c ∂u i+1 h ∂n -p i+1 h n .
Thus, we have estimated the second term of the local discretization indicator η (D) K,i . (iii) Finally, we take q = q K in (5.5) such that

q K = div u i+1 h on K 0 on Ω \ K We obtain div u i+1 h L 2 (K) ≤ u -u i+1 h 1,K .
(5.23)

Collecting the bounds above leads to the final result

η (D) K,i ≤ C u -u i h 1,ω K + u -u i+1 h 1,ω K + p -p i+1 h L 2 (κ) + κ⊂ω K h κ f -f h L 2 (κ) .
According to standard criteria, these estimates of the local linearization and discretization indicators are fully optimal [START_REF] Verfürth | A Posteriori Error Estimation Techniques For Finite Element Methods[END_REF].

Numerical results

In this section, we present numerical results for the Navier-Stokes iterative algorithm. These simulations have been performed using the code FreeFem++ due to F. Hecht and O. Pironneau, see [START_REF] Hecht | New development in FreeFem++[END_REF].

6.1. A priori estimation. We consider the square Ω =]0, 3[ 2 . Each edge is divided into N equal segments so that Ω is divided into 2N 2 triangles. We consider the iterative Navier-Stokes algorithm and the theoretical solution (u, p) = (rot ψ, p) where ψ and p are defined as follows ψ(x, y) = e -30 (x-1) 2 +(y-1) 2 , p(x, y) = cos(2πx)cos(2πy).

6.2.

A posteriori analysis. In this section, we test our a posteriori error estimates on the iterative Navier-Stokes problem. On the same domain as previously, we consider the exact solution (u, p) = (rot ψ, p) where ψ and p are defined as follows ψ(x, y) = e -30 (x-1) 2 +(y-1) 2 , p(x, y) = cos(2π x 3 )cos(2π y 3 ).

We define two different stopping criteria: the classical one η

(L) i = K∈T h η (L) K,i 2 1/2 , η (D) i = K∈T h η (D) K,i 2 1/2 , with η (L) K,i = |u i+1 h -u i h | 1,K , η (D) K,i = h K f h + ν∆u i+1 h -(u i h .∇)u i+1 h -∇p i+1 h L 2 (K) + 1 2 e∈Υ K h e [ ∂u i+1 h ∂n -p i+1 h n] L 2 (e) + div u i+1 h L 2 (K) .
Figures 9 to 12 show the evolution of the mesh (see [START_REF] Verfürth | A Posteriori Error Estimation Techniques For Finite Element Methods[END_REF], Introduction) using the iterative Navier-Stokes algorithm. An adaptive mesh refinement can be outlined as follows:

For i ≥ 0,

(1) Construct an initial mesh T i (2) Solve the discrete problem on T i (3) For each element K in T i compute the a posteriori error estimate. (4) If the estimated global error is sufficiently small then STOP. Otherwise refine locally the mesh (see [START_REF] Hecht | New development in FreeFem++[END_REF] for details), recall T i+1 the new mesh; take i = i + 1 and return to step (2). Figure 15 presents the error curve for uniform (red) and adaptive (blue) mesh refinement using the new stopping criterion. We note that the error using an adaptive mesh is much smaller than the error using a uniform mesh.

Figure 16 illustrates the performance of our new stopping criterion with γ = 0.01 by comparing it to the classical stopping criterion η (L) i ≤ 10 -5 . We can clearly observe that our new stopping criterion reduces the number of iterations. Finally, the following table presents the CPU time of each level of refinement for both criteria, the classical one and the new one. We can see clearly the efficiency of the new stopping criterion with γ = 0.01. In this work we have derived a posteriori error estimates for the finite element discretization of the Navier-Stokes equations. These estimates yield a fully computable upper bound which allow to distinguish the discretization and the linearization errors. We have shown in this work that balancing these two errors leads to important computational savings; in fact, it avoid performing an excessive number of iterations.

❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤

. 5 )

 5 We now define the local linearization indicator η (L) K,i and the local discretization indicator η (D)

Figures 1 and 2

 2 Figures 1 and 2 compare the exact and the numerical solution of the pressure p for N = 100. We can clearly see that the two solutions are coherent.

Figure 1 .

 1 Figure 1. Numerical pressure Figure 2. Exact pressure As well, Figures 3, 4, 5 and 6 compare the different components of the numerical and exact solutions of the velocity u for N = 100.

Figure 3 .

 3 Figure 3. First component of the numerical velocity

Figure 4 .

 4 Figure 4. First component of the exact velocity

Figure 5 .Figure 6 .Figure 7 .Figure 8 .Remark 6 . 1 .

 567861 Figure 5. Second component of the numerical velocity

,

  where γ is a positive parameter. The linearization error indicator η

Figure 9 .

 9 Figure 9. 273 vertices Figure 10. 507 vertices

Figure 13 .

 13 Figure 13. Numerical velocity Figure 14. Exact velocity

Figure 15 .

 15 Figure 15. Error curve as a function of the global vertices number. Uniform mesh (top), adaptive mesh (bottom).

Figure 16 .

 16 Figure 16. Iterations number as a function of the refinement level. Classical criterion (top), new criterion (bottom).

  the solutions of the iterative problem (4.1) and the discrete problem (3.2), respectively. Suppose that the solution (u, p) satisfies Assumption 5.3. Then, there exists a neighborhood O of u in X such that any solution (u i+1

	problem (4.1) with u i+1 h	in O satisfies the following a posteriori error estimate	h , p i+1 h ) of


Lorenz A Gilch

Sebastian Müller

Ends of branching random walks on planar hyperbolic Cayley graphs

Keywords: branching random walk, hyperbolic groups AMS 2000 Mathematics Subject Classification: 60J10, 60J80, 05C80

We prove that the trace of a transient branching random walk on a planar hyperbolic Cayley graph has a.s. continuum many ends and no isolated end.

Introduction

A branching random walk (BRW) is a growing cloud of particles on some graph G in discrete time. The process starts with one particle in the root o of the graph. At each time step each particle splits into offspring particles which then move one step according to a random walk on G. Particles branch and move independently of the other particles and the history of the process. A BRW is therefore driven by two classical stochastic processes: Galton-Watson processes and random walks. Under the assumption that the underlying Galton-Watson process survives the number of particles grows exponentially. If the return probabilities of the underlying random walk decay subexponentially the effect of the growing particles overshadows the transience of the spatial dynamic and the underlying graph will eventually be full of particles. However, if the return probabilities of the random walk decay exponentially as well, then there is a critical growth rate of the Galton-Watson process where the two exponential effects cancel out. While above the critical value the BRW is again recurrent, i.e. every finite set is visited infinitely many times, below and at the critical value every finite set is eventually free of particles and the BRW is called transient. In the transient case, the set of visited vertices and traversed edges defines a proper random subgraph of G and its properties become of interest. This subgraph is called the trace Tr of the BRW.

Let µ = (µ k ) k≥0 be the probability distribution that describes the branching, i.e. each particle produces k offspring with probability µ k . The expected number of offspring is denoted by m = k≥0 kµ k . In this note we assume the underlying graph G = G(Γ, S) to be the Cayley graph of a finitely generated group Γ with respect to a finite symmetric generating set S. The movement of the particles is driven by a driving measure q on S ∪ {e}, where e is the group identity. The driving measure q defines a transition kernel P by p(x, y) = q(x -1 y) for all x, y ∈ Γ.

We make the following standing assumptions.

Assumption 1.

• The underlying Galton-Watson process is supercritical, i.e. m > 1. Furthermore, we assume that µ 0 = 0 and µ 1 > 0.

• The driving measure q of the random walk on G is symmetric, i.e. q(s) = q(s -1 ) for all s ∈ S, and satisfies supp(q) = S ∪ {e}.

These assumptions are to some extend chosen to improve the presentation. The assumptions that are really necessary are that m > 1 and that the driving measure q is symmetric.

The spectral radius, ρ = ρ(P ) = lim sup n→∞ (p (n) (e, e)) 1/n , is a crucial quantity in the study of BRWs: a BRW on a Cayley graph is transient if and only if mρ ≤ 1. This is a consequence of the classification of recurrent groups and Kesten's amenability criterion, see also [START_REF] Gantert | The critical branching Markov chain is transient[END_REF] for an alternative proof. We speak of a critical BRW if mρ = 1.

It was shown in [START_REF] Benjamini | On the trace of branching random walks[END_REF] that the trace of a transient BRW on a Cayley graph G a.s. is transient for simple random walk but recurrent for BRW. Therefore, the trace of a transient BRW is a.s. a proper subgraph of G. It is believed that the trace shares many properties with infinite percolation clusters in the non-unicity phase. In the case of BRWs on free groups (or regular trees) it even turns out that the law of the trace of a BRW is the law of an infinite cluster of some invariant percolation, see [START_REF] Benjamini | Unimodular random trees[END_REF][START_REF] Benjamini | On the trace of branching random walks[END_REF]. However, the situation is not as clear for other Cayley graphs, especially one-ended Cayley graphs.

This note is devoted to the following property of invariant percolation and its analogue for the trace of BRWs. For every invariant weakly insertiontolerant percolation process on a non-amenable quasi-transitive unimodular graph G that has a.s. infinitely many clusters, we have that a.s. every infinite cluster has continuum many ends, no isolated end, and is transient for simple random walk, see Theorem 8.32 in [START_REF] Lyons | Probability on Trees and Networks[END_REF].

On groups with infinitely many ends, there are various ways to see that the trace has infinitely many ends. Even the Hausdorff dimension can be calculated, see [START_REF] Hueter | Anisotropic branching random walks on homogeneous trees[END_REF] for free groups and [START_REF] Candellero | Branching random walks on free products of groups[END_REF] for free products of groups. Note that their approach seems to carry over, using Stalling's splitting theorem, to all groups with infinitely many ends.

As pointed out in [START_REF] Candellero | The number of ends of critical branching random walks[END_REF] there is an elegant argument using symmetry that the trace of a subcritical BRW, i.e. m < 1/ρ, has infinitely many ends. This argument extends to the critical case if n≥1 nm n p (n) (e, e) < ∞. However, this criterion does not apply to the most interesting Cayley graphs like Gromov hyperbolic groups and the following conjecture remains open.

Conjecture 1 (I. Benjamini). Let G be any non-amenable vertex transitive graph and assume the transition kernel P of the underlying random walk to be symmetric. Then the trace of a transient BRW has infinitely many ends.

Remark 1.1. The assumption of symmetry is crucial, since there are nonsymmetric driving measures that induce one-ended traces, see [START_REF] Candellero | The number of ends of critical branching random walks[END_REF].

We answer this conjecture affirmative for BRWs on planar hyperbolic Cayley graphs.

Theorem 1. Assume Assumption 1 holds. The trace of a transient BRW on a planar hyperbolic Cayley graph has a.s. continuum many ends and no isolated end.

The proof uses the fact that the trace of a BRW is a unimodular random graph and therefore gives rise to the application of the generalized Mass-Transport principle. This property is used to prove that a.s. every trace that has at least 3 ends has no isolated end, see Proposition 1. The main issue will be to prove that the trace has a.s. no isolated end, see Proposition 2, and hence infinitely many ends. The proof of this proposition uses crucially the planarity of the Cayley graph, a recent result in [START_REF] Gouëzel | Local limit theorem for symmetric random walks in Gromovhyperbolic groups[END_REF] that Ancona's Inequality still holds true for the Green function at the radius of convergence, and Proposition 1.

In Section 2 we give some background on unimodular random graphs (URG) and random walks on hyperbolic groups. We believe that the information given there is sufficient to follow the proof of Theorem 1 in Section 3. However, for readers who are not familiar with the concept of URGs and of random walks on hyperbolic groups before, it might be useful to consult some of the references given along Section 2.

Preparations

Definition and preliminaries

We use the standard notation for a locally finite graph G = (V, E): V is the set of vertices, E is the set of edges, and we write x ∼ y if (x, y) ∈ E. The distance between two vertices is the length of a shortest path between these vertices and will be denoted by d(•, •). We write (G, o) for a rooted graph with root o.

Let Γ be a finitely generated group with group identity e; group operations are written multiplicatively. The group Γ together with some finite symmetric generating set S induces a Cayley graph G = G(Γ, S) whose vertex set equals Γ and x ∼ y if and only if x -1 y ∈ S. The group identity e of Γ will be identified with the root o of the Cayley graph G.

Let q be a probability measure on the generating set S ∪ {e}. The corresponding random walk (S n ) n≥0 on G is a Markov chain with transition probabilities p(x, y) = q(x -1 y) for x, y ∈ Γ. Equivalently, the random walk (starting in x) can be described as

S n = xX 1 • • • X n , n ≥ 1,
where the X i 's are i.i.d. random variables with distribution q.

Besides the definition of BRWs given in Section 1 there is another powerful description of BRWs. This definition is based on the concept of tree-indexed random walks introduced in [START_REF] Benjamini | Markov chains indexed by trees[END_REF]. Let (T, r) be a rooted infinite tree. The tree-indexed random walk can be described as a marking (or labelling) of the rooted tree (T, r). For any vertex v = r denote by v -the neighbour of v closest to r. Label the edges of T with i.i.d. random variables X v 's with distribution q; the random variable X v is the label of the edge (v -, v). These labels correspond to the steps of the tree-indexed walk and the positions of "particles" are given by S v = x • n i=1 X v i where v 0 = r, v 1 , . . . , v n = v is the unique geodesic from r to v at level n.

A tree-indexed random walk becomes a BRW if the underlying tree T is a realization of a Galton-Watson process. We call T the family tree of the BRW.

Unimodular random graphs

In this note we only give the essentials needed for our proofs. We invite the reader to consult [START_REF] Benjamini | On the trace of branching random walks[END_REF][START_REF] Müller | Interacting growth processes and invariant percolation[END_REF] for more details on the connection between BRWs and unimodular random graphs, and [START_REF] Aldous | Processes on unimodular random networks[END_REF] for a more general introduction to the concept of URGs.

A rooted isomorphism between two rooted graphs (G, o) and (G ′ , o ′ ) is an isomorphism of G onto G ′ which maps o to o ′ . We denote by G * the space of isomorphism classes of rooted graphs and write [G, o] for the equivalence class that contains (G, o). In the same way one defines the space G * * of isomorphism classes of graphs with an ordered pair of distinguished vertices. That is, (G

G * * → [0, ∞], we have x∈V f (G, o, x)dν([G, o]) = x∈V f (G, x, o)dν([G, o]).
(2.1)

Realizations of unimodular measures are called unimodular random graphs.

An important class of unimodular measures arises from Galton-Watson processes. The Galton-Watson tree is defined inductively: start with one vertex, the root r of the tree. Then the number of offspring of each particle (vertex) is distributed according to µ. Edges are between vertices and their offspring. We denote by GW the corresponding measure on the space of rooted trees. In this construction the root clearly plays a special role and GW is not unimodular. However, if we bias the distribution such that the probability that the root has degree k + 1 is proportional to µ k k+1 we obtain a unimodular measure UGW. When we use the UGW measure instead of the standard GW measure to define the family tree of the BRW we denote the BRW by UBRW.

Due to the description of the BRW as a tree-indexed random walk the unimodularity of UGW caries over to the trace: the trace of a UBRW on a Cayley graph is a unimodular random graph, see Theorem 3.7 in [START_REF] Benjamini | On the trace of branching random walks[END_REF]. This property makes the UBRW more natural to consider than the original BRW and we will prove Theorem 1 for UBRWs. However, it is not difficult to see that it then also holds true for BRWs.

Ends of graphs

Consider a locally finite graph G = (V, E). A ray is a sequence π = x 0 , x 1 , . . . of distinct vertices such that x i ∼ x i+1 for all i ≥ 0. For any finite set F of vertices we consider its complement G \ F , which is the graph induced by the vertex set V \ F . This graph consists of finitely many connected components. Every ray π must have all but finitely many points in exactly one component; we say that π ends up in that component. Two ends are equivalent if they end up in the same connected component for all choices of F . Ends are equivalence classes of rays and we denote by ϑG the set of ends. Let F be a finite vertex set and C be some component of G \ F . We write ϑC for the set of ends whose rays end up in C. The space of ends ϑG can be equipped with a discrete topology in the following way. For any finite set F and any end w there is precisely one component of G \ F whose completion contains w. Varying F yields a neighbourhood base for w. An isolated end is an end that is isolated in this topology.

Hyperbolic groups and random walks

From now on we assume that the underlying group Γ is hyperbolic and the generating set S induces a planar Cayley graph G = G(Γ, S). Both assumptions, hyperbolicity and planarity, are crucial.

Let us first collect several classic facts about hyperbolic groups and random walks; we refer to the survey [START_REF] Calegari | The ergodic theory of hyperbolic groups[END_REF] for an excellent introduction. An elementary hyperbolic group is either finite or has two ends. We will focus on the case of non-elementary hyperbolic groups since random walks on them are transient. Define the Green functions

G r (x, y) = ∞ n=0 p (n) (x, y)r n , x, y ∈ Γ,
for all r ≤ R := 1/ρ. It is proved in [START_REF] Gouëzel | Local limit theorem for symmetric random walks in Gromovhyperbolic groups[END_REF] that for finite range random walks on hyperbolic groups Ancona's Inequalities hold up to the radius of convergence: there exists some C > 0 such that for any x, z ∈ Γ and for any y on a geodesic segment from x to z we have

G r (x, z) ≤ CG r (x, y)G r (y, z) ∀r ∈ [1, R].
Symmetry of the random walk implies, see Lemma 2.1 in [START_REF] Gouëzel | Random walks on co-compact Fuchsian groups[END_REF], that lim

d(o,x)→∞ G R (o, x) = 0.
Eventually we obtain, see Lemma 2.2 in [START_REF] Gouëzel | Random walks on co-compact Fuchsian groups[END_REF], that the Green functions of the random walk decay exponentially, that is, there exist some constants C 1 and ̺ < 1 such that for all x, y ∈ Γ

G R (x, y) ≤ C 1 ̺ d(x,y) .
(2.2)

In the case of planar Cayley graphs, the Cayley 2-complex is the 2complex such that the one-skeleton is given by the Cayley graph G and the 2-cells are bounded by loops in G. The 2-complex is homeomorphic to the hyperbolic disc and it can be endowed with an orientation. This orientation is used implicitly at several points in the proof of Proposition 2. Moreover, the Gromov hyperbolic boundary ∂G can be identified with the unit circle.

Proof of Theorem 1

The following result holds true for traces of transient BRWs on Cayley graphs (or even URGs). Its proof is an adaption of the one for invariant percolation, see Proposition 8.33 in [START_REF] Lyons | Probability on Trees and Networks[END_REF]. As the arguments are short we allow us to present the details. We stick as close as possible to the notations in [START_REF] Lyons | Probability on Trees and Networks[END_REF]. Assume that ξ is an isolated end of Tr and let us show that this leads to a contradiction. There exists some finite set F such that the connected component U of G \ F whose completion contains ξ satisfies U ∩ A n = ∅. Moreover, there exists a finite set of vertices B such that all paths from U to all other connected components of G\F must pass through B. Then a subset of vertices of B gets all the mass from all the vertices in U. As U contains infinitely many vertices the set B receives infinite mass. Using the property that "everything shows at the root", see [ Proof. We start with some preparations. Since the Gromov boundary ∂G can be identified with a circle there exist infinite geodesics γ 1 , γ 2 and γ 3 starting from o with distinct boundary points ξ 1 , ξ 2 and ξ 3 . Denote by γ = 3 i=1 {γ i }, where {γ i } is the set of vertices in γ i . We define ∂G ij to be the part of the Gromov boundary that is between ξ i and ξ j and S ij to be the set of vertices between γ i and γ j . Let K be some large positive constant to be chosen later. Geodesics in hyperbolic groups either converge to the same boundary point or diverge exponentially. Hence, for K sufficiently large there exist x 1 ∈ S 12 , x 2 ∈ S 23 , and x 3 ∈ S 31 such that d(x i , γ) = K for all i ∈ {1, 2, 3}.

Let i ∈ {1, 2, 3} and consider the sphere S(x i , n) of radius n around x i in the Cayley graph metric. Since the γ i 's are geodesics and triangles are thin we have that there exists some constant C 2 such that |S(x i , n) ∩ γ| ≤ C 2 n. Now, start a BRW in x i and denote by Tr i the trace of the BRW started in x i . Using Markov's Inequality and Inequality (2.2) we obtain that

P[|Tr i ∩ γ| ≥ 1] ≤ E[|Tr i ∩ γ|] ≤ y∈γ G m (x, y) ≤ n≥K C 1 C 2 n̺ n , (3.1)
which tends to 0 as K tends to infinity.

We assume now that P[Tr has an isolated end] = c > 0 and show that this yields a contradiction. Inequality (3.1) allows us to choose K sufficiently large such that for i ∈ {1, 2, 3} P[Tr i has an isolated end, |Tr i ∩ γ| = 0] > 0.

We start the UBRW in o and condition the UBRW on the event that at time N = max{d(o, x i ) : i ∈ {1, 2, 3}} in each of the vertices x 1 , x 2 and x 3 there is exactly one particle and no particle elsewhere. This is possible since we assume that µ 1 > 0 and q(e) > 0. So what happens at times n ≥ N has the same distribution as we start three independent BRWs in x 1 , x 2 , and x 3 . Eventually, using the planarity of G we get that Tr has with positive probability at least three distinct ends including at least one isolated end, which yields a contradiction to Proposition 1.

It remains to show that the trace has a.s. continuum many ends. Proof. Due to Proposition 2 the trace Tr must have infinitely many ends because otherwise each end would be isolated. Moreover, each infinite connected component of Tr \ B(o, n) must contain at least two ends; otherwise, such a component would contain an isolated end. Thus, the number of ends is at least of order |2 N |, which proves the claim since Tr is of bounded degree.

Proposition 1 .

 1 Consider the trace of a transient symmetric UBRW on a Cayley graph. Almost surely every trace that has at least 3 ends has no isolated end. Proof. For each n ∈ N let A n be the union of all vertex sets A ⊂ Tr such that the diameter diam(A) ≤ n (in the metric in Tr) and Tr \ A has at least 3 infinite components. If Tr has at least 3 ends then A n = ∅ for all but finitely many n. We assume from now on that Tr has at least 3 ends. Fix some n ∈ N. For any vertex x in Tr let C(x) = {y ∈ A n : d(x, y) = min z∈An d(x, z)} be the set of vertices in A n that are closest to x in the metric in Tr. We can define the Borel function F : G * * → [0, ∞]: F (Tr, x, y) = 1 |C(x)| 1 {y∈C(x)} , if A n = ∅, 0, otherwise. The function F is well-defined since F (Tr, o, x) is invariant under isomorphisms. Since the law ν of the rooted trace [Tr, o] is unimodular we can apply the MTP to obtain that the expected mass received by o is at most 1: x∈Tr F (Tr, x, o)dν([Tr, o]) = x∈Tr F (Tr, o, x)dν([Tr, o]) ≤ 1.

Corollary 2 .

 2 Assume Assumption 1 holds. The trace of a transient UBRW on a planar hyperbolic Cayley graph has a.s. continuum many ends.

  1 , o 1 , o 2 ) and (G 2 , o ′ 1 , o ′ 2 ) are isomorphic if and only if there is an isomorphism from G 1 onto G 2 which maps o 1 to o ′ 1 and o 2 to o ′ 2 . The spaces G * and G * * can be equipped with metrics that turn them into separable and complete metric spaces. A Borel probability measure ν on G * is called unimodular if it obeys the Mass-Transport Principle (MTP): for all Borel function f :

  1, Lemma 2.3], we obtain that x∈Tr F (Tr, x, o)dν([Tr, o]) = ∞, a contradiction. Hence, almost surely every trace with A n = ∅ does not have isolated ends. Since this holds for all but finitely many n ∈ N, we obtain that almost surely a trace with isolated ends can have at most two ends. Proposition 2. Assume Assumption 1 holds. The trace of a transient UBRW on a planar hyperbolic Cayley graph has a.s. no isolated end.

Acknowledgment

The authors thank Elisabetta Candellero and Matthew Roberts for comments on a first version of this note. The research was supported by the exchange programme Amadeus-Amadée 31473TF.