Dang The

Huynh

Fabien Mathieu

Laurent Viennot

LiveRank: How to Refresh Old Datasets

This paper considers the problem of refreshing a dataset. More precisely, given a collection of nodes gathered at some time (Web pages, users from an online social network) along with some structure (hyperlinks, social relationships), we want to identify a significant fraction of the nodes that still exist at present time. The liveness of an old node can be tested through an online query at present time. We call LiveRank a ranking of the old pages so that active nodes are more likely to appear first. The quality of a LiveRank is measured by the number of queries necessary to identify a given fraction of the active nodes when using the LiveRank order. We study different scenarios from a static setting where the Liv-eRank is computed before any query is made, to dynamic settings where the LiveRank can be updated as queries are processed. Our results show that building on the PageRank can lead to efficient LiveRanks, for Web graphs as well as for online social networks.

Introduction

One of the main challenges for large networks data mining is to deal with the high dynamics of huge datasets: not only are these datasets difficult to gather, but they tend to become obsolete very quickly.

In this paper, we are interested in the evolution at large time scale of any large corpus available online. Our primary focus will be the Web, but our approach encompasses any online data with similar linkage enabling crawling, like P2P networks or online social networks. We thus focus on batch crawling, where starting from a completely out-dated snapshot of a large graph like the Web, we want to identify a significant fraction of the nodes that are still alive now. The interest is twofold.

First, many old snapshot of large graphs are available today. Reconstructing roughly what remains from such archives could result to interesting studies of the long term evolution of these graphs. For large archives where one is interested in a particular type of pages, recrawling the full set of pages can be prohibitive. We propose to identify as quickly as possible a significant fraction of the still alive pages. Further selection can then be made to identify a set of pages suitable for the study and then to crawl them. Such techniques would be especially interesting when testing the liveness of an item is much lighter than downloading it completely. This is for instance the case for the Web with HEAD queries compared to GET queries. If a large amount of work has been devoted to maintaining fresh a set of crawled pages, little attention has been paid to the coverage of a partial recrawling a fairly old snapshot.

Second, some graphs tend to be harder to crawl with time. For instance, Twitter has continuously restricted its capacity to be crawled. Performing a full scan was possible a few years ago [START_REF] Gabielkov | Studying Social Networks at Scale: Macroscopic Anatomy of the Twitter Social Graph[END_REF], but it can be prohibitively long nowadays. New techniques must thus be developed for identifying efficiently active accounts in such settings.

Problem formulation

Given an old snapshot, our goal is to identify a significant fraction of the items that are still alive or active now. The cost we incur is the number of fetches that are necessary to attain this a goal. A typical cost measure will be the average number of fetches per active item identified. The strategy for achieving this goal consists in producing an ordering for fetching the pages. We call LiveRank an ordering such that the items that are still alive tend to appear first. We consider the problem of finding an efficient LiveRank in three settings: static when it is computed solely from the snapshot and the link relations recorded at that time, sampling-based when a sampling is performed in a first phase allowing to adjust the ordering according to the liveness of sampled items, or finally dynamic when it is incrementally computed as pages are fetched.

Contribution

We propose various LiveRank algorithms based on the graph structure of the snapshot. We evaluate them on two Web snapshots (from 10 to 20 millions nodes) and on a Twitter snapshot (40 million nodes). We propose several propositions based on the graph structure of the snapshot. We show that a rather simple combination of a small sampling phase and PageRank-like propagation in the remaining of the snapshot allows to gather from 15% to 75% of the active nodes with a cost that remains within a factor of 2 from the optimal ideal solution.

Related work

The process of crawling the Web has been extensively studied. A survey is given by Olston and Najork [START_REF] Olston | Web crawling[END_REF].

We focus here on batch crawling where the process starts from a given set of pages and terminates at some point. This is classically opposed to incremental crawling where pages are continuously fetched. In incremental crawling, one of the main tuning is to balance between fetching new pages and refreshing old ones: the former increases coverage while the latter increases freshness. Both types may allow to discover new links towards unknown new pages (old pages can change). Cho and Garcia-Molina have extensively studied the problem of incremental crawling. For example, in [START_REF] Cho | Effective page refresh policies for web crawlers[END_REF], they propose one of the first formalization of freshness and a thorough study on refreshing policies. They show the counter-intuitive result that adapting the frequency of crawl proportionally to the frequency of change works poorly with respect to the overall freshness of the fetched copy of the Web. The results have been extended with more elaborated variations of freshness. For instance, information longevity [START_REF] Olston | Recrawl scheduling based on information longevity[END_REF] considers the evolution of fragments of the content of a page.

The issue we investigate here is closer to a problem introduced by Cho and Ntoulas [START_REF] Cho | Effective change detection using sampling[END_REF]: they use sampling to estimate the frequency of change per site and then to fetch a set of pages such that the overall change ratio of the set is maximized. Their technique consists in estimating the frequency of page change per site and to crawl first sites with high frequency change. Tan et al. [START_REF] Tan | A clustering-based sampling approach for refreshing search engine's database[END_REF] improve slightly over this technique by clusterizing the pages according to several features: not only their site (and other features read from the URL) but also content based features and linkage features (including PageRank and incoming degree). A change ratio per cluster is then estimating through sampling and clusters are downloaded in descending order of the estimated values. More recently, Radinsky and Bennett [START_REF] Radinsky | Predicting content change on the web[END_REF] investigate a similar approach using learning techniques and avoiding the use of sampling.

Note that these approaches mainly focus on highly dynamic pages and use various information about pages whereas we are interested in stable nodes and we use only the graph structure, which is lighter.

With a slightly different objective, Dasgupta et al. [START_REF] Dasgupta | The discoverability of the web[END_REF] investigate how to discover new pages while minimizing the average number of fetches per new page found. Their work advocates for a greedy cover heuristic when a small fraction of the new pages has to be discovered quickly. On the opposite, they recommend a heuristic based on out-degrees for gathering a large fraction of the new pages. Their framework is close to ours and inspired the cost function used in this paper.

A related problem consist in estimating which pages are really valid among the "dangling" pages on the frontier of the crawled web (those that are pointed by crawled pages but that were not crawled themselves). Eiron et al. propose to take this into account in the PageRank computation [START_REF] Eiron | Ranking the web frontier[END_REF]. In a similar trend, Bar-Yossef et al. [START_REF] Bar-Yossef | Sic transit gloria telae: Towards an understanding of the web's decay[END_REF] propose to compute a "decay" score for each page by refining on the proportion of dead links in a page. Their goal is to identify poorly updated pages. This score could be an interesting measure for computing a LiveRank, however its computation requires the identification of dead links. It is thus not clear how to both estimate it and at the same time try to avoid testing the liveness of possibly many dead pages.

