Christian Schmidt

Henry D Pfister

Lenka Zdeborová

On Minimal Sets to Destroy the k-Core in Random Networks

We study the problem of finding the smallest set of nodes in a network whose removal results in an empty k-core; where the k-core is the sub-network obtained after the iterative removal of all nodes of degree smaller than k. This problem is also known in the literature as finding the minimal contagious set. The main contribution of our work is an analysis of the performance of the recently introduced corehd algorithm [Scientific Reports, 6, 37954 (2016)] on random networks taken from the configuration model via a set of deterministic differential equations. Our analyses provides upper bounds on the size of the minimal contagious set that improve over previously known bounds. Our second contribution is a new heuristic called the weak-neighbor algorithm that outperforms all currently known local methods in the regimes considered.

I. INTRODUCTION

Threshold models are a common approach to model collective dynamical processes on networks. On a daily basis, we face examples such as the spreading of epidemics, opinions and decisions in social networks and biological systems. Questions of practical importance are often related to optimal policies to control such dynamics. What is the optimal strategy for vaccination (or viral marketing)? How to prevent failure propagation in electrical or financial networks? Understanding the underlying processes, and finding fast and scalable solutions to these optimal decision problems are interesting scientific challenges. Providing mathematical insight might be relevant to the resolution of practical problems.

The contribution of this paper is related to a widely studied model for dynamics on a network: the threshold model [START_REF] Granovetter | Threshold models of collective behavior[END_REF], also known as bootstrapping percolation in physics [START_REF] Chalupa | Bootstrap percolation on a bethe lattice[END_REF]. The network is represented by a graph G = (V, E), the nodes of the graph can be either in an active or inactive state. In the threshold model, a node v ∈ V changes state from inactive to active if more than t v -1 of its neighbors are active. Active nodes remain active forever. The number t v is called the threshold for node v. Throughout this paper we will be concerned with the case the threshold t v = d v -k + 1 where d v is the degree of node v and k is some fixed integer.

In graph theory, the k-core of a graph is defined as the largest induced subgraph of G with minimum degree at least k. This is equivalent to the set of nodes that are left after repeatedly removing all nodes of degree smaller than k. The significance of the k-core of a graph for the above processes can be laid out by consideration of the complementary problem. Nodes that remain inactive, after the dynamical process has converged, must have less than t v active neighbors. Or, equivalently, they have κ v = d v -t v + 1 or more inactive neighbors. Since the dynamics are irreversible, activating a node with at least t v active neighbors may be seen as removing an inactive node with fewer than d v -t v nodes from the graph. In that sense, destroying the k-core is equivalent to the activation of the whole graph under the above dynamics with t v = d v -k + 1. In other words, the set of nodes that leads to the destruction of the k-core is the same set of nodes that lead, once activated, to the activation of the whole graph. Following the literature [START_REF] Reichman | New bounds for contagious sets[END_REF][START_REF] Coja-Oghlan | Contagious sets in expanders[END_REF][START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF] we call the smallest such set the minimal contagious sets of G. In a general graph this decision problem is known to be NP-hard [START_REF] Paul | Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion[END_REF].

