Laurent Laurent

Ott Ott

QuickRanking: Fast Algorithm For Sorting And Ranking Data

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

QuickRanking: Fast Algorithm For Sorting And Ranking Data QuickRanking is an algorithm that allows in a same processing, to sort the data and to return their ranking, that is to say their rank in the sorting.

For faster processing, QuickRanking does not move data, but stores for each data, where the following data is. This method is explained in annex 1. The source code written in VBA is in annex 2.

To evaluate the effectiveness of QuickRanking, I have reproduced at annex 3 the source code for QuickSort, and in annex 4 an "enriched" version of QuickSort, called QuickSort_AndRank, which like QuickRanking, does not move the data directly but moves the references of the indices of the data. Hence a gain of time on the processing of the voluminous alphanumeric data because we move integers of 4 bytes and no more strings of character of varying lengths. This requires additional memory capacities, but therefore allows to use these reference tables to return an order of classification in addition to the sorting, just as QuickRanking does.

I have compared these three algorithms -QuickSort, QuickSort_AndRank, and QuickRanking -on lists of random data; the results are synthetised in a table in annex 5. My analysis is the following:

If the classification order is not necessary: -Sorting of digital data: QuickSort is the fastest algorithm except when the data at the beginning of the list are already classified, or if the minimum or maximum value is often represented. In these cases, QuickRanking takes the advantage. -Sorting of alphanumeric data: the more the number of characters of the data to be sorted is important, the more the algorithms work by reference, QuickSort_AndRank and QuickRanking, are effective. QuickSort must only be used if the memory capacity does not allow to use the other two algorithms which require more resources.

If the classification order is necessary:

-Sorting and classification of digital data: QuickSort_AndRank is more efficient than QuickRanking only on large lists of data. QuickRanking takes the advantage in other cases. Advantage emphasised when the data at the beginning of the list are already classified, when the list is made up of few different values, or when the minimum or maximum value is often represented. -Sorting and classification of alphanumeric data: QuickRanking is faster than QuickSort_AndRank. Advantage emphasised on the processing of large chains of characters.

Conclusion: ideally random list or highly classified list, large data or reduced size data, numeric or alphanumeric data, the reality is often between these extremes. In practice, QuickRanking may provide an interesting alternative to QuickSort...

Remarks:

-QuickRanking offers optional complementary analyzes to accelerate the processings on the lists where the data have many equalities, or when data are following. This option has not been used in the tests because they are based on random data. Annex 6 presents a function that determines, after analysis of a sample of data from the list, whether or not to enable this option.

-QuickRanking also allows you to reverse only the order of classification, without sorting all the data, which reduces the processing time. This method is useful for instance when you are looking for the first 10 elements of a list, or the nth item. However, the equalities are not managed in this method.

-The attached Excel file takes up these algorithms.

-In the tests presented, QuickSort and QuickSort_AndRank use a fixed pivot.

-The tests were done on a PC office automation in VBA in EXCEL. The results are given for information; the objective is to bring out a trend. These results need to be confirmed in other programming languages and with other operating systems. I am looking for volunteers, if you are tempted by the adventure: Laurent.ott8@orange.fr -Thanks to Christiane Bonin and Patrick for this translation.

Item : 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 5 90 Item : 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 5 90 Next item : 1 x Item : 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 5 90 Next item : 2 x 1 Item : 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 5 90 Next item : 2 4 1 0 x Annex 1: The operation principle of the algorithm QuickRanking Let's sort the 12 data in the table below to understand this sorting method, which to save processing time, does not move data, but stores for each date where the following data is:

Let us analyze the first two elements: Here we know that the item 0, which is worth 3, is the minimum value, and the item 1, which is worth 9, is the maximum value. Therefore the item following the item 0 is the item 1. We can store this information:

To simplify the reading of the table, the minimum value is represented in green and the maximum value is in orange.

To classify the item 2, which is worth 5: We read the minimum value, the item 0. The value 3 is less than 5, therefore we read the next item, the item 1, which is worth 9. Too large this time. Therefore 5 becomes the value that will follow 3 and 9 will be the value that follows 5. Which updates our table of "next item": Let's classify the item 3 which is worth 2, lower value to our former minimum value which was the item 0 of value 3. Therefore an exchange is made. And the item 0 will be the value which will follow the item 3. No change for the other data already analysed:

These arrows indicate the reading order of the table starting from the minimum reference, and in reading the "next item".

Let us go to item 4 which is worth 15, value superior to our old maximum value, the item 1 which is worth 9. Therefore an exchange is made. The item 4 will be the value which will follow the item 1. No change for the other data already analysed: 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 5 90 Next item : 2 x 1 0 Item : 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 5 90 Next item : 2 4 5 0 x 1 Item : 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 The item 5 is worth 7, superior value to our minimum value of reference item 3, which is worth 2. Therefore we read the next item, the item 0, which is worth 3. Always less than 7, so we read the next item: item 2, which is worth 5. We continue with the next item, 1, which is worth 9. This time we can break out of the loop and update the "Next item": the item following the figure 7 is therefore the item 1, and the new "next item" to the item 2 is no more 1 but 5: Same principles to classify the item 6 which is worth 8: After reading the values from the table starting from the minimum value item and using the "next item", we find that it is located between the item 5 which is worth 7 and the item 1 which is worth 9. Therefore its "next item" is the item 1, and "next item" of the item 5 is modified: 1 is replaced by 6.

Item :
Note: here a shortcut is possible to quickly sort the item 6. Actually 8 is superior or equal to the last value analysed, which was worth 7, and is inferior or equal to the value of the next item of the last value analysed, which is worth 9. Therefore the next item of the item 6 is the next item of the last value analysed. And the next item of the last value analysed becomes the item 6. This test is very efficient on the partially sorted lists or if there are many equalities, but is counter-productive on random lists. That is why this test is optional in QuickRanking in order not to run it on lists of data that you know being random, and thus save the processing time. Annex 6 presents a function that determines, after analysis of a sample of data from the list, whether or not to enable this option.

Continue the classification and if you get this table, is that you have understood:

To read the data in ascending order, it must be from the minimum reference, the item 9, the 0, and read the "next item ": item 3, which is worth 2, the item 0 which is worth 3, the item 2 which is worth 5, and so on... The data is sorted without any movement is made. Only problem: to know the classification of an element, it sometimes takes many readings. For example, to classify the item 12 which is worth 10, here is the path followed, either 8 readings, to find that the item 1 is the last inferior item:

You guess that with a table of several hundreds of elements, certain values to classify will require a number of impressive reading ... which soars the processing time.

Item : 9 3 0 2 10 5 6 1 4 8 7 11 Value : 0 2 3 5 5 7 8 9 15 17 20 90 Item : 9 3 0 2 10 5 6 1 4 8 7 11 Value : 0 2 3 5 5 7 8 9 15 17 20 We must arrive at a good compromise so that the time spent to generate this table, is profitable by the time gained by dichotomy research. I have adopted the principle to update the table when the number of readings of the "next item" is equivalent to the number of processed data.

A mathematical analysis should allow to find the formula for an optimal generation. I am open to your proposals.