While recrawling policies have been extensively studied for Web graph, other sources of online data such as social networks are less covered. Yet, it is possible to similarly crawl such networks. For example, one can explore the Twitter network by fetching information about user accounts that are linked by the follower-followee relations. However, crawling is much more restricted as all the data is possessed by a single company. This makes our approach even more relevant in such contexts where gathering a large amount can be extensively long. Interestingly, Kwak et al. [START_REF] Kwak | What is twitter, a social network or a news media[END_REF] show, among various observations, a correlation between number of followers and PageRank. On the other hand the activity of a user measured in number of tweets seems to be more correlated to his number of followees that his number of followers. First reported Twitter crawls include [START_REF] Java | Why we twitter: understanding microblogging usage and communities[END_REF][START_REF] Krishnamurthy | A few chirps about twitter[END_REF][START_REF] Kwak | What is twitter, a social network or a news media[END_REF]. Recently, Gabiekov et al. [START_REF] Gabielkov | The complete picture of the twitter social graph[END_REF][START_REF] Gabielkov | Studying Social Networks at Scale: Macroscopic Anatomy of the Twitter Social Graph[END_REF] have presented a preliminary study on a complete picture of Twitter social graph. The authors themselves claim that such extensive crawling becomes more and more difficult with time as Twitter tends to restrict its white list of IP authorized to query its API at high rate.

Roadmap

In the next Section, we propose a simple metric to evaluate the quality of a LiveRank and we introduce several classes of possible LiveRank solutions. In Section 3, we introduce three datasets, two from the .uk Web and one from Twitter, and we expose how a ground truth was computed for them. Lastly, in Section 4, we benchmark our LiveRanks against the datasets and discuss the results.

Model

Let G = (V, E) be a graph obtained from a past crawl of a structured network. For example, G can represent:

• A Web graph, V representing the crawled pages and E the hyperlinks: for i, j in V , (i, j) is in E if, and only if, there is an hyperlink to j in i. For Web graphs, edges are always directed;

• A social network, V representing the users and E social relationships between them. For social networks, edges can be undirected (symmetric relationships like friendship) or directed (asymmetric relationship like follower/followee).

Let n denote the size of V . At present time, only a subset of G is still active. The meaning of active depends of the context and needs to be defined: alive pages for Web graphs, non-idle users for social networks, etc. We call a the function that tells if nodes are active or not: a(X) denotes the active nodes from X ⊂ V , while ā(X) stands for X \ a(X). Let n a be |a(V )|.

The problem we need to solve is can be expressed as: how to crawl a maximum number of pages from a(V ) with a minimal crawling cost. In particular, one would like to avoid crawling too much pages from ā(V ). If a was known, the task would be easy, but testing the activity of a node obviously requires to crawl it. This is the rationale for the notion of LiveRank.

Performance metric

Formally, any ordering can be seen as a LiveRank, so we need some performance metrics to define good LiveRanks that succeed in ranking the pages from a(V ) first. Following [START_REF] Dasgupta | The discoverability of the web[END_REF], we define the LiveRank cost as the average number of node retrievals necessary to obtain an active node, after a fraction 0 < α ≤ 1 of the active nodes has been retrieved.

In details, let L i represent the i first pages returned by a LiveRank L, and let i(L, α) be the smallest integer such that |a(Li)| na ≥ α. The cost function of L, which depends on α, is then defined by: cost(L, α) = i(L, α) αn a .

A few remarks on the cost function:

• It is always at greater than or equal to 1. An ideal LiveRank would perfectly separate a(V ) from rest of the nodes, so its cost function would be 1. Without some oracle, this requires to test all pages, which is exactly what we would like to avoid. The cost function allows to capture this dilemma.

• Keeping a low cost becomes hard as α gets close to 1: without some clairvoyant knowledge, capturing almost all active nodes is almost as difficult as capturing all actives nodes. For that reason, one expects that when α gets close to 1, the set of nodes any real LiveRank will need to crawl will tend to V , leading to an asymptotical cost n na . This will be verified in Section 4.

• Lastly, one may have noticed that the cost function uses n a = |a(V )|, for which an exact value requires a full knowledge of active nodes. This is not an issue here as we will perform our evaluation on datasets where a is known. For use on datasets without ground truth, one could either use an estimation of n a based on a sampling or use a non-normalized cost function (for instance the fraction of active nodes obtained after i retrievals).

PageRank

Many of the LiveRanks proposed here are based on some variants of PageRank.

PageRank is a link analysis algorithm introduced in [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF] and used by the Google Internet search engine. It assigns a numerical importance to each page of a Web graph. It uses the structural information from G to attribute importance according to the following (informal) recursive definition: a page is important if it is referenced by important pages. Concretely, to compute PageRank value, denoted by the row vector Y , one needs to find the solution of the following equation:

Y = dY A + (1 -d)X, (1)
where A is a substochastic matrix derived from the adjacency matrix of G, d < 1 is a so-called damping factor (often set empirically to d = 0.85), and X 0 is a zap vector. X represents a kind of importance by default that is propagated from nodes to nodes according to A with a damping d.

Computation of PageRank vectors has being widely studied. Several specific solutions were proposed and analysed [START_REF] Langville | Deeper inside pagerank[END_REF][START_REF] Bianchini | Inside pagerank[END_REF] including power method [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF], adaptation [START_REF] Kamvar | Adaptive methods for the computation of pagerank[END_REF], extrapolation [START_REF] Haveliwala | Computing pagerank using power extrapolation[END_REF][START_REF] Kamvar | Extrapolation methods for accelerating pagerank computations[END_REF], adaptive on-line method [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF], etc.

We now present the different LiveRanks that we will consider in this paper. We broadly classify them in three classes: static, sample-based and dynamic.

Static LiveRanks

Static LiveRanks are computed offline using uniquely the information from G. That makes them very basic, but also very easy to be used in a distributed way: given p crawlers of similar capacities, if L = (l 1 , . . . , l n ), simply assign the task of testing node l i to crawler i mod p.

We propose the following three static LiveRanks.

Random permutation (R) will serve both as a reference and as a building block for more advanced LiveRanks. R ignores any information from G, so its cost should be in average n na , with a variance that tends to 0 as α tends to 1. We expect good LiveRanks to have a cost function significantly lower than cost(R).

Decreasing Indegree ordering (I) is a simple LiveRank that we expect to behave better than a random permutation. Intuitively, a high indegree can mean some importance, and important pages may be more robust. Also, older nodes should have more incoming edges (in terms of correlation), so high degree nodes can correspond to nodes that were already old at the time G was crawled, and old nodes may last longer than younger ones. Sorting by degree is the easiest way to exploit these correlations.

PageRank ordering (P ) pushes forward the indegree idea. The intuition is that nodes that are still active are likely to point towards nodes that are still active also, even considering only old edges. This suggests to use a PageRanklike importance ranking. In absence of further knowledge, we propose to use the solution of (1) using d = .85 (typical value for Web graphs) and X uniform on V .

Note that it is very subjective to evaluate PageRank as an importance ranking, as importance should be ultimately validated by humans. On the other hand, the quality of PageRank as a static LiveRank is straightforward to verify, for instance using our cost metric.

The possible existence of correlation between Indegree (or PageRank) and activity will be investigated in Section 3.3.

Sample-based LiveRanks