Most of the existing studies of the minimal contagious set problem are algorithmic works in which algorithms are proposed and heuristically tested against other algorithms on real and synthetic networks; see e.g. [1, [START_REF] Altarelli | Optimizing spread dynamics on graphs by message passing[END_REF][START_REF] Altarelli | Large deviations of cascade processes on graphs[END_REF][START_REF] Braunstein | Network dismantling[END_REF][START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF] for some recent algorithmic development. Theoretical analysis commonly brings deeper understanding of a given problem. In the case of minimal contagious sets, such analytic work focused on random graphs, sometimes restricted to random regular graphs, in the limit of large graphs. On random graphs the minimal contagious set problem undergoes a threshold phenomenon: in the limit of large graph size the fraction of nodes belonging to the minimal contagious set is with high probability concentrated around a critical threshold value.

To review briefly the theoretical works most related to our contribution we start with the special case of k = 2 that has been studied more thoroughly than k ≥ 3. The choice of k = 2 leads to the removal of the 2-core, i.e. removal of all cycles, and is therefore referred to as the decycling problems. This case is also known as the feedback vertex set, one of the 21 problems first shown to be NP-complete [START_REF] Richard | Reducibility among combinatorial problems[END_REF]. On random graphs the decycling problem is very closely related to network dismantling, i.e. removal of the giant component [START_REF] Braunstein | Network dismantling[END_REF]. A series of rigorous works analyzes algorithms that are leading to a the best known bounds on the size of the decycling set in random regular graphs [START_REF] Bau | Decycling numbers of random regular graphs[END_REF][START_REF] Hoppen | Induced forests in regular graphs with large girth[END_REF]. Another series of works deals with the non-rigorous cavity method and estimated values for the decycling number that are expected to be exact or extremely close to exact [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF][START_REF] Braunstein | Network dismantling[END_REF][START_REF] Zhou | Spin glass approach to the feedback vertex set problem[END_REF]. The cavity method predictions also lead to specific message passing algorithms [START_REF] Altarelli | Optimizing spread dynamics on graphs by message passing[END_REF][START_REF] Altarelli | Large deviations of cascade processes on graphs[END_REF][START_REF] Braunstein | Network dismantling[END_REF]. While there is some hope that near future will bring rigorous establishment on the values of the thresholds predicted by the cavity method, along the lines of the recent impressive progress related to the K-SAT problem [START_REF] Ding | Proof of the satisfiability conjecture for large k[END_REF], it is much further of reach to analyze rigorously the specific type of message passing algorithms that are used in [START_REF] Altarelli | Optimizing spread dynamics on graphs by message passing[END_REF][START_REF] Altarelli | Large deviations of cascade processes on graphs[END_REF][START_REF] Braunstein | Network dismantling[END_REF]. A very well performing algorithm for decycling and dismantling has been recently introduced in [1]. One of the main contributions of the present work is to analyze exactly the performance of this algorithm thus leading to upper bounds that are improving those of [START_REF] Bau | Decycling numbers of random regular graphs[END_REF] and partly closing the gap between the best know algorithmic upper bounds and the expected exact thresholds [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF][START_REF] Braunstein | Network dismantling[END_REF].

The case of contagious sets with k ≥ 3 is studied less broadly, but the state-of-the-art is similar to the decycling problem. Rigorous upper bounds stem from analysis of greedy algorithms [START_REF] Coja-Oghlan | Contagious sets in expanders[END_REF]. The problem has been studied very thoroughly via the cavity method on random regular graphs in [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF], result of that paper are expected to be exact or very close to exact.

A. Summary of our contribution

This work is inspired by the very simple decycling algorithm corehd proposed in [1]. In numerical experiments the authors of [1] found that corehd is close in performance to the message passing of [START_REF] Braunstein | Network dismantling[END_REF], which is so far the best performing algorithm for random graphs. The corehd algorithm of [1] proceeds by iterating the following two steps: first the 2-core of the graph is computed and second a largest-degree-node is removed from the 2-core. It was already anticipated in [1] that this algorithm can be easily extended to the threshold dynamics where we aim to remove the k-core by simply replacing the 2 with a k.

In this work, we observe that the dynamics of the corehd algorithm is amenable to rigorous analysis and performance characterization for random graphs drawn from the configuration model with any bounded degree distribution. We show that it is possible to find a deterministic approximation of the macroscopic dynamics of the corehd algorithm. Our results are based on the mathematical analysis of peeling algorithms for graphs by Wormald in [START_REF] Nicholas | Differential equations for random processes and random graphs[END_REF]. Our particular treatment is inspired by the tutorial treatment in [START_REF] Henry | The analysis of graph peeling processes[END_REF] of the decoding analysis in [START_REF] Luby | Efficient erasure correcting codes[END_REF]. Clearly the algorithm cannot be expected to perform optimally as it removes nodes one by one, rather than globally. However, our work narrows considerably the gap between the existing rigorous upper bounds [START_REF] Coja-Oghlan | Contagious sets in expanders[END_REF][START_REF] Bau | Decycling numbers of random regular graphs[END_REF] and the expected optimal results [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF]. Note also that the fully solvable relaxed version -where first all nodes of the largest degree are removed from the core before the core is re-evaluated -yields improvements.

Our analysis applies not only to random regular graphs, but also to random graphs from the configuration model defined by a degree distribution. The basic theory requires that the degree distribution is bounded (i.e. all the degrees are smaller than some large constant independent of the size of the graph). But, the most commonly used Erdős-Rényi random graphs have a Poisson degree distribution whose maximum degree grows slowly. Fortunately, one can add all the nodes with degree larger than a large constant to the contagious set. If the fraction of thus removed edges is small enough, then the asymptotic size of the contagious set is not affected and the same result holds. Results are presented primarily for random regular graphs in order to compare with the existing results.

The following results are presented. a. Exact analysis of the corehd algorithm. We show that the corehd algorithm (generalized to k-core removal) translates to a random process on the degree distribution of the graph G. We track this random process by derivation of the associated continuous limit. This is done by separating the random process into two deterministic processes and absorbing all randomness into the running time of one of them. We derive a condition for the running time in terms of the state of the system and this reduces the dynamics to a set of coupled non-linear ordinary differential equations (ODEs) describing the behaviour of the algorithm on a random graph, eqs. [START_REF] Cocco | Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms[END_REF][START_REF] Pittel | Sudden emergence of a giant k-core in a random graph[END_REF][START_REF] Nicholas | The differential equation method for random graph processes and greedy algorithms[END_REF].

b. New upper bounds on the size of the minimal contagious sets in random graphs. The stopping time of the before-mentioned ODEs is related to the number of nodes that were removed from the k-core during the process. Thus providing upper bounds on the expected minimal size of the contagious set of G. A numerical evaluation shows that the bounds improve the best currently known ones [START_REF] Bau | Decycling numbers of random regular graphs[END_REF] and narrow the gap to the anticipated exact size of the minimal contagious set from [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF], see e.g. table II for the decycling, k = 2, problem.

c. Improved heuristic algorithm. Based on intuition we gained analyzing the corehd algorithm we propose it's extension that further improves the performance. In this new algorithm, instead of first removing high degree nodes, we first remove nodes according to the decision rule arg max d i -1 di j∈∂i d j . On graphs with bounded degree this algorithm has O(N ) running time, where N is the number of nodes in the graph. In experiments we verify that this weak-neighbor heuristics improves over corehd and other recently introduced algorithms such as the citm of [START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF].

The paper is organized in two main parts. The first part in section II is devoted to the analysis of the generalized corehd algorithm and comparison of the resulting upper bounds with existing results. In the second part in section III we introduce the new algorithm called the weak-neighbor (that we do not study analytically) and close with some numerical experiments and comparison with other local algorithms.

II. THE ANALYSIS OF THE COREHD ALGORITHM

In Algorithm 1 we outline the corehd algorithm of [1], generalized from k = 2 to generic k. The algorithm provides us with a contagious set of nodes D such that after their removal the resulting graph has an empty k-core. Consequently the size of D provides an upper bound on the size of the minimal contagious set. In terms of Algorithm 1, our aim is to show that the size of D per node has a well defined limit, and to compute this limit.

Algorithm 1: Generalized corehd algorithm. Data: G(V, E) Result: A set of nodes D whose removal makes the k-core vanish Function: core (k,G) returns the k-core of the graph

G 1Initialize: C ← core(k, G) , D = { } 2while |C| > 0 do 3 M ← {i ∈ V C | i = arg max [d i ]} ; // V C is the set of nodes in C 4 r ← uniform(M) ; 5 C ← C\r ; 6 D ← D ∪ {r} ; 7 C ← core(k, C) ; 8end
With a proper book-keeping for the set M and dynamic updating of the k-core the running time of corehd on graphs with bounded degree is O(N ). The algorithm can be implemented such that in each iteration exactly one node is removed: if a node of degree smaller than k is present, it is removed, else a node of highest degree is removed. Thus running the algorithm reduces to keeping track of the degree of each node. If the largest degree is O(1) this can be done in O(1) steps by binning all the nodes of equal degree. If a node is removed only the degrees of all its O(1) neighbours must be moved to the new adequate bins. To review and test our implementation of the corehd algorithm see the open depository [20].

A. Reduction into a random process on the degree distribution

In the next several sections, we derive closed-form deterministic equations for the macroscopic behavior of the corehd algorithm in the limit of large random graphs taken from the configuration model. This is possible because, when the corehd algorithm is applied to a random graph from the configuration model (parameterized by its degree distribution), the result (conditioned on the new degree distribution) is also distributed according to the configuration model. Thus, one can analyze the corehd algorithm by tracking the evolution of the degree distribution.

In particular, the behaviour of the corehd procedure averaged over the graph G can be described explicitly in terms of the following process involving colored balls in an urn [START_REF] Henry | The analysis of graph peeling processes[END_REF]. At time step n there will be N n balls in the urn, each of which carries a color d i , with d i ∈ {1, . . . , d} and d being the maximum degree in the graph at the corresponding time step. At any time step n there are v q (n) balls of color q. The colors of the balls are initialized in such a way that at time n = 0, the number of balls, N 0 , is the size of the k-core of the original graph G and the initial values of their colors are chosen from the degree distribution of the k-core (relation of this to the original degree distribution is clarified later).

In a first step, called "removal" (line 3-6 in Alg. 1), one ball is drawn among the v d (n) balls of maximum degree (color d) uniformly at random. Next d balls {i 1 , i 2 , . . . , i d } are drawn with colors following the excess degree distribution of the graph. The excess degree distribution P (q) = qQ(q)/c of a graph of degree distribution Q(q) and average degree c gives the probability that an outgoing edge from one node is incoming to another node of degree q. To conclude the first step, each of the d balls is replaced by a ball of color d ij -1 (we assume that there are no double edges). In a second step, called "trimming" (line 7 in Alg. 1), we compute the k-core of the current graph. In the urn-model this is equivalent to repeatedly applying the following procedure until v i = 0 ∀ i < k: draw a ball of color q ∈ {1, . . . , k -1} and relabel q other balls chosen according to the excess degree distribution. Thus, we obtain a random process that depends purely on the degree distribution. Note that in this process we used the fact that the graph was randomly drawn from the configurations model with degree distribution Q(q). One difficulty, when analyzing the above process, is to chose the right observables. In the previous paragraph the nodes were used as observables. However, equally, one might consider the process in terms of the edges of the graph. As outlined in the previous paragraph, it is important to keep track of the excess degree distribution. Henceforth we will be working with the half-edges to simplify the analysis.

To reinterpret the above process in terms of half-edges let h i be the total number of half-edges that are connected to nodes of degree i at the current iteration. Furthermore, we distinguish nodes of degree smaller than k from all the others. To do so we adapt our index notation in what follows and identify h k< := i<k h i and denote the sum over the entries of a vector h

(n) = (h k< (n), h k (n), . . . , h d (n)) T as |h(n)|.
Finally let us also define the unit vectors e k< = (1, 0, . . . , 0) T , e k = (0, 1, 0, . . . , 0) T , . . . , e d = (0, . . . , 0, 1) T . Each ball now represents a half-edge and its color is according to the degree of the node that this half-edge is connected to.

The two steps (trimming and removal) can be described in terms of half-edges as follows. We start with the "removal" step (line 3-6 in Alg. 1). It can be recast in the following rule

(i) h ← h -d • e d (ii) Repeat d times: h ← h + Az (1)
where the vector z ∈ R d-k+2 is a random vector that has zeros everywhere except in one of the d -k + 2 directions, in which it carries a one. The probability that z is pointing in direction at iteration n is given by the excess degree distribution

h q (n)/ |h(n)| for q = k < , k, k + 1, . . . , d.
When a node of degree d is removed from the graph, together with its half-edges, the remaining cavity leaves behind some dangling half-edges that are pruned away in step (ii) using the following "relabelling" matrix

A =       -1 k -1 -k k . . . . . . -(d -1) d -1 -d       ∈ R (d-k+2)×(d-k+2) . (2)
Analogously, the "trimming" step (line 7 in Alg. 1) can be cast in the following update rule where step (i) removes a single half-edge of degree < k and subsequently step (ii) trims away the dangling cavity half-edge while h k< > 0 iterate:

(i) h ← h -e k< (ii) h ← h + Az . (3)
where again the position q where to place the one in the random variable z is chosen from the current excess degree distribution

h q (n)/ |h(n)| for q = k < , k, k + 1, . . . , d.
The advantage of working with a representation in terms of half-edges is that we do not need to distinguish the different edges of color "k < ". Further |h(n)| is deterministic because each column of (2) sums to the same constant. During the removal step, eq. (1), we remove 2d half-edges and in one iteration of the trimming step, eq. ( 3), we remove 2 half-edges (resp. d edges and one edge). However, the running time of the second step has become a random variable. We have effectively traded the randomness in |h(n)| for randomness in the running time. For now we have simply shifted the problem into controlling the randomness in the running time. In section II C it will be shown that transitioning to continuous time resolves this issue, after averaging, by determination of the running time δt as a function of Eh(t).

This alternating process is also related to low-complexity algorithms for solving K-SAT problems [START_REF] Achlioptas | Setting 2 variables at a time yields a new lower bound for random 3-SAT[END_REF][START_REF] Achlioptas | Lower bounds for random 3-SAT via differential equations[END_REF][START_REF] Cocco | Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms[END_REF]. These K-SAT solution methods alternate between guessing variables, which may create new unit clauses, and trimming unit clauses via unit clause propagation. Due to this connection, the differential equation analyses for these two problems are somewhat similar.

B. Taking the average over randomness

As the equations stand in (1) and (3) they define a random process that behaves just as Alg. 1 on a random graph G, but with z and the stopping time of the trimming step implicitly containing all randomness. In terms of the urn with balls representing half-edges, the random variable z indicates the color of the second half-edge that is left behind after the first was removed. We denote the average over z as

• := E z [•] .
Performing the average over the randomness per se only yields the average behaviour of the algorithm. In section II D it is shown that the stochastic process concentrates around its average in the continuous limit.

Next the combination of steps (i) and (ii) in eq. (1) for the "removal" and eq. ( 3) for the "trimming" is considered. In terms of half-edges we remove 2d half-edges in one iteration of (1) and 2 half-edges in one iteration of [START_REF] Chalupa | Bootstrap percolation on a bethe lattice[END_REF]. In order to write the average of the removal step, we recall that the probability that one half-edge is connected to a color q ∈ {k < , k, k + 1, . . . , d} is given by the excess degree distributionh q (n)/ |h(n)|. In the large system limit the average drift of a full removal step can be written as

h(n + 1) = 1 + 1 h(n) -d -(d -1) A • • • 1 + 1 h(n) -d A h(n) -d e d (4)
=   1 + d-1 j=0 1 h(n) -d -j A   h(n) + d k=2 c k A k h(n) -d e d -d d k=1 ck A k e d (5)
=   1 + d-1 j=0 1 h(n) -d -j A   h(n) -d e d + O( 1 h(n) ) (6) = 1 + d h(n) A h(n) -d e d + O( 1 h(n) ) , (7)
where 1 represents the identity matrix. In the above estimate, we use d intermediate steps to transition from n → n+1, that is the removal of a whole degree d node. We assume that d is O(1). It then follows that the coefficients c k and ck are O( h(n) -k ). The last line follows from a similar estimate for the leading term in the sum.

The average removal step can now be written as

h(n + 1) = h(n) + A d h(n) h(n) . (8)
with the effective average drift matrix

A d := d(A + B d ) , (9)
where the matrix B d has all entries in the last row equal to -1 and zeros everywhere else, such that B d v = -e d for a non-negative, normalized vector v. Similarly, taking the average in one trimming time step (3) yields the following averaged version

h(n + 1) = h(n) + A k< h(n) h(n) . ( 10
)
For the trimming step the effective drift is simply

A k< := A + B k< . ( 11
)
where now B k< has all its entries in the first row equal to -1 and zeros everywhere else. We emphasize that the two processes ( 8) and [START_REF] Braunstein | Network dismantling[END_REF], while acting on the same vector, are separate processes and the latter (10) needs be repeated until the stopping condition h k< = 0 is hit. Note also, that in the trimming process, one iteration n → n + 1 indicates the deletion of a single edge, while it indicates the deletion of a whole node in the removal process.

C. Operator and Continuous Limits

As discussed at the end of Sec. II A, a key observation, by virtue of which we can proceed, is that |h(n)| is deterministic (and hence equal to its average) during both the removal and trimming steps. This is due to the structure of A k< and A d that have columns sums independent of the row index:

q k< ≡ i [A k< ] ij = -2 and q d ≡ i [A d ] ij = -2d
The only randomness occurs in the stopping time of the trimming step.

In this section the transition to the continuous time-variable t is performed. To that end we define the scaled process

η(t) = lim N0→∞ 1 N 0 h(tN 0 ) (12)
and presume that the derivative η (t) is equal to its expected change. Here N 0 stands for the initial number of vertices in the graph. Before proceeding to the analysis of corehd, let us first describe the solution for the two processes (removal and trimming) as if they were running separately. Let us indicate the removal process [START_REF] Altarelli | Optimizing spread dynamics on graphs by message passing[END_REF] and trimming processes [START_REF] Braunstein | Network dismantling[END_REF] with subscripts α = d and α = k < respectively. It then follows from ( 8) and ( 10) that the expected change is equal to

η α (t) = A α η α (t) |η α (t)| . ( 13
)
Owing to the deterministic nature of the drift terms A α we have

|η α (t)| = 1 + q α t (14)
and the above differential equation can be solved explicitly as

η α (t) = exp A α q α ln (1 + q α t) η α (0) . ( 15
)
We have thus obtained an analytic description of each of the two separate processes ( 8) and [START_REF] Braunstein | Network dismantling[END_REF].

Note that this implies that we can analytically predict the expected value of the random process in which all nodes of degree d are removed from a graph successively until none remains and then all nodes of degree smaller than k are trimmed. This already provides improved upper bounds on the size of the minimal contagious sets, that we report in Table II (cf. "two stages"). This "two stages" upper bound has the advantage that no numerical solution of differential equations is required. The goal, however, is to analyze the corehd procedure that merges the two processes into one, as this should further improve the bounds.

Crucially the running time of the trimming process depends on the final state of the removal process, i.e. the differential equations become nonlinear in η(t). As a consequence, they can no longer be brought into a simple analytically solvable form (at least as far as we were able to tell). To derive the differential equations that combine the removal and trimming processes and track corehd we will be working with the operators that are obtained from the "iterations", ( 8) and [START_REF] Braunstein | Network dismantling[END_REF], in the continuous limit [START_REF] Bau | Decycling numbers of random regular graphs[END_REF]. The evolution within an infinitesimally small removal step (α = d), respectively trimming step (α = k < ), follows from [START_REF] Bau | Decycling numbers of random regular graphs[END_REF] to

η α (t + δt) = Tα (δt, t)η α (t) , (16)
where we defined the propagator

Tα (δt, t) = 1 + A α |η α (t)| δt .
In what follows we will be considering the removal and trimming processes to belong to one and the same process and therefore η(t) will no longer be carrying subscripts. Upon combination a full step in the combined process in terms of the operators then reads

η (t + δt) = Tk< ( δt, t + δt) Td (δt, t) η (t) . ( 17
)
Note that one infinitesimal time step is the continuous equivalent of the removal of one degree d node, together with the resulting cascade of degree < k nodes. It is for that reason that the final continuous time after which the k-core vanishes will be directly related to the size of the set D in Algorithm 1. Note also that in Tk< ( δt, t + δt) we replaced the running time with the operator δt. It acts on a state to its right and can be computed from the condition that all the nodes of degree smaller k must be trimmed after completing a full infinitesimal step of the combined process, so that

η k< (t + δt) ! = 0 . ( 18
)
Requiring this condition in eq. ( 17) we get from an expansion to linear order in δt that

δt = δt • - [A d η(t)] k< [A k< η(t)] k< . (19)
Once again, we recall that [v] k< denotes the first component of the vector v. We can now use this equation to eliminate the dependence on δt in the combined operator Tk< ( δt, t) Td (δt, t). Using ( 16) and keeping only first order terms in δt in [START_REF] Nicholas | Differential equations for random processes and random graphs[END_REF] yields

η(t + δt) = η(t) + - [A d η(t)] k< [A k< η(t)] k< A k< + A d η(t) |η(t)| δt, (20)
which leads us to the following differential equation

η (t) = [ϕ (η(t)) A k< + A d ] η(t) |η(t)| . ( 21
)
The nonlinearity ϕ(•) is directly linked to the trimming time and defined as

ϕ (η(t)) ≡ - [A d η(t)] k< [A k< η(t)] k< = - d (-η k< (t) + (k -1)η k (t)) -|η(t)| -η k< (t) + (k -1)η k (t) = d (k -1)η k (t) |η(t)| -(k -1)η k (t) . ( 22
)
To obtain the last equality in [START_REF] Achlioptas | Lower bounds for random 3-SAT via differential equations[END_REF] we used the trimming condition, i.e. set η k< (t) = 0. The initial conditions are such that the process starts from the k-core of the original graph. This is achieved by solving [START_REF] Zhou | Spin glass approach to the feedback vertex set problem[END_REF], with α = k < , for arbitrary initial degree distribution η(0) (without bounded maximum degree) until η k< (t) = 0. Hence, the set of differential equations defined by ( 21) can be written explicitly as

η k< (t) = 0 (23)
η i (t) = d • i • -η i (t) + η i+1 (t) |η(t)| -(k -1)η k (t) for k ≤ i < d (24)
η d (t) = -d + d 2 • -η d (t) |η(t)| -(k -1)η k (t) . (25)

D. Rigorous Analysis

A rigorous analysis of the k-core peeling process for Erdős-Rényi graphs is presented in [START_REF] Pittel | Sudden emergence of a giant k-core in a random graph[END_REF]. This analysis is based on the Wormald approach [START_REF] Nicholas | Differential equations for random processes and random graphs[END_REF] but the presentation in [START_REF] Pittel | Sudden emergence of a giant k-core in a random graph[END_REF] is more complicated because it derives an exact formula for the threshold and there are technical challenges as the process terminates. For random graphs drawn from the configuration model, however, the standard Wormald approach [START_REF] Nicholas | Differential equations for random processes and random graphs[END_REF] provides a simple and rigorous numerical method for tracking the macroscopic dynamics of the peeling algorithm when the maximum degree is bounded and the degree distribution remains positive. The primary difficulty occurs near termination when the fraction of degree < k edges becomes very small.

The peeling process in corehd alternates between deleting maximum-degree nodes and degree < k edges and this introduces a similar problem for the Wormald method. In particular, the corehd peeling schedule typically reduces the fraction of maximum-degree nodes to zero at some point and then the maximum degree jumps downward. At this jump, the drift equation is not Lipschitz continuous and does not satisfy the necessary conditions in [START_REF] Nicholas | Differential equations for random processes and random graphs[END_REF]. More generally, whenever there are hard preferences between node/edge removal options (i.e., first delete largest degree, then 2nd largest degree, etc.), the same problem can occur.

For corehd, one solution is to use weighted preferences where the removal of degree < k edges is most preferred, then removal of degree-d nodes, then degree d -1 nodes, and so on. In this case, the drift equation remains Lipschitz continuous if the weights are finite but the model dynamics only approximate the corehd algorithm dynamics. In theory, one can increase the weights to approximate hard preferences but, in practice, the resulting differential equations become too numerically unstable to solve efficiently. A better approach is to use the operator limit described in Section II C. Making this rigorous, however, requires a slightly more complicated argument.

The key argument is that the k-core peeling step (after each maximum-degree node removal) does not last too long or affect too many edges in the graph. A very similar argument (dubbed the Lazy-Server Lemma) is used in the analysis of low-complexity algorithms for solving K-SAT problems [START_REF] Achlioptas | Setting 2 variables at a time yields a new lower bound for random 3-SAT[END_REF][START_REF] Achlioptas | Lower bounds for random 3-SAT via differential equations[END_REF]. In both cases, a suitable stability (or drift) condition is required. In this work, we use the following lemma.

Lemma 1. For some δ > 0, suppose h

(n) satisfies h k (n) ≤ 1-3δ k-1 |h(n)| and M |h(n)| ≥ M 0 (δ).
Consider the corehd process where a maximum-degree node is removed and then the trimming operation continues until there are no edges with degree less than k (see (3)). Let the random variable T denote the total number of trimming steps, which also equals the total number edges removed by the trimming operation. Then, we have

Pr T > (k -1) 2 δ -2 ln M ≤ M -2 .
Proof. See Appendix A 1. Lemma 2. Let η(t) be the solution to the operator-limit differential equation (21) at time t starting from η(0) = 1 N h(0). Assume, for some δ > 0, there is a

t 0 > 0 such that 1 η k (t) ≤ 1-4δ k-1 |η(t)| and |η(t)| ≥ δ for all t ∈ [0, t 0 ]. Then, there is C > 0 such that Pr sup t∈[0,t0] η(t) - 1 N h( N t ) > C N 1/4 = O N -1 . Proof. See Appendix A 2.
Theorem 1. The multistage corehd process converges, with high probability as N → ∞, to the piecewise solution of the operator-limit differential equation.

Sketch of Proof. The first step is recalling that the standard k-core peeling algorithm results in graph distributed according to the configuration model with a degree distribution that, with high probability as N → ∞, converges to the solution of the standard k-core differential equation [START_REF] Pittel | Sudden emergence of a giant k-core in a random graph[END_REF]. If k-core is not empty, then the corehd process is started. To satisfy the conditions of [25, Theorem 5.1], the process is stopped and restarted each time the supply of maximum-degree nodes is exhausted. Since the maximum degree is finite, this process can be repeated to piece together the overall solution. Using Lemma 2, we can apply [START_REF] Nicholas | The differential equation method for random graph processes and greedy algorithms[END_REF]Theorem 5.1] at each stage to show the corehd process follows the differential equation [START_REF] Achlioptas | Setting 2 variables at a time yields a new lower bound for random 3-SAT[END_REF]. It is important to note that the cited theorem is more general than the typical fluid-limit approach and allows for unbounded jumps in the process as long as they occur with low enough probability.