Very Important Note : The search algorithm of dichotomous QuickRanking is different from conventional algorithms based on a loop of type " Do ... Loop While beginning ≤ end ", including a condition of equality to break out prematurely of the loop when the value sought is found.

To speed up processing QuickRanking proceeds in two steps:

-The first step is a loop " For… next " made of a number of times inferior to the number calculated by the formula Log(n) / Log(2) which gives the maximum number of loop that will have to be done to find the solution in a dichotomous search. This is sufficient to approach the solution. -The second step is a loop that runs from the last inferior solution and which, this time, researches the exact solution.

This approach allows you to limit the number of conditional tests, which are time-consuming processing, and, most important, allows QuickRanking to be faster than if it used a conventional dichotomous research.

Item : 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 5 90 Next item : 2 4 10 0 8 6 1 11 7 3 5 x Item : 0 1 2 3 4 5 6 7 8 9 10 11 Value : 3 9 5 2 15 7 8 20 17 0 5 QuickRanking sorts the data, but also returns a rank order.

Let's go back to the table already seen:

The reading of the next items gives the sorting of the elements: 0, 2, 3, 5, 5, 7, 8, 9, 15, 17, 20, 90. This reading also allows to obtain the rank order of the elements:

The first element is the item 9. In an annexed table that serves as a ranking order, we put 1 for the item 9.

The following item is item 3, we put 2 in the rank order of the item 3.

The following item is item 0, we put 3 in the rank order of the item 0. And so on to obtain this table :   The item 0 is worth 3, it is the 3 rd element of the sorted list.

The item 1 is worth 9 it is the 8 th element of the sorted list. The item 2 is worth 5 it is the 4 th element of the ordered list... Inversely, you can know the value of the nth element of a list: List(rank(n)) List(rank( 9)) = 15. The 9 th item in the list is worth 15.

The rank order is convenient to fill a table of this type: Annexe 5 : Comparison of the three algorithms.

Annex 6: analysis of a sample of the data in the list allows you to determine whether or not to enable the option of additional tests.

QuickRanking offers optional complementary analyses to accelerate the processing, based on the last analysised item -research of series and duplicates for immediate processing, research of series non-contiguous for a rapid update of the table of already classified items. These analyses are performing with partially classified lists or if there are many equalities, but are counterproductive with random lists. That is why these analyses are optional in QuickRanking in order not the run on lists of data that you know they are random, and thus save processing time.

The dilemma thus arises when you do not know in advance if the list of data to sort will be or not random lists.

Because in some cases activating the option will speed up incredibly the processing or, on the contrary will slow it down.

The solution I suggest, is to take at random a sample of data from the list, and analyse it with the selected option. QuickRanking will feed in his argument taken by reference, TauxTest, the rate of successful tests. If this number represents a significant percentage, in the TauxConformite argument of the function, it can be estimated that it must activate the option.

The larger the sample size, the more the test will be representative, but the longer time it will take. Thus, I have limited the size of the sample to 3% of the size of the original list. Conversely if the sample is less than 20 items, it is considered non-significant and the function reverses True without making a test. By default the size of the sample is 1/1000 of the list.

Annexe 3 :

 3 The Quicksort algorithm C.A.R. Hoare You can optimize this algorithm for processing digital data by replacing the variable declarations "Variant" with "Long".Annexe 4 : The QuickSort_AndRank algorithm (based on the Quicksort algorithm)To return a ranking order.

  To save time, an already classified data table must be kept: Which allows you to make a dichotomous search to find the closest value of the element that we want to classify, which is worth 10, in only 4 readings:This method takes all its power on a very large table. For example, on a table of 10,000 elements, 14 readings only allow you to find the searched item, or approximately Log (n) / Log (2), where n is the number of elements in the table. A comparison with the hundreds of required readings by reading one by one "next item".

		90
	Item :	5 6 1 4 8 7 11
	Value :	7 8 9 15 17 20 90
	Item :	5 6 1
	Value :	7 8 9
	Item :	6 1
	Value :	8 9

The generation of this data table already classified being time consuming, it will be carried out from time to time. But even incomplete, this table allows you to move rapidly to the nearest item and then go on to a regular processing by reading the "next item" one by one, until you find the correct item. Consider this table as a shortcut to quickly arrive close to the final destination, and not necessarily to the final destination.

  : the data equal have the same order Method 2 : order data equal respect the original order. Method : does not return sorting data but only the ranking without management equalities. (A1) : Comparison of ranking without sorting between Quicksort and QuickSort_AndRank. (A2) : Comparison of ranking without sorting between Quicksort and QuickRanking (B) : Comparison between QuickRanking and QuickSort_AndRank : B0 = Sorting without ranking, B1 = Sorting and ranking method 1, B2 = Sorting and ranking method 2, B3 = ranking only method 3. Quick Ranking does not use the additional analysis option. This option is not useful on random data.

	1,000,000 alphanumeric of 1 to 250 chars 13,59 8% Method 1 QuickSort 100,000 alphanumeric of 1,000 chars 1,92 13% Sorting Without Ranking
	71%	26%
	1,70	12,53
	1,74 1,78	12,81 13,11					QuickSort_AndRank
	1,32	11,18
	1,12 -34%	10,75 -14%		Ranking	Without	Sorting
	1,17 -33% 1,18 -34%	11,44 -11% 11,53 -12%	-12%	Method 1 Method 2	ranking ranking	Sorting and Sorting and	QuickRanking
	0,72 -45%	9,28 -17%	4,16 -16%	Méthod 3		Ranked only

Item : 0 1 2 3 4 5 6 7 8 Value : 8 8 9 8 10 8 8 10 5 Next item : 1 2 4 0 7 3 5 x 6 Rank : 5 6 7 4 8 3 2 9 1 Item : 0 1 2 3 4 5 6 7 8 Value : 8 8 9 8 10 8 8 10 5 Next item : 1 2 4 0 7 3 5 x 6

Rank : 2 2 7 2 8 2 2 8 1

Item : 0 1 2 3 4 5 6 7 8 Value : 8 8 9 8 10 8 8 10 5 Next item : 1 2 4 0 7 3 5 x 6

Rank : 2 3 7 4 8 5 6 9 1

But the exercise may be more complicated in some cases, as in the table below:

The elements of value 8, item 0, 1, 3, 5 and 6, have an inconsistent ranking order. Nothing can justify that the item 6 is ranked 2nd whereas the item 5 is ranked 3 th .

In practice, either we attribute the same ranking to all equal values (Method 1):

Here there is a first, and 5 second ex-aequo. The element of value 9 (item 2) is 7 th.

Either we keep the original order to classify the equal values (Method 2):

Here each element has a separate row. There is no exaequo even for the elements of the same value. In case of equality, it is the element at inferior item that is prioritised.

QuickRanking can manage both ranking methods, as well as the ascending or descending order.

The function accepts four arguments, in addition to sort the table :  -OrdreCroissant (Ascending order) : If it is True, the sorting is done by ascending order. If it is False, the sorting is descending. -ModeClassement (ranking mode) indicates the ranking mode to return: 0 for no ranking. The data are sorted only.