Using a LiveRank consists in crawling V in the prescribed order. During the crawl, the activity function a becomes partly available, and the obtained information could be used to enhance the retrieval. Following that idea, we consider here a two-steps sample-based approach: we first fix a testing threshold z and test z items following a static LiveRank (like R, I or P ). For the set Z of nodes tested, called sample set or training set, a(Z) is known, which allows us to recompute the LiveRank of the remaining untested nodes.

Because the sampling uses a static LiveRank, and the adjusted new LiveRank is static as well, sample-based LiveRanks are still easy to use in a distributed way as the crawlers only need to receive crawl instructions on two occasions.

Notice that in the case where the sampling LiveRank is a random permutation, |a(Z)| n z can be used as an estimate for n a . This can for instance be used to decide when to stop crawling if we desire to identify αn a active nodes in a(V ).

Simple adaptive LiveRank (P a ) When a node is active, we can assume it increases the chance that nodes it points to in G are also active, and that activity is transmitted somehow through hyperlinks. Following this idea, a possible adaptive LiveRank consists in taking for X in (1) the uniform distribution on a(Z). This diffusion from such an initial set can be seen as a kind of breadth-first traversal starting from a(Z), but with a PageRank flavour.

Double adaptive LiveRank (P +/a

) The simple adaptive LiveRank does not use the information given by ā(Z). One way to do this is to calculate an "anti"-PageRank based on ā(Z) instead of a(Z). This ranking would represents a kind of diffusion of idleness, the underlying hypothesis being that idle nodes may point to nodes that tend to be idel too. As a result, we obtain a new Liv-eRank by combining these two PageRanks. After having tested several possible combinations not discussed in this paper, we empirically chose to weight each node by the ratio of the two sample-based PageRank, after having set all null entries of the anti-PageRank equal to the minimal non-null entry.

Active-site first LiveRank (ASF) To compare with previous work, we propose the following variant inspired by the Dasgupta et al. [START_REF] Dasgupta | The discoverability of the web[END_REF] strategy for finding pages that have changed in a recrawl. Their algorithm is based on sampling for estimating page change rate for each website and then to crawl sites by decreasing change rate. In details, Active-site first (ASF) consists in partitioning Z into websites determined by inspecting the URLs. We thus obtain a collection Z 1 , . . . , Z p of sets. For each set Z i corresponding to some site i, we obtain an estimation |a(Z i )|/|Z i | of its activity (i.e. the fraction of active pages in the site). We then sort the remaining URLs by decreasing site activity. Of course, this technique only works for Web graphs and can hardly be adjusted to other networks.

Dynamic LiveRanks

Instead of using the acquired information just one time after the sampling, Dynamic LiveRanks are continuously computed and updated on the fly along the entire crawling process. On the one hand, this gives them real-time knowledge of a, but on the other hand, as the dynamic LiveRank may evolve all the time, they can create synchronization issues when used by distributed crawlers.

Like for sample-based LiveRanks, dynamic LiveRanks use a training set Z of z nodes from a static LiveRank. This allows to bootstrap the adjustment by giving a non-empty knowledge of a, and prevents the LiveRank from focusing on only a small subset of V .

Breadth-First Search (BFS) With BFS, we aim at taking direct advantage of the possible propagation of activity. The BFS queue is initialized with the (uncrawled) training set Z. The next node to be crawled is popped from the queue following First-In-First-Out (FIFO) rule. If the selected node appears to be active, all of its uncrawled outgoing neighbors are pushed into the end of the queue. When the queue is empty, we pick the unvisited node with highest PageRank1 .

Active indegree (AI) BFS uses a simple FIFO queuing to determine the processing order. We now propose AI which provides a more advanced node selection scheme. For AI, each node in the graph is associated with a activity score value indicating how many reported active nodes point to it. These values are set to zeros at the beginning and always kept up-to-date. AI is initialized by testing Z: each node in a(Z) will increment the associated values of its out-going neighbors by one. After Z is tested, the next node to be crawled is simply the one with highest activity score (in case of equality, to keep things consistent, we pick the node with highest PageRank). Whenever a new active node is found, we update the activity scores of its untested neighbors.

With Dynamic LiveRank, it is natural to think of a last variant, a dynamic PageRank-based strategy where PageRank vector is recursively computed. Starting from a uniform distribution on a(Z), we obtain X in [START_REF]Twitter graph[END_REF]. Then a new teleportation vector is constructed as a uniform distribution on largest value entries of X, i.e., those which are considered probably active after the first diffusion of a(Z). The process continues and X is updated iteratively. However, after some experimentations, we realized that this method is not efficient since it can not escape from the locality of a(Z).

Datasets

We chose to evaluate the proposed LiveRanks on existing datasets of the Web and Twitter available on the WebGraph platform [START_REF] Boldi | The WebGraph framework I: Compression techniques[END_REF][START_REF] Boldi | Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks[END_REF][START_REF] Boldi | Ubicrawler: A scalable fully distributed web crawler[END_REF]. In this Section, we present the datasets, describe how we obtained the activity function a and observe the correlations between a, indegree and PageRank.

Webgraph Datasets

For the study of Web graphs, we focused on snapshots of the British domain .uk.

uk-2002 dataset

The main dataset we use is the web graph uk-20022 from UbiCrawler [START_REF] Boldi | Ubicrawler: A scalable fully distributed web crawler[END_REF]. This 2002 snapshot contains 18,520,486 pages and 298,113,762 hyperlinks.

The preliminary task is to determine a, which is for Web graphs the liveness of the pages of the snapshot. For each URL, we have performed a GET request and hopefully obtained a corresponding HTTP code. Our main findings are:

• One third of the total pages are no longer available today, the server returns error 404.

• One fourth have a DNS problem (which probably means the website is also dead).

• For one fifth of the cases, the server sends back the redirection message 301. Most redirections for pages of an old site lead to the root of a new site. If we look at the proportion of distinct pages alive at the end of redirections, it is as low as 0.1%.

• Less than 13% of pages return the code 200 (success). However, we found out that half of them actually display some text mentioning that the page was not found. To handle this issue, we have fully crawled all the pages of the dataset with code 200 and filtered out pages whose title or content have either Page Not Found or Error 404.

The results are summarized in Table 1. In the end, our methodology led to finding out 1,164,998 alive pages, accounting for 6.4% of the dataset.

uk-2006 dataset

The settings of uk-2002 are rather adversarial (old snapshot with relatively few alive pages), so we wanted to evaluate the impact of LiveRanks on shorter time scales. In absence of fresh enough available datasets, we used the DELIS dataset [START_REF] Boldi | A large time-aware graph[END_REF], a series of twelve continuous snapshots 3

Twitter Dataset