E. Evaluating the results

Here we clarify how the upper bound is extracted from the equations previously derived. Note that the nonlinearity ( 22) exhibits a singularity when

|η(t)| = (k -1)η k (t) , (26)
that is, when the gain (r.h.s.) and loss (l.h.s.) terms in the trimming process are equal. This can be either trivially true when no more nodes are left, |η(t)| = 0, or it corresponds to an infinite trimming time. The latter is precisely the point where the size of the k-core jumps downward discontinuously, whereas the first case is linked to a continuous disappearance of the k-core. Either of these two cases define the stopping time t s of the differential process [START_REF] Achlioptas | Setting 2 variables at a time yields a new lower bound for random 3-SAT[END_REF]. By construction the stopping time t s provides the size of the set D that contains all the nodes the corehd algorithm removed to break up the k-core. It hence also provides an upper bound on the size of the minimal contagious set, i.e. the smallest such set that removes the k-core.

Note that η(t s -) (for an infinitesimally small ) gives the size of the k-core, right before it disappears. For all the cases investigated in this paper we found that solving eqs. [START_REF] Cocco | Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms[END_REF][START_REF] Pittel | Sudden emergence of a giant k-core in a random graph[END_REF][START_REF] Nicholas | The differential equation method for random graph processes and greedy algorithms[END_REF] for k = 2 yields a continuous disappearance of the 2-core, and for k ≥ 3 the stopping criteria yield discontinuous disappearance of the k-core.