1 to classify the data by applying the same rank to equal data. 2 to classify the data by assigning a different rank to equal data, respecting their original position.

3 to return the ranking, without sorting the data or managing any equality. 4 to return the data list without duplicates. The data are sorted but are not ranked -NiveauTest, (level test) determines whether or not to perform additional testing, to accelerate the processings on the lists where the data have many equalities, or when the data follow, see annex 6.

If it is worth -1 (or True), additional tests are performed.

If it is worth 0 (or False), no additional test is performed.

If it is worth between 1 and 100: a sample of the data is analysed by activating additional tests. If these tests prove successful, that is to say that the success rate is higher than in past argument NiveauTest, then the option will be enabled (the argument then takes the value -1). -TauxTest, (rate test) will contain the percentage of effective additional tests (integer between 0 and 100). This argument is used by the "TesterNiveauQR" function to test whether or not to activate the option of additional tests. In principle this argument is not used in the regular calls to the function, except perhaps by curiosity.

By default, QuickRanking sorts the data in ascending order and rank them by applying the same rank to equal data (Method 1). The option of additional testing is activated when the efficiency rate is at least 15 %. ACM 4, 321-322, 1961.

QuickSort_AndRank (based on the Quicksort algorithm): Laurent Ott QuickRanking: Laurent Ott


Emmanuel Jacob

Peter Mörters

The spread of infections on evolving scale-free networks

We study the contact process on a class of evolving scale-free networks, where each node updates its connections at independent random times. We give a rigorous mathematical proof that there is a transition between a phase where for all infection rates the infection survives for a long time, at least exponential in the network size, and a phase where for sufficiently small infection rates extinction occurs quickly, at most like the square root of the network size. The phase transition occurs when the power-law exponent crosses the value four. This behaviour is in contrast to that of the contact process on the corresponding static model, where there is no phase transition, as well as that of a classical mean-field approximation, which has a phase transition at power-law exponent three. The new observation behind our result is that temporal variability of networks can simultaneously increase the rate at which the infection spreads in the network, and decrease the time which the infection spends in metastable states.

Introduction

The spread of disease, information or opinion on networks has been the concern of extensive research over the past decade. Beyond a large body of empirical research and simulation studies there is now also a growing number of analytic results, based on relatively simple mathematical models of the network and the spreading mechanism [START_REF] Durrett | Some features of the spread of epidemics and information on a random graph[END_REF][START_REF] Danon | Networks and the epidemiology of infectious disease[END_REF][START_REF] Kiss | Modelling approaches for simple dynamic networks and applications to disease transmission models[END_REF][START_REF] Janson | Law of large numbers for the SIR epidemic on a random graph with given degrees[END_REF]. A popular assumption on the networks in which a disease is transmitted is that they are scale-free, which means that as the network size grows, the proportion of nodes of degree k stabilizes to a limit which, as k increases, decays like k -τ for some positive power-law exponent τ . Power-law exponents have been statistically estimated for a range of networks, and there is an abundance of tractable mathematical models for scale-free networks [START_REF] Barabási | Emergence of scaling in random network[END_REF][START_REF] Newman | Random graph models of social networks[END_REF][START_REF] Norros | On a conditionally Poissonian graph process[END_REF][START_REF] Lu | Complex Graphs and Networks[END_REF][START_REF] Dereich | Random networks with concave preferential attachment rule[END_REF]]. An established model for the spread of an infection on a network is the contact process, or SIS model. In this model every node can either be infected or healthy. An infected node passes the infection at a fixed rate λ to each of its neighbours, and recovers with a fixed rate of one. Once it has recovered, it is again susceptible to infection.

The extinction time of this type of infections on a scale-free network has been subject of a controversial discussion in the literature. Pastor-Sattoras and Vespignani [START_REF] Pastor-Satorras | Epidemic spreading in scale-free networks[END_REF][START_REF] Pastor-Satorras | Epidemic dynamics and endemic states in complex networks[END_REF][START_REF] Pastor-Satorras | Epidemic dynamics in finite size scale-free networks[END_REF] have used a non-rigorous mean-field calculation to predict a phase transition in the behaviour of the contact process. They predicted that, for networks with a power-law exponent τ < 3, the infection can survive for a time exponential in the network size regardless of the infection rate. If τ > 3 however, 1 for sufficiently small infection rate, the time to extinction is at most polynomial in the network size. Chatterjee and Durrett [START_REF] Chatterjee | Contact processes on random graphs with power law degree distributions have critical value zero[END_REF] have shown that this prediction is inaccurate and the infection survives for an exponential time for all infection rates and power-law exponents. An earlier version of this result is due to Berger et al. [START_REF] Berger | On the spread of viruses on the internet[END_REF], and a refinement can be found in Mountford et al. [START_REF] Mountford | Metastable densities for the contact process on power law random graphs[END_REF]. The failure of the mean-field approach highlights the need for mathematically rigorous arguments in this area of complex networks.

Up to now, rigorous mathematical research has focused almost exclusively on networks that remain constant while the states of the vertices change. In reality, however, connections between individuals change over time, and investigating the effect of this temporal variability on processes taking place on the network is a question of fundamental importance. The study of evolving, or temporal, networks has been identified as an important direction for research, for example in the concluding paragraph of [START_REF] Durrett | Some features of the spread of epidemics and information on a random graph[END_REF] and in the recent survey [START_REF] Holme | Temporal networks[END_REF]. The present paper is intended as a first step into territory almost untouched by rigorous mathematics up to now, offering a rigorous analysis of the contact process on a very simple model of an evolving scale-free network.

When setting up our model we make three assumptions, which may be justified, for example, if the network is a human interaction network, the updating models movement or migration of individuals, and infection does not greatly affect mobility of individuals. First, we assume that the time-evolution of the network happens independently of the infection process. This is mainly a simplifying assumption in the light of substantial additional difficulties coming from mutual dependence of processes in random environments. 1 Second, we assume that the evolution of the network and the evolution of infection are on the same time scale, which leads to the most interesting interaction between the evolutions. And third we assume that the power of a node, which varies greatly between nodes in scale-free networks, is not changed over time.

In the absence of individual features of the nodes of the network, there are two natural graph evolutions to study: Edge-updating in which the presence or absence of every edge is updated with a fixed rate, and vertex-updating in which every vertex refreshes all its connections with a fixed rate. Edge updating has been studied under the name of dynamical percolation on a range of regular graph models, see for example [START_REF] Steif | A survey of dynamical percolation[END_REF][START_REF] Peres | Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times[END_REF]. In our scenario edge-updating would not produce qualitatively different behaviour from the static case, which is why we focus our attention on the vertex updating rule. In line with our assumptions, vertex updating can serve as a rough model for migration of nodes to a different location.

Our main interest in this paper is in the emergence of qualitatively new phenomena due to the temporal variability of the network. Observe that it is not a priori clear whether temporal variability increases or decreases the extinction time of the infection. Our analysis shows that, on the one hand, the temporal variability is helping the system to exit metastable states, thus decreasing the extinction time. As a result, beyond a critical value of τ a phase of fast extinction emerges which is not present for the static model. On the other hand, time-variability increases the number of nodes infected by a single node, leading to a faster spread of the infection, thus increasing the extinction time. As a result, the transition between the phases of fast and slow extinction does not occur at the value τ = 3, as in the mean-field calculation [START_REF] Pastor-Satorras | Epidemic dynamics and endemic states in complex networks[END_REF], but at the larger value τ = 4. This constitutes an interesting new effect emerging in evolving networks.