Lastly, we used the dataset twitter-2010 first introduced in [20]4 . The graph contains roughly 42 millions Twitter user accounts and 1.5 billions followerfollowee relationships among them. Arcs in the graph are directed from followers to followees: there is an arc from node x to y if user x follows y. This orientation convention is in line with a PageRank approach: a user is important when she is followed by important users. Notice that information (tweets) traverses arcs in the opposite direction, from followees to followers. We consider that a user is active if she has posted a tweet recently. For that purpose, we can query the Twitter interface to recover the timestamp of the last tweet of the user associated with a given identifier. Recovering the timestamps of all 41 millions users using Twitter API [START_REF]Twitter graph[END_REF] would be extremely slow: when we made our measurements (05/2014), an authorized Twitter account was limited to 350 API requests/hour so querying all the accounts would have taken 13 years. While this is one of the main reasons for designing good LiveRank, we still need a full crawl to build a ground truth. To overcome this obstacle, we worked around the API limitation by using a browser-like crawler to recover each user timeline as if a regular browser was connecting to Twitter front servers. This is possible because the timestamp of the last entry can easily be scrapped from the HTML structure of the returned documents. However, such an approach becomes much more difficult for complex queries and might also be detected and prevented by Twitter in the future.

Having tested all nodes, we found three main categories of users corresponding to those who (i) no longer exist, (ii) have no tweet at all and (iii) have tweeted at least once before the crawling time. Figure 1 shows the relative proportion of each category.

For users with at least one tweet, we extracted the timestamp of their last tweet. After considering the cumulative distribution of last-tweet timestamps, we arbitrarily decided to set the activity threshold to six months: a user is active if she has tweeted during the last six months. With these settings, we obtained a list of 7,300,399 (17.53%) active users, serving as ground truth for LiveRank evaluation.

Correlations

The rationale behind the LiveRanks I and P is the assumption that the activity of nodes is correlated to the graph structure of the snapshot, so that a node with high in-degree or PageRank has more chances to stay active.

To validate this, we plot in Figure 2 the cumulative distribution of in-degree (figure 2a) and PageRank (figure 2b) for alive, dead, and all pages of the uk-2002 dataset. We observe that the curve for active nodes is slightly shifted to the right compared to the other curves in each figures: active users tend to have slightly higher in-degree and PageRank than in the overall population. The bias is bigger for PageRank, suggesting that LiveRank (P) should perform better than Figure 3 presents the same results for the twitter-2010 dataset. While the curves are qualitatively similar, the bias comparison is not as clearly in favor of PageRank.

We will now measure how this bias impacts the cost function of corresponding LiveRanks.

LiveRanks evaluation

After having proposed several LiveRanks in Section 2 and described our datasets in previous Section, we can now benchmark our proposals.

All our evaluations are based on representations of the cost functions. In each plot, the x-axis indicates the fraction α of active nodes we aim to discover and the y-axis corresponds to the relative cost of the crawl required to achieve that goal. A low curve indicates an efficient LiveRank. Like said in Section ??: an ideal LiveRank would achieve a constant cost of 1; a random LiveRank is quickly constant with an average cost n/n a ; any non-clairvoyant LiveRank will tend to cost n/n a as α goes to 1.

Evaluation on Web Graphs

We mainly focus here on the uk-2002 dataset. Unless otherwise specified, the training set contains the z = 100000 pages of higher (static) PageRank.

Static and sample-based LiveRanks

We first evaluate the results of static and sample-based LiveRanks. The results are displayed in Figure 4. For static LiveRanks, we see as expected that a random ordering gives an almost constant cost equal to n na ≈ 15.6. Indegree ordering (I) and PageRank (P) significantly outperform this result, PageRank being the best of the three: it is twice more efficient than random for small α, and still performs approximately 30% better when up to α = 0.6. We then notice that we can get even much better costs with sample-based approaches, the double-adaptive LiveRank P +/a giving a significant improvement over the simple-adaptive one P a . P +/a allows improving the ordering by a factor of 6 approximately around α = 0.2 with a cost of 2.5 fetches per active node found. The cost for gathering half of the alive pages is less than 4, and for 90% it stays under 10. but similar results were obtained for P a . Figure 5a shows the impact of the size z of the sampling set (sampling the top PageRank pages). We observe some trade-off: as the sampling set grows larger, the initial cost increases as the sample does not use any fresh information, but it results in a significant increment of efficiency in the long run. For this dataset, taking a big training set (z=500 000) allows reducing the cost of the crawl for α ≥ 0.4, and maintains a cost less than 4 for up to 90%. Another key aspect of the sampling phase is the qualitative choice of the sample set. Using z=100 000, we can observe in Figure 5b that the performance of double adaptive P +/a is further improved by using a random sample set rather than selecting it according to the PageRank or by decreasing indegree. We believe that the reason is that a random sample avoids a locality effect in the sampling set as high PageRank pages tend to concentrate in some local parts of the graph. To verify that, we tried to modify Indegree and PageRank selection to avoid the selection of neighbor pages. The results (not displayed here) show a significant improvement while staying less efficient than using a random sample.

To summarize, double-adaptive LiveRank through random sampling seems to offer a very low cost, within a factor of 2 from optimal for a large range of values α. We then consider the performance of fully dynamic strategies, using the double-adaptive LiveRank with random training set as a landmark. The results are displayed in Figure 6a. We see that bread-first search BFS and active indegree AI perform similarly to double adaptive P +/a for low α and can outperform it for large α (especially BFS). BFS begin to significantly outperform double adaptive for α ≥ 0.5. However, if one needs to gather half of the active pages or less, double adaptive is still the best candidate as it is much simpler to operate, especially with a distributed crawler.

Additionally, Figure 6b shows the impact of different sampling sets on BFS and AI. Except for high values of α where a random sampling outperforms other strategies, the type of sampling does not seem to affect the two dynamic LiveRanks as much as it was observed for the double-adaptive LiveRank.

uk-2006 dataset

We have repeated the same experiments on the dataset uk-2006, where the update interval is only one year. Figure 7 shows the results for static and sample-based LiveRanks, using z=200 000 (because the dataset is larger) and random sampling. The observation are qualitatively quite similar to uk-2002. The main difference is that all costs are lower due to a higher proportion of alive pages ( n na ≈ 2.81). The double-adaptive version still gives the lower relative cost among static and sample-based LiveRanks, staying under 1.4 for a wide range of α.

Comparison with a site-based approach

To benchmark with techniques from previous work for finding web pages that been updated after a crawl, Figure 8 compares double adaptive P +/a to activesite first ASF with random sampling. The number of random pages tested in each site and the overall number of tests are the same for both methods. Note that given the budget z, it was not possible to sample small websites. Unsampled websites are crawled after the sampled ones.

We see that for α greater than 0.9, ASF performs like a random LiveRank. This corresponds to the point where all sampled website have been crawled. That effect aside, the performance of ASF is not as good as double-adaptive LiveRank for earlier α. In the end, ASF only beats P +/a for a small range of α, between 0.7 and 0.85, and the gain within that range stays limited.

Evaluation on Twitter

As discussed before, the Twitter graph has structural properties distinct from Web graphs. In this part we analyze how these differences affect the performance of LiveRanks. the other LiveRanks, including Indegree I. It indicates that if the intuition of some death propagation was relevant for Web graphs (it was a convenient way to spot dead web sites for instance), this is not the case for Twitter: the fact that followers become inactive does not seem to have an impact on the activity of the followees. In the end, the simple adaptive LiveRank P a has the best performance, closely followed by the static LiveRanks P and I. The three of them have a cost function that seem to grow roughly linearly between 2 and 4 as α goes from 0 to 0.6.