Algorithm 2: Analysis of corehd. Recall that indices are k < are referring to the first component of a vector, k to the second and so forth until the last component d. Data: Initial degree distribution Q(q); k Result: The relative size of set of removed nodes, t s .

1Initialize half-edges: 0) with t 0 such that η k< (t 0 ) = 0 and A k< defined in [START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF]; 3Set: d ← the degree associated to the last non-zero component of η 0 ; t s ← 0 ; 4while stop = true do Solve: In order to solve the above set of ODEs numerically, we first use equation ( 15) to trim away nodes of color k < , i.e. reduce the graph to it's k-core. Then we use equation ( 20) recursively, until the last component η d is zero. Subsequently we reduce η by removing its last component, send d → d -1, adapt the drift term (9) and repeat with the reduced η and initial condition given by the result of the previous step. All this is performed until the stopping condition ( 26) is reached. We summarize the procedure in a pseudo-code in Algorithm 2, for our code that solves the differential equations see open depository [20].

η(0) = k-1 i=1 i • Q(i), k • Q(k), (k + 1) • Q(k + 1), . . . , d • Q(d) T ; 2Compute distribution of half-edges in the k-core: η 0 = exp - A k < 2 • ln (1 -2t 0 ) η(
η (t) = d(k -1)η k (t) |η(t)| -(k -1)η k (t) A k< + A d η(
Example: two-cores on three regular random graphs. For a simple example of how to extract the upper bound consider the following case. We have k = 2 and d = 3 and we set k < = 1, then the differential equation in [START_REF] Achlioptas | Setting 2 variables at a time yields a new lower bound for random 3-SAT[END_REF] becomes

η 1 (t) = 0 (27) η 2 (t) = 6 • 1 - η 2 (t) η 3 (t) (28) η 3 (t) = -12 , (29)
with initial condition η(0) = d • e d because there are dN half-edges, all connected to nodes of degree d initially. The equations are readily solved

η 1 (t) = 0 (30) η 2 (t) = 3 • √ 1 -4t • 1 - √ 1 -4t (31) η 3 (t) = 3 • (1 -4t) ; ( 32
)
According to [START_REF] Ackerman | Combinatorial model and bounds for target set selection[END_REF] the stopping time is t s = 1/4, i.e. |D| = N/4, which suggests that the decycling number (2-core) for cubic random graphs is bounded by N/4 + o(N ). In accordance with Theorem 1.1 in [START_REF] Bau | Decycling numbers of random regular graphs[END_REF] this bound coincides with the actual decycling number. For d > 3 the lower and upper bounds do not coincide an the stopping time resulting from our approach only provides an upper bound.

Finding a closed form expression for the generic case is more involved and we did not manage to do it. However, very reliable numerical resolution is possible. The simplest approach to the differential equations is to work directly with (20) as indicated in Algorithm 2.

F. corehd analyzed and compared with existing results

In this section we evaluate the upper bound on minimal contagious set obtained by our analysis of corehd. In Figure 1 we compare the fraction of nodes of a given degree that are in the graph during the corehdprocedure obtained from solving the differential equations and overlay them with averaged timelines obtained from direct simulations of the algorithm.

Table I then compares direct numerical simulations of the corehd algorithm with the prediction that is obtained from the differential equations. The two are in excellent agreement, for the analysis higher precision can be obtained without much effort. When analyzing Erdős-Rényi graphs it is necessary to restrict the largest degree to avoid an infinite set of differential equations. The error resulting from that is exponentially small in the maximum degree, and hence in practice insignificant.

Confident with this cross-check of our theory, we proceed to compare with other theoretical results. As stated in the introduction, Guggiola and Semerjian [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF] have derived the size of the minimal contagious sets for random regular graphs using the cavity method. At the same time, several rigorous upper bounds on size of the minimal contagious set exist [START_REF] Reichman | New bounds for contagious sets[END_REF][START_REF] Coja-Oghlan | Contagious sets in expanders[END_REF][START_REF] Ackerman | Combinatorial model and bounds for target set selection[END_REF]. In particular the authors of [START_REF] Bau | Decycling numbers of random regular graphs[END_REF] provide upper bounds for the decycling number (2-core) that are based on an analysis similar to ours, but of a different algorithm. 2 In table II we compare the results from [START_REF] Bau | Decycling numbers of random regular graphs[END_REF] with the ones obtained from our analysis and the presumably exact results from [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF]. We clearly see that while corehd is not quite reaching the optimal performance, yet the improvement over the existing upped bound is considerable.

In table III we quantify the gap between our upper bound and the results of [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF] for larger values of k. Besides its simplicity, the corehd algorithm provides significantly better upper bounds than those known before. Clearly, we only consider a limited class of random graphs here and the bounds remain away from the conjectured optimum. However, it is worth emphasizing that previous analyses were often based on much more involved algorithms. The .0184 [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF] .01842 .95038 ---Table I. Comparison between direct simulations of the corehd Algorithm 1 and the theoretical results for random graphs of different degree d and core-index k. The left hand side of the table reports results for random regular graphs, the right hand side for Erdős-Rényi random graphs of the corresponding average degree. The simulation results are averaged over 50 runs on graphs of size N = 2 19 . The fractions of removed nodes agree up to the last stable digit (digits in brackets are fluctuating due to finite size effects). We also list the size of the k-core just before it disappears (in the column "final core"). Table II. Best known upper bounds on the minimal decycling sets by [START_REF] Bau | Decycling numbers of random regular graphs[END_REF], compared to the upper bounds obtained from our analysis when all nodes of maximum degree are removed before the graph is trimmed back to its 2-core (two stages), and to our analysis of corehd . The last column gives the non-algorithmic cavity method results of Guggiola and Semerjian [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF] that provide (non-rigorously) the actual optimal sizes.

d (degree) Bau,
analysis in [START_REF] Coja-Oghlan | Contagious sets in expanders[END_REF] or the procedure in [START_REF] Bau | Decycling numbers of random regular graphs[END_REF] are both based on algorithms that are more difficult to analyze.

III. IMPROVING COREHD

The main focus of this paper has been, up until now, the analysis of corehd on random networks. Rather naturally the question of how to improve over it raises. In this section we evaluate the possibility of a simple local strategy that systematically improves over the corehd performance. We show that introducing additional local information about the direct neighbors of a node into the decision process can significantly improve the performance, while essentially conserving the time complexity.

The corehd algorithm (Alg. 1) does not take into account any information of the neighborhood of a node. The theoretical analysis in the previous section owes its simplicity to this fact. However, the idea behind corehd can be extended to the next order by considering the structure of the nearest neighbors of a node. Once we include the nearest neighbors the number of options is large. Our aim is not to make an extensive study of all possible strategies, but rather to point out some heuristic arguments that lead to improvement.

According to the previous section, selecting high degree nodes is a good strategy. Another natural approach is a greedy strategy that, in each step, selects a node such that the caused cascade of nodes dropping out of the core is maximized [START_REF] Coja-Oghlan | Contagious sets in expanders[END_REF][START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF][START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF]. In the following we list some strategies that aim to somehow combine these two on the level of the direct neighborhood of a node. corehdld: This approach selects high degree nodes, but then discriminates those that have many neighbors of high degree. The idea is that nodes that have neighbors of large degree might get removed in the trimming procedure preferentially and hence the degree of the node in question will likely decrease. More specifically we implemented the following:

• First select the set M ← {i ∈ V C | i = arg max i [d i ]} and then update it according to M ← {i ∈ M | i = arg max i j∈∂i I [d j < d i ] }.
weak-neighbor: The weak-neighbor strategy aims to remove first those nodes that have high degree and low average degree of the neighbors, thus causing a larger trimming step on average. There are different ways to achieve this. We tried two strategies that both yield very similar results on all the cases considered. These two strategies are • The order in which the nodes are removed is according to arg max i d i -s i with d i being the degree of node i and s i the average degree of the neighbors of i.

• We separate the two steps. First select the set M ← {i ∈ V C | i = arg max i [d i ]} and then update it according to M ← {i ∈ M | i = arg min i j∈∂i d j }.

Our implementation of the weak-neighbor algorithm is available in the open depository [20]. corehd-critical: The coreHD-critical combines the corehd with the vanilla-greedy algorithm on the direct neighbors. Nodes are first selected according to their degree and subsequently among them we remove nodes first that have the largest number of direct neighbors that will drop out in the trimming process.

• First select the set M ← {i ∈ V C | i = arg max i [d i ]} and then update it according to M ← {i ∈ M | i = arg max i j∈∂i I [d j ≤ k] }.
Finally it is interesting to contrast the stated algorithms with a version in which the high degree selection step is left out Table III. Performance results of three algorithms: citm (with L = 10), corehd, weak-neighbor (with arg maxi di -si). As well as the conjectured optimal results obtained non-constructively via the cavity method in [START_REF] Guggiola | Minimal contagious sets in random regular graphs[END_REF].

, i.e. select M ← {i ∈ V C | i = arg max i j∈∂i I [d j ≤ k] }
Let us summarize the results. First, we find that all above strategies improve over the corehd algorithm (at least in some regimes). Second, we find that among the different strategies the weak-neighbor algorithm performs best. While we have systematic numerical evidence that the weak-neighbor strategy performs best, it is not clear which are the effects responsible. What we can say for sure is that the generic locally greedy procedure of trying to reduce the size of the k-core at every step is not optimal.

The most commonly considered greedy procedures do consider information not only from the direct neighborhood of a node. The vanilla-greedy approach removes nodes according to the size of cascade that is caused by their removal. 3Nodes are removed first that cause the largest cascade of nodes dropping out in the subsequent trimming process. The high degree version of this approach additionally focusses on the nodes of maximum degree, e.g. by picking nodes according to arg max i [d i + s i ] with s i now being the size of the corona, this time not limited to the direct neighborhood, but rather the total graph. Here we merely report that this greedy procedures tend to perform worse than weak-neighbor when k d -1 and becomes comparable when k ≈ d -1. Next we contrast the corehd performance and the weak-neighbor performance with the performance of recently introduced [START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF] algorithm citm-L that uses neighborhood up to distance L and shown in [START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF] to outperform a range of more basic algorithm. In figure 2 we compare the performances of the weak-neighbor algorithm, corehd, and citm-10 (beyond L = 10 resulted in negligible improvements) on Erdős-Rényi graphs. We observe that the weakneighbor algorithm outperforms not only the corehd algorithm, but also the citm algorithm. We conclude that the optimal use of information about the neighborhood is not given by the citm algorithm. What the optimal strategy, that only uses local information up to a given distance, remains an intriguing open problem for future work.

To discuss a little more the results observed in Figure 2, for small k the corehd algorithm outperforms the citm algorithm, but when k is increase the performance gap between them shrinks, and for large k (e.g. in Fig. 2 part (a)) CIMT outperforms corehd. Both corehd and citm are outperformed by the weak-neighbor algorithm in all the cases we tested. In addition to the results on Erdős-Rényi graphs in figure 2 we summarize and compare all the three considered algorithms and put them in perspective to the cavity method results on regular random graphs in table III.

Finally, following up on [START_REF] Braunstein | Network dismantling[END_REF] we mention that in applications of practical interest it is possible to improve each of the mentioned algorithm by adding an additional random process that attempts to re-insert nodes. Consider the set S ⊂ G of nodes that, when removed, yield an empty k-core. Then find back the nodes in S that can be re-inserted into the graph without causing the k-core to re-appear.

IV. CONCLUSION

In this paper we study the problem of what is the smallest set of nodes to be removed from a graph so that the resulting graph has an empty k-core. The main contribution of this paper is the theoretical analysis of the performance of the corehd algorithm, proposed originally in [1], for random graphs from the configuration model with bounded maximum degree. To that end a deterministic description of the associated random process on sparse random graphs is derived that leads to a set of non-linear ordinary differential equations. From the stopping time -the time at which the k-core disappears -of these differential equations we extract an upper bound on the minimal size of the contagious set of the underlying graph ensemble. The derived upper bounds are considerably better than previously known ones.

Next to the theoretical analysis of corehd we proposed and investigated numerically several other simple strategies to improve over the corehd algorithm. All these strategies conserve the essential running time of O(N ) on graphs with maximum degree of O(1). Among our proposals we observe the best to be the weak-neighbor algorithm. It is based on selecting large degree nodes from the k-core that have neighbors of low average degree. In numerical experiments on random regular and Erdős-Rényi graphs we show that the weak-neighbor algorithm outperforms corehd, as well as other scalable state-of-the-art algorithms [START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF].

There are several directions that the present paper does not explore and that would be interesting project for future work. One is generalization of the differential equations analysis to the weak-neighbor algorithm. This should in principle be possible for the price of having to track the number of neigbors of a given type, thus increasing considerably the number of variables in the set of differential equations. Another interesting future direction is optimization of the removal rule using node and its neigborhood up to a distance L. It is an open problem if there is a method that outperforms the WN algorithm and uses only information from nearest neighbors. Yet another direction is comparison of the algorithmic performance to message passing algorithms as developed in [START_REF] Altarelli | Optimizing spread dynamics on graphs by message passing[END_REF][START_REF] Altarelli | Large deviations of cascade processes on graphs[END_REF]. Actually the work of [START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF] compares to some version of message passing algorithms and finds that the CIMT algorithm is comparable. Our impression is, however, that along the lines of [START_REF] Braunstein | Network dismantling[END_REF] where the message passing algorithm was optimized for the dismantling problem, analogous optimization should be possible for the removal of the k-core, yielding better results. This is an interesting future project.

V. ACKNOWLEDGEMENT

We are thankful to the authors of [START_REF] Sen | Efficient collective influence maximization in cascading processes with first-order transitions[END_REF] for sharing their implementation of the citm algorithm with us. We would further like to thank Guilhem Semerjian for kind help, comments and indications to related work. LZ acknowledges funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No 714608 -SMiLe). This work is supported by the "IDI 2015" project funded by the IDEX Paris-Saclay, ANR-11-IDEX-0003-02

[1] Lenka Zdeborová, Pan Zhang, and Hai-Jun Zhou, "Fast and simple decycling and dismantling of networks," Scientific Reports 6 (2016).

quickly when h(n) satisfies the stated conditions. Then, the fluid limit of the corehd process follows from [START_REF] Nicholas | The differential equation method for random graph processes and greedy algorithms[END_REF]Theorem 5.1].