Statement of the result

We consider an evolving network model (G t ) t≥0 , a family of graphs indexed by continuous time. Its set of vertices is fixed, for all t ≥ 0, and identified with a set of labels V = {1, . . . , N }. The labels correspond to the strength of vertices, with low labels corresponding to powerful vertices. At time t = 0, each unordered pair of vertices {x, y} ⊂ V independently forms an edge with probability

p x,y = min βN 2γ-1 x γ y γ , 1 ,
where β > 0 and γ ∈ (0, 1) are the parameters of the model. This is a special case of the Chung-Lu model, and it is shown in [START_REF] Lu | Complex Graphs and Networks[END_REF] that G 0 is a scale-free network with power-law exponent τ = 1 + 1 γ . Moreover, the connection probabilities are asymptotically the same as in all rank-one models including the configuration model, see for example [START_REF] Newman | Random graph models of social networks[END_REF][START_REF] Norros | On a conditionally Poissonian graph process[END_REF][START_REF] Lu | Complex Graphs and Networks[END_REF]. Note that the expected degree of the vertex labeled x is proportional to (N/x) γ , reflecting the strong hierarchy of vertices. We remark that, unless γ = 1 2 , the connection probability differs from that in the preferential attachment models, see [START_REF] Dereich | Random networks with concave preferential attachment rule[END_REF], and we believe the results of this paper do not extend to that class.

The time-evolution of the edges of the network obeys the following rule. Each vertex updates independently with intensity κ > 0. When vertex x updates, every unordered pair {x, y} ⊂ V , for y ∈ V \ {x}, forms an edge with probability p x,y , independently of its previous state and of all other edges. The remaining edges {w, y} with w, y = x remain unchanged. Note that the network evolution is stationary, namely for every t ≥ 0, the law of G t is equal to the law of G 0 . We emphasise that the strength of a vertex is given by its label and does not change over time.

We consider the contact process, or SIS infection, on this evolving network. Every vertex is in either of two states, infected or healthy. These states evolve according to the following dynamics. Every infected vertex turns to healthy with rate one. Every healthy vertex turns to infected with rate given by the number of infected neighbours, multiplied by a parameter λ > 0 called the infection rate. The time-evolution of both the network structure and the infection process can be described by a continuous time Markov chain. Figure 1 illustrates the principal transitions that affect the state of a given vertex or its set of neighbours. The vertex is healthy and has three infected neighbours (represented by black dots) and one healthy one (represented by a white dot, other vertices being not represented). At rate 3λ, the vertex gets infected , while at rate κ, it updates, and receives a (possibly) completely new set of neighbours. Right: The vertex is infected. It turns to healthy at rate 1, and still updates at rate κ. Not represented are updates of other vertices that may lead to loss or creation of new neighbours of the vertex.

On a finite graph, no matter how the contact process is started it eventually reaches its unique equilibrium, when all vertices are healthy and the infection has died. We denote by T ext the (random) extinction time for the infection. The interesting question in this context is now, once the infection has broken out, how long it takes until the infection becomes extinct. We observe a dichotomy between slow extinction on the one hand, when T ext is very large, e.g. exponential in the number of vertices, and fast extinction on the other, when T ext is small, no more than polynomial in the number of vertices. It is shown in [START_REF] Durrett | Some features of the spread of epidemics and information on a random graph[END_REF][START_REF] Mountford | Metastable densities for the contact process on power law random graphs[END_REF] that the contact process on the static network G 0 exhibits slow extinction for all parameters γ, β, λ. Our main result shows that this is different for the evolving network model.

Theorem 1 Consider the contact process on the evolving network (G t ) t≥0 , and assume that at time t = 0 every vertex is infected.

(a) If γ > 1/3 (or equivalently τ < 4), then whatever the other parameters of the network, there exists a positive constant c such that, uniformly in N > 0,

P(T ext ≤ e cN ) ≤ e -cN .
(b) If γ < 1/3 (or equivalently τ > 4), then there exists a parameter λ c > 0 such that, for λ < λ c , there exists a positive constant C such that, uniformly in N > 0, we have

E[T ext ] ≤ C √ N .
Remark 1 The result of (b) is true without the assumption on the initial infection. If in (a) initially not all vertices are infected, there is additional uncertainty about the outbreak of the infection. In particular, if under the assumptions of (a) initially a positive proportion of the vertices are infected, the event T ext > e cN still holds with a positive probability, independent of N .

We say that a family of events E t depending on t ≥ 0 holds exponentially long if there exists c > 0 such that, for all N ,

P s≤e cN E s ≥ 1 -e -cN .
Using this terminology, we can rephrase (a) in Theorem 1 as saying that in the given regime the infection survives exponentially long.

Comparison with the static model

Before entering the rigorous proof of Theorem 1, we explain, on a heuristic level, how the timevariability of the network can lead to new phenomena that differ both from the rigorous results on static networks, and from the non-rigorous mean-field predictions.

Mean-field predictions

We first describe informally the phase-transition as predicted by the mean-field calculations. To demonstrate the difference in behaviour of the static and evolving models, our description focuses on the core assumptions of the predictions and simplifies the actual arguments. Consider the contact process on a static network in which the empirical distribution of the degrees of the vertices is given by some probability measure µ on N = {1, 2, . . .}.

The mean-field predictions are based on the principle that instead of taking into account the complex geometry of a network, it suffices to study the behaviour of the contact process around a typical newly infected vertex. The critical infection rate is then the value λ at which such a vertex will, on average, transmit the infection once before its recovery. Conditionally on the degree k of the newly infected vertex, the average number of transmissions before recovery is roughly λk, therefore to understand criticality it suffices to understand the degree of a newly infected vertex.

Assuming that the law of the degree of a newly infected vertex is given by µ, one obtains

λ c = 1 kµ(k) .
While this assumption is widely used, for example in [START_REF] Gross | Adaptive coevolutionary networks: a review[END_REF] in the context of adaptive networks, a possible refinement in our context would take into account that it is easier for a vertex with high degree to become infected. More precisely, we expect the probability of a vertex being infected to be proportional to the number of possible sources of infection, and hence to its degree. Under this assumption, the law of the degree of a newly infected vertex is the size-biased distribution μ, defined by

μ(k) = kµ(k) iµ(i) ,
which leads naturally to

λ c = 1 k μ(k) = kµ(k) k 2 µ(k) ,
as in [START_REF] Pastor-Satorras | Epidemic dynamics in finite size scale-free networks[END_REF]. If µ is the asymptotic degree distribution of a scale-free graph with power-law exponent τ , we get λ c = 0 if τ < 3 and λ c > 0 if τ > 3.