Static and sampled-based LiveRanks

Quantitative and qualitative impact of the training set

In Figure 10a, we vary the size of the training set, ranging from z =200 000 to z =1000 000. Results indicate that the cost function is almost not affected by z as long as it is high enough. Compared to the results observed on Web graphs, this means that taking a big training set: (i) will not burden the cost function for small α. This likely comes from the fact that the sampling set is PageRank-based by default, and the static PageRank is already close to the best LiveRank we can get; (ii) will not improve the performance for large α either, meaning that no significantly useful knowledge is obtained after some threshold. This relative independence with respect to z is another qualitative difference compared to Web graphs. Figure 10b shows the impact of training set types on simple adaptive LiveRank P a . Unlike Web graphs where random sampling dominates others, in social network the training set filled by PageRank is the best whereas the random seed is worse. This can be interpreted as a result of a weaker structural locality (i.e., no highly correlated clusters like web sites for Web graphs), so that activeness is more concentrated around important Twitter individual users that should be considered as soon as possible. In Figure 11a, we compare the simple adaptive PageRank P a with the dynamic LiveRanks. All of them are initialized with default values (PageRank sampling of size z =100 000). P a stays the best option: it is slightly better than AI and much more efficient than BFS. While for Web graphs, dynamics LiveRanks could still be preferred for some settings, it seems that in the context of Twitter it is never the case especially considering their deploiement complexity in a distributed crawler.

Dynamic LiveRanks

Lastly, Figure 11b indicates the impact of different training sets on the two dynamic LiveRanks. It confirms that the combination of AI and a PageRankordered training set gives the best results for that type of LiveRanks, which is still not enough to compete against P a .

Conclusion

In this paper, we investigated how to efficiently retrieve large portions of alive pages from an old crawl using orderings we called LiveRanks. We observed that PageRank is a good static LiveRank, which can be significantly improved by first testing a small fraction of the pages for adjustment in a sample-based approach.

Compared to previous work on identifying modified pages, our technique performs similarly for a given large desired fraction (around 80%) when compared to the LiveRank algorithm inspired by the technique in [START_REF] Cho | Effective change detection using sampling[END_REF]. However, outside that range, our method outperforms this technique. Interesting future work could reside in using our techniques for the problem exposed in [START_REF] Cho | Effective change detection using sampling[END_REF] (identification of pages that have changed) and compare with the Website sampling approach.

Another advantage of our technique is the possibility to be applied to more general types of structured networks, like Twitter. However, it seems that the choice of an appropriate LiveRank is closely related to the type of network.

Interestingly, we could not get significant gain when using fully dynamic Liv-eRanks. As noticed before, each of the two phases of the sample-based approach can be easily parallelized through multiple crawlers whereas this would be much more difficult with a fully dynamic approach. The sample-based method could for example be implemented with in two rounds of a simple map-reduce program whereas the dynamic approach requires continuous exchanges of messages between the crawlers.

Our work establishes the possibility of efficiently recovering a significant portion of the active nodes of an old snapshot and advocates for the use of an adaptive sample-based PageRank for obtaining an efficient LiveRank.

To conclude, we emphasize again that the LiveRank approach proposed in this paper is very generic, and its field of applications is not limited to Web graphs or Twitter. It can be straightforwardly adapted to any online data with similar linkage enabling crawling.

Figure 1 :

 1 Figure 1: Statistics of the twitter-2010 dataset

Figure 2 :

 2 Figure 2: Impact of liveness to Indegree/PageRank distribution for uk-2002.

Figure 3 :

 3 Figure 3: Impact of activity to Followers/PageRank for twitter-2010.

Figure 4 :

 4 Figure 4: Main results on static and sample-based LiveRanks (uk-2002)

  Impact of the selection of Z

Figure 5 :

 5 Figure 5: Impact of the training set (uk-2002)

  Random seed Alive Indegree -Top Indegree seed Alive Indegree -Top PR seed BFS -Random seed BFS -Top Indegree seed BFS -Top PR seed Ideal LiveRank (b) Impact of Z on dynamic LiveRanks

Figure 6 :

 6 Figure 6: Performance of dynamic LiveRanks (uk-2002)

Figure 7 :

 7 Figure 7: uk-2006 main evaluation results

Figure 9

 9 Figure 9 compares the static and sample-based LiveRanks. A first observation is that the double adaptive LiveRank P +/a performs very poorly compared to

Figure 8 :

 8 Figure 8: Comparison with active-site first LiveRank (uk-2002)

Figure 9 :

 9 Figure 9: Main results on static and sample-based LiveRanks (twitter-2010)

Figure 10 :

 10 Figure 10: Impact of the training set (twitter-2010)

  Random seed Alive Indeg -Top Indegree seed Alive Indeg -TopPR seed BFS -Random seed BFS -Top Indegree seed BFS -Top PR seed Idead LiveRank (b) Impact of Z on dynamic LiveRanks

Figure 11 :

 11 Figure 11: Performance of dynamic LiveRanks (twitter-2010)

Table 1 :

 1 Status of web pages in uk-2002, crawled in December 2013.

	starting

considered the last snapshot (05/2007) as "present time", setting the active set a(V ) as the intersection between the two snapshots. With this methodology, we hope to have a good approximation of a after a one-year period. For this dataset, we obtained n a = 11, 142, 177 "alive" nodes representing 35.56% of the graph.

We tested several other natural options and observed no significant impact.

http://law.di.unimi.it/webdata/uk-2002/

http://law.di.unimi.it/webdata/uk-union-2006-06-2007-05/

http://law.di.unimi.it/webdata/twitter-2010/