To apply [START_REF] Nicholas | The differential equation method for random graph processes and greedy algorithms[END_REF]Theorem 5.1], we first fix some δ > 0 and choose the valid set D to contain normalized degree distributions satisfying η k (t) ≤ 1-4δ k-1 |η(t)| and |η(t)| ≥ δ. This choice ensures that Lemma 1 can be applied uniformly for all η(t) ∈ D. Now, we describe how the constants are chosen to satisfy the necessary conditions of the theorem and achieve the stated result. For condition (i) of [START_REF] Nicholas | The differential equation method for random graph processes and greedy algorithms[END_REF]Theorem 5.1], we will apply Lemma 1 but first recall that the initial number of nodes in the graph is denoted by N and hence |η(t)| ≥ δ implies M = |h(n)| ≥ BN with high probability for some B > 0. Thus, condition (i) can be satisfied by choosing4 β(N ) = (k -1) 2 δ -2 d ln N applying Lemma 1 with M = BN to see that γ(N ) = O(N -2 ). To verify condition (ii) of the theorem, we note that ( 21) is derived from the large-system limit of the drift and the error λ(n) can be shown to be O(N -1 ). To verify condition (iii) of the theorem, we note that that ( 21) is Lipschitz on D. Finally, we choose λ(N ) = N -1/4 ≥ λ 1 (N ) + C 0 N γ(N ) for large enough N . Since β(N )/λ(N )e -N λ(N ) 3 /β(N ) 3 = O ln N N -1/4 e -AN 1/4 /(ln N ) 3 = O N -1 , these choices imply that the corehd process concentrates around η(t) as stated. We only sketch this proof because very similar arguments have used previously for other graph processes [START_REF] Achlioptas | Setting 2 variables at a time yields a new lower bound for random 3-SAT[END_REF][START_REF] Achlioptas | Lower bounds for random 3-SAT via differential equations[END_REF][START_REF] Cocco | Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms[END_REF].