The size-biasing effect is crucial in the study of scale-free networks, and can also be found in the rigorous analysis of another infection process, the SIR infection, as in [START_REF] Janson | Law of large numbers for the SIR epidemic on a random graph with given degrees[END_REF]. It often leads to a phase transition at the value τ = 3, see for example [START_REF] Dereich | Random networks with concave preferential attachment rule[END_REF][START_REF] Van Der Hofstad | Universality for distances in power-law random graphs[END_REF], so that the mean-field predictions loosely described here did conform to expectations at their initial appearance in [START_REF] Pastor-Satorras | Epidemic dynamics and endemic states in complex networks[END_REF]. As already mentioned, these mean-field predictions have proven to be inaccurate for the contact process on static scale-free networks. It turns out to be essential for the analysis to consider the geometry of the network in the neighbourhood of vertices of large degree, as we explain now.

Slow extinction for the static network

Heuristic for the evolving network

In our evolving network, we can first control how long the quick reinfections can maintain the contact process around a vertex, then make mean-field like calculations rigorous. Consider an infected vertex with large degree k. The key observation is that in the evolving network quick reinfections alone can maintain the infection around this vertex for a length of time proportional to the degree k. In fact, the period of quick reinfection will come to an end if either the vertex updates and then recovers before it has infected its new neighbours, or if the vertex recovers and then updates before its old neighbours have reinfected the vertex. Hence, the infection can be kept in a vertex of degree k without external reinfection for λ 2 k units of time in the evolving network, which has to be compared with the value one (for mean-field calculations not taking reinfections into account) or exp(λ 2 k) (for the static network). During the quick reinfection period the vertex will have infected roughly λ 3 k 2 vertices. After the quick reinfection period the vertex can be infected again, but not by a quick reinfection. It will have to be a new infection by a vertex that has become a neighbour before infecting it. For such a new infection, we can rigorously argue that the degree of the newly infected vertex follows the size-biased distribution.

Therefore, if µ stands for the asymptotic degree distribution of the scale-free network, we should observe fast extinction roughly if

λ 3 k 2 μ(k) = λ 3 k 3 µ(k) kµ(k) < 1.
Thus, we expect a phase of fast extinction to emerge as soon as k 3 µ(k) < ∞, which corresponds to τ > 4 and is in line with (b) in Theorem 1.

This heuristic can be made rigorous and leads formally to Lemma 2 in the proof of Theorem 1 (a). In the proof of Theorem 1 (b), the heuristic does not appear explicitly, but has inspired the coupling with a process in which we modify the recoveries, in such a way that a vertex recovers only when we can ensure that it cannot be quickly reinfected by a neighbour.

Graphical representation

In this section, we provide an equivalent description of our model by a convenient graphical representation. The evolving network model (G t ) t≥0 is represented with the help of the following independent random variables;

(1) For each x ∈ V , a Poisson point process of intensity κ > 0, written U x = (U x n ) n≥1 , describing the updating times of x. We also write U x,y = (U x,y n ) n≥1 for the union U x ∪ U y , which is a Poisson point process of intensity 2κ, describing the updating times of the potential edge {x, y} ⊂ V .

(2) For each potential edge {x, y} ⊂ V , a sequence of independent random variables (C x,y n ) n≥0 , all Bernoulli with parameter p x,y , describing the presence/absence of the edge in the network after the successive updating times of the potential edge {x, y}. More precisely, if t ≥ 0 then {x, y} is an edge at time t if and only if C x,y n = 1 for n = |[0, t] ∩ U x,y |. Given the network we represent the infection by means of the following set of independent random variables;

(3) For each x ∈ V , a Poisson point process of intensity one, written R x = (R x n ) n≥1 , describing the recovery times of x.

(4) For each {x, y} ⊂ V , a Poisson point process I x,y 0 with intensity λ describing the infection times along the edge {x, y}. Only the trace I x,y of this process on the set

∞ n=0 {[U x,y n , U x,y n+1 ) : C x,y n = 1} ⊂ [0, ∞)
can actually cause infections. Write (I x,y n ) n≥1 for the ordered points of I x,y . If at time I x,y n vertex x is infected and y is healthy, then x infects y. If y is infected and x healthy, then y infects x. Otherwise, nothing happens.

The infection is now described by a process (X t (x)) x∈V with values in {0, 1} V , such that X t (x) = 1 if x is infected at time t, and X t (x) = 0 if x is healthy at time t. Formally, the infection process X t (x) associated to this graphical representation and to a starting set A 0 of infected vertices, is the càdlàg process with X 0 = 1 A0 evolving only at times t ∈ R x ∪ ∞ n=1 I x,y n , according to the following rules:

• If t ∈ R x , then X t (x) = 0 (whatever X t-(x)). • If t ∈ I x,y , then (X t (x), X t (y)) = (0, 0) if (X t-(x), X t-(y)) = (0, 0).
(1, 1) otherwise.

Proof of Theorem 1(a): Exponential extinction time

Fix γ > 1/3 and note that it suffices to look at small values of the infection rate λ > 0. Our strategy is to focus on highly connected vertices, which we call stars. Informally, when a star is infected typically a proportion of its neighbours is infected at any time. When the star recovers, it is likely to be quickly reinfected by its neighbours, keeping the infection alive for a long time. Only when the star updates before it is reinfected by its neighbours, the recovery is sustained. We use a coupling to look at infections between stars, taking into account only the sustained recoveries. More precisely, we partition the vertex set V into two sets

S := {1, . . . , λ (2+α)/γ N }, C := { λ (2+α)/γ N + 1, . . . , N },
where α > 0 is a constant. We call the vertices in S stars, those in C connectors. Note that a star has an average degree of order λ -2-α , which is large when λ is small. The constant α > 0 is chosen large enough so that we have

1 γ -3 α + 2 γ -3 < 0, (1)
which is possible since γ > 1/3. The reason for this choice will become clear only at the end of the proof. If x and y are stars, then p x,y ≥ px,y := βλ -4-2α N -1 , while if x is a star and y a connector, then

p x,y ≥ px,y := βλ -2-α N -1 .
By a simple coupling argument, it is enough to prove (a) on the modified network where the connection probabilities are replaced by px,y and there are no connections between connectors. We continue to denote this process by (X t (x)) x∈V .

Connector update and recovery times

In order for the infection to survive for a long time around a star, it requires connectors to infect, and get reinfected by. The first lemma ensures that, at any time, there are sufficiently many connectors that do not update or recover too quickly. For any t ∈ N ∪ {0} let

C t := {y ∈ C : (R y ∪ U y ) ∩ [t, t + 2] = ∅}.
Lemma 1 For any sufficiently small η > 0 the event

E t := {|C t | ≥ ηN } holds exponentially long.
This lemma is easy and its proof is omitted. From now on, we work conditionally on the realization of the recovery and update times of the connectors, (R y ) y∈C and (U y ) y∈C , and assume that E t holds exponentially long, without mentioning explicitly the implied constants.

Extinction time for one star

Let T λ := λ -α , where α is positive constant strictly smaller than α, such that

1 γ -2 α -α + 2 γ -3 < 0, (2)
which is possible by [START_REF] Durrett | Some features of the spread of epidemics and information on a random graph[END_REF]. We shall see that a star, alone with its neighbouring connectors, is likely to sustain the infection up to time of order T λ . Note that when λ is small, T λ becomes larger, but λ -2 T λ stays negligible compared to the average degree of a star.