Acknowledgments The work presented in this paper has been carried out at LINCS (http://www.lincs.fr) and has been founded by the European project Reveal (http://revealproject.eu/).


Laetitia Giraldi

Pierre Martinon

Marta Zoppello

Optimal Design of the Three-link Purcell Swimmer

In this paper we address the question of the optimal design for the Purcell 3-link swimmer. More precisely we investigate the best link length ratio which maximizes its displacement. The dynamics of the swimmer is expressed as an ODE, using the Resistive Force Theory. Among a set of optimal strategies of deformation (strokes), we provide an asymptotic estimate of the displacement for small deformations, from which we derive the optimal link ratio. Numerical simulations are in good agreement with this theoretical estimate, and also cover larger amplitudes of deformation. Compared with the classical design of the Purcell swimmer, we observe a gain in displacement of roughly 60%.

The study of self-propulsion at microscopic scale is attracting increasing attention in the recent literature both because of its intrinsic biological interest, and for the possible implications on the design of bio-inspired artificial replicas reproducing the functionalities of biological systems (see for instance [START_REF] Lighthill | Mathematical biofluiddynamic[END_REF][START_REF] Brennen | [END_REF][3][4]). At this scale, inertia forces are negligible compared to the viscous ones i.e. low Reynolds number, calling for different swimming strategies than at greater scales. Thus, we assume that the surrounding fluid is governed by Stokes equations which implies that hydrodynamic forces and torques are linear with respect to the swimmer's velocity. In the case of planar flagellar propulsion , the Resistive Force Theory (RFT) provides a simple and concise way to compute a local approximation of hydrodynamic forces and Newton laws (see [5]). The resulting equations can be written as a system of linear ODEs (see [6][7][START_REF] Giraldi | Proc. 52th Conf. on Dec. and Contr[END_REF]). In this paper we focus on one of the first example of micro-swimmer model found in literature: the "three-link swimmer" [START_REF] Purcell | [END_REF]. This model is still attracting interest in recent studies, see [10,11]. The structure of the equations of motion leads to establish a connexion between geometrical control theory and micro-swimming (see [START_REF] Montgomery | A tour of subriemannian geometries, theirs geodesics and applications[END_REF]). In this paper, we address the optimal design issue, namely finding the optimal length ratio between the three links which maximizes displacement of the swimmer. A similar issue has been studied in [START_REF] Tam | [END_REF] where a Fourier expansion is used to derive an optimal design. Here, techniques from the control theory are used to approximate the leading order term of the swimmer's displacement. Maximizing this leading term gives a theoretical value for the optimal link ratio. As far as we know, this procedure is original in that context, and could be applied to others models such as the three-sphere swimmer (see [14]).

The paper is organized as follows. Section I recalls the equations of motion for the Purcell swimmer. Section II presents strokes which maximize the x-displacement, based on previous simulations from [START_REF] Giraldi | Proc. 52th Conf. on Dec. and Contr[END_REF]. Section III details the expansion of the displacement for such strokes at small amplitude. By maximizing the leader term of this expansion, we derive an optimal length ratio. Section IV shows the numerical simulations whose results are consistent with this theoretical ratio, for both small and large amplitude of deformation.

I. MODELING

Purcell's 3-link swimmer. The 3-link swimmer is modeled by the position of the center of the second stick x = (x, y), the angle θ between the x-axis and the second stick (the orientation of the swimmer). The shape of the swimmer defined by the two relative angles β 1 and β 3 (see Fig 1). We also denote by L and L 2 the length of the two external arms and central link. Dynamics via Resistive Force Theory. We approximate the non local hydrodynamic forces exerted by the fluid on the swimmer with local drag forces depending linearly on the velocity. We denote by e i and e ⊥ i the unit vectors parallel and perpendicular to the i-th link, and we also introduce v i (s) the velocity of the point at distance s from the extremity of the i-th link, that is

v 1 (s) = ẋ - L 2 2 θe ⊥ 2 -s( θ -β1 )e ⊥ 1 , s ∈ [0, L], v 2 (s) = ẋ -(s - L 2 2 ) θe ⊥ 2 , s ∈ [0, L 2 ], v 3 (s) = ẋ + L 2 2 θe ⊥ 2 + s( θ -β3 )e ⊥ 3 , s ∈ [0, L].
The force f i acting on the i-th segment is taken as

f i (s) := -ξ v i (s) • e i e i -η v i (s) • e ⊥ i e ⊥ i , (1)
where ξ and η are respectively the drag coefficients in the directions of e i and e ⊥ i .

Neglecting inertia forces, Newton laws are written as

F = 0 , e z • T x = 0 , ( 2
)
where F is the total force exerted on the swimmer by the fluid,

F = N i=1 Li 0 f i (s) ds , (3)
and T x is the corresponding total torque computed with respect to the central point x,

T x1 = N i=1 Li 0 (x i (s) -x 1 ) × f i (s) ds . ( 4
)
Since the f i (s) are linear in ẋ, θ, β1 , β3 , the system (2) can be rewritten as

A(z) • ẋ θ -B(z) • β1 β3 = 0, (5)
where z(t) := (β 1 , β 3 , x, y, θ)(t) T . The matrix A is known as the "Grand Resistance Matrix" and is invertible (see [6]). Then the dynamics of the swimmer is finally expressed as an ODE system

ż(t) = f (z, β1 , β3 ) = g 1 (z(t)) β1 (t) + g 2 (z(t)) β3 (t) , (6)
where g 1 (z) g 2 (z) :=

I 2 A -1 (z)B(z)
with I 2 the 2×2 identity matrix. The literal expression of the g i is quite complicated (several pages).

II. OPTIMAL STROKES

Optimal control problem. We are interested in finding a periodic sequence of deformations which maximizes the displacement of the swimmer along the x-axis. More precisely, we optimize both the link length ratio L 2 /L and the deformation of the swimmer over time. Taking the deformation speed β1|3 as control functions, we obtain the optimal control problem (OCP )

                 max x 2 (T ) s.t. ż(t) = f (z(t), β1 , β3 ) ∀t ∈ [0, T ] , β1|3 ∈ U = [-b, b] ∀t ∈ [0, T ] , β 1|3 (t) ∈ [-a, a] ∀t ∈ [0, T ] , x 2 (0) = y 2 (0) = θ 2 (0) = 0, y 2 (T ) = θ 2 (T ) = 0 , β 1|3 (0) = β 1|3 (T ), 2L + L 2 = c.
We set the constraints a and b over the amplitude and deformation speed, as well as the total length c of the swimmer. The final time T is fixed, and the constraint β 1|3 (0) = β 1|3 (T ) ensures that the swimmer is in the same configuration at the initial and final time. Note that this condition can be satisfied by either a single stroke or a sequence of strokes. From [START_REF] Giraldi | Proc. 52th Conf. on Dec. and Contr[END_REF], numerically solving (OCP ) typically gives a periodic sequence of identical strokes. Their phase portrait is octagonal, as illustrated on Fig. 2, and we will detail how this shape is consistent with optimal control theory.

Pontryagin's Maximum Principle (PMP). We recall here the PMP as it gives some insight on the shape of optimal strokes. This theorem in optimal control introduced by Pontryagin et al. in [15] gives necessary conditions for local optimality. Interested readers can find more information on the PMP in [START_REF] Agrachev | Non linear and optimal control theory[END_REF][START_REF] Trelat | Contrôle optimal : théorie and applications[END_REF]. The PMP is characterized by an Hamiltonian function H that formally depends on the state variables z, the control functions β1|3 , and so-called co-state variables noted p. While originally inspired by the Hamiltonian in mechanics, in the context of optimal control H does not actually correspond to the energy of the system. The co-state variables play the part of the generalized velocities in Lagrangian mechanics, and they can be interpreted as Lagrange multipliers (in the sense of constrained optimization) related to the dynamics of the system. Let the Hamiltonian be

H(z, p, β1 , β3 ) = p, g 1 (z) β1 + p, g 2 (z) β3 . ( 7
)
Under the assumption that g 1|2 are continuous and C 1 with respect to z, the PMP states that: Symmetries. As stated in [START_REF] Tam | [END_REF], we expect optimal strokes to be symmetric with respect to the diagonal axes β 1 = β 3 and β 1 = -β 3 . This comes from the equations of motion being linear and time independent. From the linearity, optimal strokes should be invariant by reflection with respect to the axis of the swimmer's body. From time independence, the stroke should be invariant when inverting the arms movement and going backwards in time.

if (z * , β * 1 , β * 3 )

III. OPTIMAL SWIMMER DESIGN

In this section, we express the leader term of the swimmer's displacement for a stroke of small perimeter which satisfies all properties stated in the previous section. We represent the stroke by a closed octagonal curve γ in the phase portrait (β 1 , β 3 ), see Fig. 2. As a consequence of neglecting inertia forces, velocities appear linearly in the dynamic, and time can be rescaled without changing the dynamics. Thus the displacement of the swimmer after one stroke does not depend on the speed along the curve γ, but only on the shape of the stroke. From now on, we parametrize γ by the arc-length s. Using a similar approach to [START_REF] Coron | Control and Nonlinearity[END_REF], we express the swimmer's displacement along the x-axis (i.e., x(T ) -x(0)) as an asymptotic expansion for small length a

i , i = 1, • • • , 4.
Displacement over the arc s ∈ [0, a 1 ]. On this part, according to Fig. 2, we set u = ( β1 , β3 ) = (0, -1). The dynamics of the swimmer is therefore given by ż = -g 2 , and the time expansion at order two is given by

z(a 1 ) = z(0) -a 1 g 2 (z(0)) + a 2 1 2 ∂g 2 ∂z z(0) (g 2 (z(0))) + o(a 3 1 ) . ( 8
)
Displacement over the arc s ∈ [a 1 , a 1 + a 2 ]. Similarly, the position of the swimmer at s = a 1 + a 2 can be expressed as

z(a 1 + a 2 ) =z(a 1 ) - a 2 √ 2 2 h(z(a 1 )) + a 2 2 4 ∂h ∂z z(a1) (h(z(a 1 ))) + o(a 3 2 ) , ( 9
)
where h := g 1 + g 2 . Plugging the value of z(a 1 ) from ( 8) into ( 9) and neglecting the terms of order greater than two, we get

z(a 1 + a 2 ) =z(0) + c 1 (g 1 , g 2 , z(0), a 1 , a 2 ) +c 2 (g 1 , g 2 , z(0), a 1 , a 2 ) +o(a 3 1 ) + o(a 3 2 ) (10)
with

c 1 (f , g, z, a 1 , a 2 ) =- √ 2a 2 2 f (z) +(-a 1 - √ 2a 2 2 )g(z), c 2 (f , g, z, a 1 , a 2 ) = a 2 2 4 ∂f ∂z z (f (z)) + a 2 2 4 ∂g ∂z z (f (z)) + a 1 a 2 √ 2 2 + a 2 2 4 ∂f ∂z z (g(z)) + a 1 a 2 √ 2 2 + a 2 2 4 + a 2 1 2 ∂g ∂z z (g(z)) .
Displacement over the complete stroke. Iterating the computations along each arc and noting by P = 2(a 1 + a 2 + a 3 + a 4 ) the stroke perimeter, the expansion of the total displacement for the octagonal stroke is finally obtained as

z(T ) -z(0) = C [g 1 , g 2 ](z(0)) + o(a 3 i ) i=1-4 , (11)
where

C = a 1 a 2 √ 2 2 +a 1 a 3 + a 2 a 3 √ 2 2 + a 1 a 4 √ 2 2 +a 2 a 4 + a 3 a 4 √ 2 2 and [g 1 , g 2 ](z(0)) = ∇g 2 (z(0))•g 1 (z(0))-∇g 1 (z(0))•g 2 (z(0))
is the Lie brackets of g 1 and g 2 at point z(0). Choosing the starting point z(0) such that θ(0) = β 1 (0) = β 3 (0) = 0, we compute the Lie bracket with a formal calculus tool

[g 1 , g 2 ](0, 0, x, y, 0) =       0 0 η-ξ ξ L 3 L2(3L+2L2) (2L+L2) 4 0 0       . ( 12
)
Consequently, the x-displacement after one stroke is approximated by

∆x ∼ C η -ξ ξ L 3 L 2 (3L + 2L 2 ) (2L + L 2 ) 4 + o(a 3 i ) i=1-4
(13) Setting the total length of the swimmer by a constant equal to c, i.e., 2L + L 2 = c, we find that (13) has a unique maximum at

L * = c 1 - 2 5 , L * 2 = c 2 2 5 -1 , ( 14
)
which gives an optimal ratio of

L 2 L * = √ 10 -1 3 ∼ 0.721 . ( 15
)
Remark: in [START_REF] Tam | [END_REF] an optimal ratio of 0.747 is given for an efficiency-type criterion. The small gap may be due to the difference in models, or the change of the objective function.

IV. NUMERICAL SIMULATIONS

We solve now the optimal control problem (OCP ) numerically, in order to determine the optimal swimming strategy and link ratio. Simulations are performed with the toolbox Bocop ( [START_REF] Bonnans | Bocop -A collection of examples[END_REF]) that implements a direct transcription method. This approach uses a time discretization to transform the continuous (OCP ) into a finite-dimensional optimization problem (nonlinear programming). We refer interested readers to [START_REF] Betts | Practical Methods for Optimal Control Using Nonlinear Programming[END_REF] for more details on these methods. We use here an implicit midpoint discretization with 100 to 2500 time steps. Note that this method does not use the PMP.

As stated in (OCP ), the criterion is to maximize the total displacement along the x-axis over a fixed time T . The initial state of the swimmer is set as x(0) = y(0) = θ 2 (0) = 0, with the final conditions y(T ) = θ 2 (T ) = 0. The initial shape angles are left free, with the periodicity conditions β i (0) = β i (T ), i = 1, 3. We set the total length c = 4 for an easier comparison with the classical Purcell swimmer (L = 1, L 2 = 2).

We explore different values for the bounds a, b on the shape angles and deformation speed and see their influence on the optimal stroke and link ratio. For practical applications, the values for a and b should reflect the physical characteristics of the studied swimmer. It should be pointed out that the period of the optimal stroke is not known a priori. We arbitrarily set T = 1 in the first set of simulations, and T = 25 when studying the larger amplitudes. In the latter case we find that the swimming strategy consists in a periodic sequence of identical strokes, as previously observed in [START_REF] Giraldi | Proc. 52th Conf. on Dec. and Contr[END_REF].

A. Small amplitudes, influence of speed limits

We start with small amplitudes by setting a = π/20 and solve (OCP ) for different values of the speed limit b. Here we set T = 1 and use 250 time steps for the discretization. Optimizations take about one minute on a standard laptop. Results are given in Table .I, with the phase portraits for the shape angles β 1 , β 3 on Fig. 3.

First, we observe that the optimal ratio L 2 /L is very close to its theoretical value of 0.721 from (15), regardless of b. The speed bound does however have an influence on the shape of the optimal stroke, and its displacement. Displacement increases with higher speeds, and we find the following empirical relation between b and the stroke shape, confirmed by simulations with other values of a: -for b < 4a/T : diamond stroke, which touches the bound a for the limit case b = 4a/T . -for 4a/T < b < 8a/T : octagonal stroke.

-for b = 8a/T : classical Purcell stroke (square).

-for b > 8a/T : sequence of several strokes. The three strokes observed (diamond, octagon, square) match the discussion from Section II. They include only diagonal lines (bang arcs saturating the speed limit b) and horizontal/vertical lines (constrained arcs for the amplitude limit a). Note also that the square and diamond strokes are particular cases of the octagonal one, by setting the appropriate arc lengths to 0.

Remark: this empirical relation can also be interpreted in terms of the period T , with the two limit values T = 8a/b for the Purcell stroke and T = 4a/b for the diamond touching a.

B. Comparison with the classical Purcell swimmer

Now we compare the performance of the optimal swimmer with respect to the classical Purcell swimmer defined by L = 1, L 2 = 2, meaning a ratio of 2. For this comparison we set a = π/6 (thus a stroke amplitude of π/3) and b = π/3, 2π/3, π, 4π/3 and T = 1. The optimization for the Purcell swimmer is done by setting L = 1 instead of letting it free. The results are summed up in Table .II and Fig. 4. We see that the shape of the stroke matches the empirical law, and that the optimal link ratio stays close to its theoretical value. We also observe a consistent gain in displacement that seems to increase with the speed limit, up to 64% for the classical Purcell stroke (square).

C. Large amplitudes, influence of angle limits

Now we study the influence of the maximal amplitude of the stroke, set by the bound a. In this last part we set the deformation speed limit b = 1 to focus on the amplitude. Since we would like to study only the true optimal strokes, whose period is not known, we also take a longer final time T = 25. We expect to obtain trajectories that exhibit a sequence of several identical strokes with a period T * < T . The number of time steps is raised accordingly to 2500, which increases the computational time up to half an hour. Another way of finding the optimal stroke directly could be to leave the final time T free in the optimization, while maximizing the average speed of the stroke x(T )/T instead of the displacement x(T ).

The results are illustrated in Table .III and Figs. 56. First, the simulations confirm that the optimal strategy is a periodic sequence of identical strokes. The shape of the optimal stroke is always octagonal until it becomes unconstrained for very large values of a. We observe that the central symmetry observed for small amplitudes is lost for larger a, however symmetry w.r.t both diagonal axes still holds as expected.

In the unconstrained case, we see arcs that are neither bang arcs (diagonal) or constrained arcs (horizontal/vertical), but rather appear as smooth curves (see Fig. 5) . These are characteristic of so-called singular arcs, namely the case where p, g i (z) = 0 in the PMP. More details on the analysis of singular arcs can be found in [START_REF] Trelat | Contrôle optimal : théorie and applications[END_REF], unfortunately here the complexity of the g i makes further study quite difficult.

The total displacement x(T ) increases with a, first almost linearly when a < π/3 (see Fig. 6). From a ≈ 1.95 and above, we obtain the same, unconstrained solution. The improvement in displacement appears to be marginal between a = π/3 and the unconstrained case. Note that since the displacement is expected to be a monotone increasing function of a, we see that for a = 1.5, the optimization converged to a local solution.

The optimal ratio L 2 /L shows a steady decrease with a, starting quite close to the value 0.721 computed for small amplitudes, the seemingly reaching a limit value of 2/3 in the unconstrained case (i.e. L = 1.5, L 2 = 1). We recall that the classical Purcell swimmer has a link ratio of 2 (L = 1, L 2 = 2).

V. CONCLUSION

This study is devoted to the optimization of the link ratio of the three-link swimmer for maximal displacement. We provide an estimate of the displacement based on an expansion for small deformations, which gives a theoretical optimal link ratio. Numerical simulations are consistent with this theoretical ratio for small amplitudes of deformation. We also observe optimal ratio changes for large amplitudes of deformation, with a limit value of 0.667 in the unconstrained case versus a theoretical ratio of 0.721 obtained for small amplitudes of deformation. For an amplitude of π/3, the displacement gain is about 60% compared with the classical Purcell swimmer design. A possible continuation of this work is the comparison of different objective functions, such as speed or efficiency.

2 LFigure 1 .

 21 Figure 1. Purcell's 3-link swimmer.

  is a solution of (OCP ) then there exists p * = 0 absolutely continuous such that ż * = H p (z * , p * , β * 1 , β * 3 ), ṗ * = -H z (z * , p * , β * 1 , β * 3 ), p * (T ) is orthogonal to the cotangent cone of the final conditions at z * (T ) and ( β * 1 , β * 3 ) maximizes the Hamiltonian for almost every time t ∈ [0, T ]. Bang arcs. The Hamiltonian in (7) is linear in the controls β1|3 . If we assume p, g i (z) = 0 for i = 1, 2 over a time interval, then the optimal control β1|3 * that maximizes H must be on the boundary of U = {(-b, -b), (-b, b), (b, -b), (b, b)}. In terms of phase portrait, this corresponds to diagonal lines. Constrained arcs. Moreover, we have the constraints on the joint angles β 1|3 (t) ∈ [-a, a]. When one of them is active and |β i | = a, the corresponding control βi = 0. In terms of phase portrait, this gives horizontal or vertical lines.

Figure 2 .

 2 Figure 2. (Color online) Phase portrait (β1, β3) of the octagonal stroke considered for the expansion of the displacement.

Figure 3 .

 3 Figure 3. (Color online) Phase portraits of the strokes for small amplitudes, a = π/20. The shapes observed are consistent with the discussion in section II.

Figure 4 .

 4 Figure 4. (Displacement for the optimal/Purcell swimmer.

Figure 5 .

 5 Figure 5. Larger amplitudes -Phase portrait (each trajectory consists in several superposed strokes).

Figure 6 .

 6 Figure 6. Larger amplitudes -Overall displacement. For a = 1.5 the optimization converged to a local solution, since displacement is expected to be an increasing function of a.

Table II .

 II Optimal swimmer vs Purcell swimmer.

		b	x(T) L2/L	stroke x P urcell (T ) gain
		pi/3 1.17E-2 0.717 diamond 7.373E-3		51%
		2π/3 4.57E-2 0.708 diamond 2.848E-2		60%
		π	7.82E-2 0.699 octagon 4.806E-2		63%
		4π/3 8.80E-2 0.695 square 5.359E-2		64%
		0.09
		0.08
		0.07
		0.06
	x(T)	0.04 0.05
		0.03
		0.02
						OPTIMAL SWIMMER
		0.01				PURCELL SWIMMER
		1 0	1.5	2	2.5	3	3.5	4	4.5
						b

Table III .

 III Larger amplitudes: optimal link ratio and stroke. Solutions become unconstrained about a = 1.95.

	a	x(T) L2/L	stroke
	π/20 0.192 0.719	octagon x26
	π/10 0.384 0.712	octagon x13
	π/6 0.593 0.697	octagon x7
	0.75 0.811 0.676	octagon x5
	π/3 1.088 0.660	octagon x4
	1.25 1.266 0.660	octagon x4
	1.5 1.263 0.660	octagon x3
	1.75 1.329 0.667	octagon x3
	2π/3 1.335 0.667 unconstrained x3
	2.5 1.335 0.667 unconstrained x3