5

 5

Figure 1 .

 1 Figure 1. Comparison of the solution of the differential equation Algorithm 2 with a direct simulations of the corehd algorithm on several graphs of 2 14 nodes, here with d = 7 and k = 2 (left hand side) and k = 3 (right hand side). The time t is directly related to the fraction of removed nodes of degree ≥ k. For k = 2 the k-core disappears continuously at ts = 0.5006, for k = 3 discontinuously at ts = 0.3376.

Figure 2 .

 2 Figure 2. (a)A typical transition of three algorithms, with L for the citm set to the size of the graph. When k is increased the gap between the citm algorithm and the corehd algorithm closes and they become close in terms of performance. However, there remains a gap to the weak-neighbor algorithm. (b) Comparison of the three algorithms (here citm with L = 10) on ER graphs for different k and vary the average degree. Compare also table III for results on regular random graphs.

  t) |η(t)| with initial condition η 0 . Until either η d (t * ) = 0 or |η(t * )| = (k -1)η k (t * ) ; // A k< and A d defined by (11) and (9) with d set to the current largest degree

6 Update:

t s ← t s + t * ; 7 if |η(t * )| = 0 or |η(t * )| = (k -1)η k (t * ) then

8 stop ← true; 9 else 10 η 0 ← η k<:d-1 (t * ) ; 11 d ← d -1 ; 12 end 13end

  RRG corehd RRG theory final core ERG corehd ERG theory final core

	3 2	.2500(0)	.25000	0	.1480(7)	.14809	0
	4 2	.3462(3)	.34624	0	.2263(0)	.22634	0
	3	.0962(5)	.09623	.67349	.0388(5)	.03887	.32718
	5 2	.4110(7)	.41105	0	.2924(8)	.29240	0
	3	.2083(6)	.20832	.48428	.1068(2)	.10679	.33105
	4	.0476(9)	.04764	.85960	-	-	-
	6 2	.4606(2)	.46063	0	.3480(8)	.34816	0
	3	.2811(2)	.28107	.40916	.1700(1)	.16994	.34032
	4	.1401(1)	.14007	.68672	.0466(0)	.04662	.46582
	5	.0280(7)	.02809	.92410	-	-	-
	7 2	.5006(0)	.50060	0	.3954(7)	.39554	0
	3	.3376(1)	.33757	.36179	.2260(0)	.22597	.32878
	4	.2115(0)	.21150	.58779	.1043(2)	.10429	.46788
	5	.1010(2)	.10100	.78903	.0088(5)	.00882	.54284
	6