For each star x, let X x be the infection process obtained by keeping only the edges linking x and C , with initial condition

X x 0 (y) = 0 if y = x, X 0 (x) if y = x.
We call X x the infection process around x. This process depends only on the updating times and recovery times at x, and the infection times on edges {x, y} for y ∈ C . Therefore X x and X w are conditionally independent if x and w are two different stars, given the realization of (R y ) y∈C and (U y ) y∈C . Moreover, the infection process X satisfies

X t (x) ≥ X x t (x) for all t ≥ 0, x ∈ S .
We say the infection persists on [0, T ] at a star x ∈ S , if

• X x T (x) = 1, and

• {t ∈ U x ∩ [0, T -1] : X x t (x) = 1, (U x ∪ R x ) ∩ [t, t + 1] = {t}} ≥ 1 2 κe -(1+κ) T.
The second condition ensures that there are enough updating times after which x stays infected for a unit of time without any update or recovery. This will be useful later to control interinfections of stars.

Lemma 2 Let x ∈ S be a star and P x be the event that the infection persists on [0, T λ ] at x. Then lim λ↓0 lim inf

N →∞ P P x X 0 (x) = 1 = 1.
We say an event depending on λ and N holds with high probability, if its probability is arbitrarily close to one when first λ is chosen small enough, and then N sufficiently large. In this sense, Lemma 2, which we prove in the remainder of this section, states that on [0, T λ ] persistence holds with high probability. A first simple observation is that with high probability we have

|U x ∩[0, T λ ]| ≤ 2κT λ and {t ∈ U x ∩ [0, T λ -1] : (U x ∪ R x ) ∩ [t, t + 1] = {t}} ≥ 1 2 κe -(1+κ) T λ .
It remains to prove that we also have, with high probability, that

X x U x n (x) = 1 for n ≤ 2κT λ . Set U 0 = 0 and recursively U n+1 = min{1 + U n , U x ∩ (U n , ∞)}, so that all time intervals [U n , U n+1 ]
have length at most one. It is enough to prove that, with high probability, we have

X x U n (x) = 1 for n ≤ (1 + 2κ)T λ . For t ≤ T λ , define C t (x) := y ∈ C t : {x, y} ∈ G t ,
the set of neighbours of x that are in C t . These are neighbours that we will use to help maintain the infection in x. The following lemma shows that, with high probability, there are enough of them at any time in [0, T λ ].

Lemma 3 lim

λ↓0 lim inf

N →∞ P |C U n (x)| ≥ 1 2 ηβλ -2-α ∀n ≤ (1 + 2κ)T λ = 1.
The result of Lemma 3 follows if P{|C U n (x)| < 1 2 ηβλ -2-α } is, for large enough N , uniformly in n, bounded by a function that is negligible compared to λ α . To this end, observe that, conditionally on U n , the cardinality of C U n (x) is binomial with parameters |C U n | and βλ -2-α N -1 . As we work on the event {|C U n | ≥ ηN }, the cardinality of C U n (x) is asymptotically bounded from below by a Poisson variable with parameter ηβλ -2-α . By a standard large deviation bound, the probability that it is less than 1 2 ηβλ -2-α decays exponentially fast in λ -2-α , completing the proof. Using Lemma 3, we can work conditionally on the event

{|C U n (x)| ≥ 1 2 ηβλ -2-α ∀n ≤ (1 + 2κ)T }.
Lemma 2 is proved once we prove the following lemma.

Lemma 4 For n ≥ 0, we have

P X x U n+1 (x) = 0 X x U n (x) = 1 = o(λ α ),
where the bound is uniform in n.

Discrete infection process

We study the infection process on stars at discrete times 0, T λ , 2T λ , . . . For n ≥ 0, we denote by I n the set of stars x ∈ S with X nT λ (x) = 1, and by A n as the set of stars x ∈ I n such that the infection persists on [nT λ , (n + 1)T λ ] at x. We start with I 0 = S , ie. initially all stars are infected. By Lemma 2, the cardinality of A 0 is stochastically larger than a binomial random variable with parameters |S | and 1 /2, if λ is small and N large. More generally, for n ≥ 0, the cardinality of

Next, we show inductively that, with high probability, the event E n := {|I n | ≥ 1 4 |S |} holds exponentially long. Let n ≥ 0 and condition on E n . Then, as the number of stars is linear in N and each persists on [nT λ , (n + 1)T λ ] independently with probability at least 1 /2, we infer that the event

|A n | ≥ 2 5 |I n | ≥ 1 10
|S | holds with probability at least 1 -e -cN for some c > 0, which depends on λ but not on N . If this holds, then we have

|A n |λ -3-2α T λ N ≤ 1 10 λ ( 1 γ -2)α-α + 2 γ -3 .
The exponent in λ is negative, by our choice of α and α , see [START_REF] Danon | Networks and the epidemiology of infectious disease[END_REF]. Therefore, choosing λ smaller if necessary, we can ensure that the value of ( 4) is larger than 1 /3, which means that each non-infected star, or vertex in S \I n , has independently probability at least 1 /3 to get infected. This, together with |A n | ≥ 2 5 |I n |, ensures that the event |I n+1 | ≥ 1 4 |S | holds with probability at least 1 -e -cN for some (new) constant c. Altogether, we have proved that the infection persists exponentially long.

Proof of Theorem 1(b): Polynomial extinction time

In this section, we propose a coupling of the contact process on an evolving scale-free network, with a mean-field infection model. In the mean-field infection model, an infected vertex recovers only when for the original process we can ensure the recovery is sustained and not subject to a quick reinfection. This is the case when the recovery is immediately preceeded by an update of the vertex, so that it is no longer exposed to its original infected neighbours. This allows us to neglect information on the graph structure around the infected vertex prior to the update. Hence we can set up the mean-field infection model independently of the topology of the evolving network, namely as an infection process on the complete graph with appropriately decreased infection rates. Finally, the mean-field infection model can be studied with standard techniques, and we can show that the time to extinction is polynomial when γ < 1/3.

Mean-field infection model

To set up the mean-field infection model, for every x ∈ V , we use the point processes R x and U x introduced for graphical representation of the original infection process. In addition, for each potential edge {x, y} ⊂ V , we define an independent Poisson point process J x,y = (J x,y n ) n≥1 with intensity λp x,y . The sets J x,y describe infection times for this process, but the sets R x and U x have now a different meaning. They describe how recoveries can happen, but in a more involved way. To describe the infection, we use a Markov process (Y t (x)) x∈V with values in {0, 1, 2} V , where a vertex x can take three different values, the value 0 still meaning healthy, the value 2 meaning infected, and the value 1 meaning infected but ready to recover. The process evolves according to the following rules;

(1) If t ∈ J x,y , then

(Y t (x), Y t (y)) = (0, 0) if (Y t-(x), Y t-(y)) = (0, 0), (2, 2)
otherwise.

(

) If t ∈ U x , then Y t (x) = 1 if Y t-(x) = 2, Y t-(x) 2
otherwise.

(

) If t ∈ R x , then Y t (x) = 0 if Y t-(x) = 1, Y t-(x) 3
otherwise.

In other words, once a vertex x is infected, in order to recover, it has to observe an 'updating' time in U x , then a 'recovery' time in R x , and no infection time in-between (in y J x,y ).

Coupling

The next proposition states that, if we fix the initial conditions of the infection processes X and Y so that X 0 ≤ Y 0 , then there exists a coupling maintaining the ordering X t ≤ Y t for all times.

Proposition 1 Fix deterministic initial conditions X 0 ≤ Y 0 . One can construct, on the same probability space, the evolving network (G t ) t≥0 , the infection process (X t (x)) x∈V,t≥0 on this network, and the mean-field infection process (Y t (x)) x∈V,t≥0 , such that X t (x) ≤ Y t (x) for all x ∈ V and t ≥ 0.

We stress that the coupling uses the knowledge of the initial condition X 0 . As indicated above, we choose the same U x and R x for both models. The coupling will actually be a coupling between the processes J x,y and the processes I x,y , which are determined as before by variables I x,y 0 , C x,y n and U x,y = U x ∪U y . Given the latter, the set J x,y is defined as a subset of I x,y 0 , obtained by percolation of parameter p x,y , and hence is a Poisson point process of parameter λp x,y , as requested. However, this percolation procedure will be dependent on the process X and on the C x,y n , as we now explain. We introduce the following notions.

• An infection time is an infection time of the original process, namely a time t ≥ 0 belonging to some I x,y , or equivalently belonging to some I x,y 0 and such that C x,y n = 1 if t ∈ (U x,y n , U x,y n+1 ). • A potential infection time is any time t in some I x,y 0 . • A true infection time is an infection time t satisfying the additional condition max{X t-(x), X t-(y)} = 1.

• A potential true infection time is a potential infection time t satisfying additionally max{X t-(x), X t-(y)} = 1. the survival of the infection. Actually, we want to define them in such a way that, if the infection rate λ is small, M is a tractable supermartingale with respect to the filtration (F t ) generated by (Y t ). Informally, s 2 (x) should be larger than s 1 (x), and, for i = 1, 2, we should have s i (x) larger than s i (x ) if x < x , as p x,y ≥ p x ,y for all y = x, x . We have In this equality we have written for each vertex x, the change of its contribution to the total score, namely s 1 (x)1{Y t (x) = 1} + s 2 (x)1{Y t (x) = 2}, induced by the infinitesimal transition probabilities of the infection process changing the state of x. The third sum can be rewritten as

x : Yt(x)≥1 y : y =x, Y t (y)=0 λp x,y s 2 (y) ≤

x : Yt(x)≥1 y λp x,y s 2 (y).

Writing S(x) := y p x,y and T (x) := y p x,y s 2 (y), we get the following bound,

1 dt E M (t + dt) -M (t) F t ≤ x : Yt(x)=2
λT (x) -κ s 2 (x) -s 1 (x) +

x : Yt(x)=1

λT (x) + λS(x) s 2 (x) -s 1 (x) -s 1 (x).

It is easy to bound S(x), which is the average degree of x, as

S(x) ≤ β N 1-2γ x γ N y=1 y -γ ≤ β 1 -γ N x γ .
We now choose s 1 and s 2 as

s 1 (x) = N x 2γ s 2 (x) = s 1 (x) + N x γ .
Then, we can bound T (x) as

T (x) ≤ 2β N 1-4γ x γ N y=1 y -3γ ≤ 2β 1 -3γ N x γ ,
where we used γ < 1 /3. Therefore, for any x, we have λT (x) -κ s 2 (x) -s 1 (x) ≤ 2λβ 1 -3γ -κ N x γ and λT (x) + λS(x) s 2 (x) -s 1 (x) -s 1 (x) ≤ 2λβ 1 -3γ

N x γ + λβ 1 -γ -1 N x 2γ .
If λ is small enough, the negative terms compensate all the positive ones, and we get, for some positive constant ν > 0,

1 dt E M (t + dt) -M (t) F t ≤ -ν   x : Yt(x)=2
s 2 (x)

1 2 + x : Yt(x)=1 s 1 (x)   ≤ -ν M (t).
We introduce the process Z(t) = M (t) + νt/2, and get, on the event M (t) > 0,

1 dt E Z(t + dt) -Z(t) F t ≤ ν 2 + 1 2 M (t) 1 dt E M (t + dt) -M (t) F t ≤ 0.
Observing that the extinction time T ext of the process Y is also the hitting time of 0 for the process M , we get that Z(t∧T ext ) defines a positive supermartingale, converging to Z(T ext ) = ν 2 T ext . Using the optional stopping theorem we deduce E[Z(T ext )] ≤ Z(0), and therefore

E[T ext ] ≤ 2 ν M (0) ≤ 2 ν x s 2 (x) ≤ 2 ν 2N 1 -2γ .
Hence the expectation of T ext grows at most like √ N and the second part of Theorem 1 is proved.

EJ was supported by CNRS, and PM was supported by EPSRC grant EP/K016075/1.

Figure 1 :

 1 Figure1: Left: The vertex is healthy and has three infected neighbours (represented by black dots) and one healthy one (represented by a white dot, other vertices being not represented). At rate 3λ, the vertex gets infected , while at rate κ, it updates, and receives a (possibly) completely new set of neighbours. Right: The vertex is infected. It turns to healthy at rate 1, and still updates at rate κ. Not represented are updates of other vertices that may lead to loss or creation of new neighbours of the vertex.

1 2 1 -

 11 A n conditionally on |A 0 |, . . . , |A n-1 | and on |I 0 |, . . . , |I n | is stochastically larger than a binomial random variable with parameters |I n | and 1 /2. By Lemma 5, conditionally on |A 0 |, . . . , |A n | and on |I 0 |, . . . , |I n |, the cardinality of I n+1 \A n is stochastically larger than a binomial random variable with parameters |S | -|I n | and exp -1 4 βκe -(1+κ) |An|λ -3-2α T λ N .

1

 1 dt E M (t + dt) -M (t) F t = x : Yt(x)=2 κ(s 1 (x) -s 2 (x)) + x : Yt(x)=1   -s 1 (x) + y : y =x λp x,y (s 2 (x) -s 1 (x))