d k

  Wormald, Zhou two stages corehd cavity method

	3	.25	.3750	.25	.25
	4	.3955	.3913	.3462	.3333
	5	.4731	.4465	.4110	.3785
	6	.5289	.4911	.4606	.4227
	7	.5717	.5278	.5006	.4602

  and then remove at random from this set.

	d k citm-10 corehd weak-neighbor cavity method
	3 2	.254	.2500	.2500	.25000
	4 2	.365	.3462	.3376	.33333
	3	.077	.0963	.0744	.04633
	5 2	.437	.4111	.3965	.37847
	3	.205	.2084	.1876	.16667
	4	.032	.0477	.0277	.01326
	6 2	.493	.4606	.4438	.42270
	3	.296	.2811	.2644	.25000
	4	.121	.1401	.1081	.07625
	5	.019	.0281	.0134	.00582
	7 2	.540	.5006	.4831	.46023
	3	.362	.3376	.3206	.30009
	4	.207	.2115	.1813	.15006
	5	.081	.1010	.0686	.04289
	6	.013	.0185	.0077	.00317

The first condition implies that the denominator of (22) is positive.

The numerical values, provided for the bounds in[START_REF] Bau | Decycling numbers of random regular graphs[END_REF] are actually not correct, as the authors realized and corrected in a later paper[START_REF] Hoppen | Induced forests in regular graphs with large girth[END_REF]. We acknowledge the help of Guilhem Semerjian who pointed this out.