We note however that network dynamics depending on the states of the nodes, are studied under the name adaptive, or co-evolutionary, networks in the nonrigorous literature, see for example[19,

[START_REF] Gross | Adaptive coevolutionary networks: a review[END_REF][START_REF] Durrett | Graph fission in an evolving voter model[END_REF][START_REF] Holme | Nonequilibrium phase transition in the coevolution of networks and opinions[END_REF], and[START_REF] Basu | Evolving voter model on dense random graphs[END_REF] for a rare rigorous example.

The starting point of the rigorous studies[START_REF] Chatterjee | Contact processes on random graphs with power law degree distributions have critical value zero[END_REF][START_REF] Berger | On the spread of viruses on the internet[END_REF][START_REF] Mountford | Metastable densities for the contact process on power law random graphs[END_REF] concerning the contact process on a static scale-free network is the observation that the infection can survive near a vertex of high degree for much longer than predicted by the mean-field calculations. Specifically, Lemma (5.3) in[START_REF] Berger | On the spread of viruses on the internet[END_REF] gives an estimate for the survival probability of the contact process on a star graph, which contains only one vertex of degree k, and its k neighbours, of degree one. It shows that if λ 2 k is larger than an absolute constant, then the time to extinction on this star graph is exponential in λ 2 k. This is due to quick reinfections of the central vertex of degree k. More precisely, when the central vertex recovers, it is typically surrounded by many infected vertices that reinfect it almost instantly. This quick reinfection is not picked up by mean-field calculations, as they keep no memory of the actual neighbours of the central vertex.

The probability on the left does not depend on n, so we may take n = 0 and X x 0 (x) = 1. On the event {X x U 1 (x) = 0}, we necessarily have R x ∩ (0, U 1 ) = ∅. Define random variables

The strategy is to find a connector y that gets infected by x during the time interval [0, R], and then reinfects x on [U 1 -L, U 1 ]. We look for such a connector in the set C 0 (x), as these are connected to x during the whole interval [0, U 1 ], and do not recover during this time. For a given y ∈ C 0 (x), the probability that the back-and-forth infection between x and y occurs is

where the bound uses the inequality 1 -e -x ≥ x/2 for x ∈ [0, 1] and the fact that L, R < 1. Hence, the probability that this fails for all y ∈ C 0 (x) is bounded by

On the event that the product LR is not too small, ie. LR ≥ λ α , with α = 1 2 (α + α ), the bound is o(λ α ), as requested. Finally, to bound the probability that LR is small, we show that

Indeed, Equation (3) follows by bounding separately the probability of the three events {L ≤ 2λ α }, {R ≤ 2λ α }, and

The bound on the third event uses the fact that on {L ≤ 1/2, R ≤ 1/2}, the random variables L and R are independent and their laws have bounded density on [0, 1/2]. The bound for the first two events also follows from this, we leave the (easy) details to the reader.

Reinfections between stars

Consider an initial condition where the stars in I ⊂ S are infected, and those in S \I are healthy.

From the preceding subsection, we know that, independently for each infected star, the infection is likely to persist at that star. Denote by I the set of infected stars at which the infection persists on [0, T λ ].

In this subsection, we prove a quantitative lemma stating that each healthy star has independently some probability of becoming infected by some star s ∈ I , and then be infected at time T λ . We condition on the infection processes (X x ) x∈I , which determine I . For x ∈ S \I , we define

Observe that if T x is finite, then x is necessarily infected at this time, namely we have X Tx (x) = 1.

If T x ≤ T λ , we define an infection process similar to the process X x , but on the restricted time interval [T x , T λ ]. More precisely, define the process ( Xx t ) t∈[Tx,T λ ] as the infection process obtained by keeping only edges between x and C , and with initial condition

We further extend this process to [0, T λ ] by letting Xx t ≡ 0 if t < T x (so the process is well-defined even if

Moreover, note the following two facts;

• The processes Xx , for x ∈ S \I , are independent (conditionally on (X x ) x∈I ).

• Conditionally on T x < T λ , the probability that x is infected at time T λ goes to 1 when λ goes to 0 and N is large. This is obtained by a slight variation of Lemma 2.

Therefore, if λ is small and N large enough, every healthy star has independently probability at least 1 2 P T x < T λ (X y ) y∈I of being infected at time T λ . The following lemma bounds this probability from below by a quantity depending on |I |.

Lemma 5 If x ∈ S \I is a healthy star, ie. X 0 (x) = 0, then

Condition on (X y ) y∈I , the infection processes around each y ∈ I . We first suppose that the infection persists at only one star called y, namely I = {y}. We further condition on the updating times U x , and hence on the updating times of the edge {x, y}, namely (U x,y n ) n≥0 . For n ≥ 0, write

1{X y t (y) = 1} dt, the total time when vertex y is infected between consecutive updating times. The probability that y does not infect x is

Using the lower bound for the sum we get from the fact that the infection persists around y, we continue the inequality by

Note that the events that y does not infect x, for y ∈ I , are majorised by events that are independent given the realization of U x . Hence the probability that no vertex of I infects x is bounded by the right-hand-side to the power |I |, and the result follows.

It is clear that only true infection times can play any role in the spread of the infection. Observe also that the notion of true infection times depends monotonically on the infection process up to time t-, in the sense that any true infection time for X would also be a true infection time for a process X ≥ X. For each x, y, and n, we denote by F x,y n the first potential true infection time in (U x,y n , U x,y n+1 ) if there is any,

with the convention inf ∅ = +∞. The important observation now is that the time F x,y n and the infection process strictly before that time, on [0, F x,y n ), are independent of C x,y n . This follows from the fact that, on (U x,y n , U x,y n+1 ), before the first potential true infection, there cannot be any true infection along x, y, whatever the value of C x,y n , and thus the infection process can be determined independently of C x,y n . To construct J x,y let t ∈ I x,y 0 ∩ (U x,y n , U x,y n+1 ). If t is the first potential true infection, ie, if t = F x,y n , we let t ∈ J x,y if C x,y n = 1 and t / ∈ J x,y if C x,y n = 0. Otherwise, sample an independent Bernoulli p x,y random variable to determine whether t is kept in J x,y or not.

It is clear that J x,y has the required law, ie. it is a Poisson point process of intensity λp x,y obtained by percolation of parameter p x,y on I x,y 0 . We now explain why the mean-field process Y has to stay above X if it has started with Y 0 ≥ X 0 . To this end, we have to ensure two things:

• If a vertex x recovers for the process Y at some time t, then it also recovers for the process X (if it was infected).

• If t ∈ I x,y ∩(U x,y n , U x,y n+1 ) is a true infection time for the process X, then we have (Y t (x), Y t (y)) ≥ (1, 1).

The first item is obvious as Y recovers only at times t ∈ R x , and X also recovers at these times. To verify the second item observe that under our assumption we have C x,y n = 1, and hence on (U x,y n , U x,y n+1 ) potential infections and potential true infections coincide with infections and true infections. Now we distinguish two cases. In the first case, t = F x,y n is the first true infection time for the process X on (U x,y n , U x,y n+1 ). By checking all the potential infection times t ∈ I x,y 0 successively we ensure that Y is above X up to time t-. As t ∈ J x,y by construction, we obtain (Y t (x), Y t (y)) = (2, 2) ≥ (1, 1). In the second case, t is not the first true infection time on (U x,y n , U x,y n+1 ). Then we have F x,y n < t, and at time F x,y n ∈ J x,y , we have set the value of Y in x and y to be 2. These values cannot decrease before the next updating time for x or y, namely U x,y n+1 . We deduce again Y t (x) = Y t (y) = 2, and this finishes the proof.

Study of the mean-field infection model

In this part, we show that the infection dies in polynomial time for the mean-field model. We use a simple supermartingale technique, by introducing a process M (t) defined by M (t) := The values s 1 (x) and s 2 (x), for x ∈ {1, . . . , N }, are nonnegative scores, associated to infected vertices, which should roughly quantify to which extent the fact that x is infected contributes to