Note that such greedy algorithms have O(N 2 ) running time.

The additional factor of d is required because each trimming step can change the number of degree-j edges by at most d.

Based on some worst-case assumptions, we can analyze the evolution of the number of degree-k < edges. In particular, in the worst case, the initial removal of a degree-d node can generate d(k -1) degree-k < edges (i.e., all of its edges were attached to degree-k nodes). During removal, the number of degree-k edges can also increase by at most dk. Though both of these events cannot happen simultaneously, our worst-case analysis includes both of these effects.

During the m-th trimming step, a random edge is chosen uniformly from the set of edges adjacent to nodes of degree k < (i.e., degree less than k). Let the random variable Z m ∈ {k < , k, k + 1, . . . , d} equal the degree of the node adjacent to the other end and the random variable X m equal the overall change in the number of degree-k < edges.

For m = 1, this edge is distributed according to

where h z denotes the number of edges of degree z before trimming. If Z 1 = k < , then the edge connects two degree-k < nodes and removal reduces the number of k < edges by X 1 = -2. If Z 1 = k, then the edge connects a degree-k node with a degree-k < node and removal reduces the number of degree-k edges by k and increases the number of degree-k < edges by X 1 = k -2. If Z 1 > k, then removal decreases the number of degree-Z 1 edges by Z 1 and increases the number of degree-(Z 1 -1) edges by Z 1 -1. In this case, the number of degree-k < edges is changed by

The crux of the analysis below is to make additional worst-case assumptions. One can upper bound the probability of picking degree-k edges because, after m steps of trimming, the number of degree-k edges can be at most h k +dk+mk (i.e., if initial node removal generates dk edges of degree-k and Z m = k + 1 during each step of trimming). Also, one can upper bound the number of degree-k < edges because at least one is removed during each step. To upper bound the random variable T , we use the following worst-case distribution for X m ,

In this formula, the 2d term represents initial removal of a degree-d node and the 2m term represents the edge removal associated with m steps of trimming. We note that, since edges attach two nodes of different degrees, all edges are counted twice in h. Similarly, the dk term represents the worst-case increase in the number of degree-k edges during the initial removal. Now, we can upper bound the number of degree-k < edges after m steps of trimming by the random sum

where each X i is drawn independently according to the worst-case distribution (A1). The term d(k -1) represents the worst-case event that the initial node removal generates d(k -1) edges of degree-k < . By choosing M 0 (δ) appropriately, our initial assumption about h implies that E[X i ] ≤ -2δ for all M > M 0 (δ). Thus, the random variable S m will eventually become zero with probability 1. Since S m upper bounds the number of degree-k < edges after m steps of trimming, when it becomes zero (say at time m ), it follows that the stopping time satisfies T ≤ m .

To complete the proof, we focus on the case of m = (k -1) 2 δ -2 ln M . Since the distribution of X m gradually places more weight on the event X m = k -2 as m increases, we can also upper bound S m by replacing X 1 , . . . , X m -1 by i.i.d. copies of X m . From now on, let Y denote a random variable with the same distribution as X m and define Next, we observe that (A1) converges in distribution (as M → ∞) to a two-valued random variable Y * that places probability at most 1-3δ k-1 on the point k -2 and the remaining probability on -1. Since E[Y * ] = -3δ, there is an M 0 (δ) such that E[Y ] = -2δ for all M > M (δ) Finally, Hoeffding's inequality implies that

Putting these together, we see that

for m > d(k -1)/δ. As m = (k -1) 2 δ -2 ln M , the last condition can be satisfied by choosing M (δ) > e δ 2 d/(k-1) . Since this condition is trivial as δ → 0, the previous convergence condition will determine the minimum value for M 0 (δ) when δ is sufficiently small.

Proof Sketch for Lemma 2

We note that graph processes like corehd often satisfy the conditions necessary for fluid limits of this type. The only challenge for the corehd process is that the h(n) process may have unbounded jumps due to the trimming operation. To handle this, we use Lemma 1 to show that, with high probability, the trimming process terminates