betaFeedback

WorksComputer Science

Batch-Dynamic Coreness and Applications with Logarithmic Work via Balanced Pressures

Abstract

We give a parallel algorithm that maintains a one-sided (2+ε)(2+\varepsilon)-approximation of all core numbers under batches of edge insertions and deletions. For fixed ε>0\varepsilon>0, the expected amortized work is O(log⁡n)O(\log n) per edge update, and each batch has deterministic polylogarithmic depth. This improves on the previously known (4+ε)(4+\varepsilon)-approximation and O(log⁡2n)O(\log^2 n) amortized work bounds. This approximation factor approaches the factor-two limit for polylogarithmic update and query time under the OMv conjecture. Our algorithm is based on assigning each vertex a "pressure" and splits each edge's unit load smoothly between its endpoints according to their pressures. After each batch of updates, our dynamic algorithm adjusts the pressures of vertices in parallel to restore balance between the pressures and loads. We show that by maintaining balanced pressures we can obtain good approximations of core numbers. Our construction also gives a (1+ε)(1+\varepsilon)-approximation of the densest-subgraph value with logarithmic expected amortized work and supports batch-dynamic maximal matching, clique counting, forest decomposition, and coloring in low-arboricity graphs with improved or matching work bounds. We give a practical implementation of our batch-dynamic coreness algorithm and find that it is able to achieve smaller empirical error than the state-of-the-art parallel batch-dynamic implementation, while running faster. On six real-world graphs, it runs 32×32\times faster than that implementation in geometric mean and 4.1×4.1\times faster than a state-of-the-art heuristic baseline. On three graphs with up to 1.8 billion edges, it is 9.2×9.2\times faster than the heuristic baseline.

Introduction

The core number of a vertex measures how well it is connected within a cohesive part of a graph. Formally, the kk-core is the largest subgraph in which every vertex has degree at least kk, and the core number (or coreness) κ(v)\kappa(v) is the largest kk for which vv belongs to the kk-core. These nested subgraphs give a simple description of network structure [27] and help identify influential spreaders [21], among many other practical applications [1, 3, 26, 28].

The exact core numbers of every vertex can be computed in O(n+m)O(n+m) time by repeatedly peeling a vertex of minimum degree [5, 25]. However, maintaining coreness dynamically as the graph changes is much harder, as adding one edge to close a path into a cycle changes every core number from 1 to 2. Thus, an algorithm that explicitly maintains exact core numbers must sometimes update every vertex in response to one edge. Allowing for approximation in the core numbers allows algorithms to defer changes until they become significant, making it possible to achieve much lower work in theory and in practice.

In this paper, we study coreness in the fully dynamic setting, with both edge insertions and deletions, and allow updates to arrive in batches of any size. In particular, we are interested in the parallel batch-dynamic setting, where the goal is to process a batch with low work per edge update and low depth (i.e., the length of the longest chain of dependencies). This setting is a strict generalization of the classical dynamic setting, where we have a batch size of one.

Previous work. Sun et al. [29] gave the first algorithm for approximate core numbers with polylogarithmic update time. They provide a (4+ε)(4+\varepsilon)-approximation with O(log⁡2n)O(\log^2 n) amortized update time for constant ε>0\varepsilon>0. Liu et al. [24] introduced the parallel level data structure (PLDS), obtaining the same approximation guarantee with O(log⁡2n)O(\log^2 n) amortized work per update and polylogarithmic depth per batch. More recently, Ghaffari and Koo [16] obtained polylogarithmic worst-case work per update, again with a (4+ε)(4+\varepsilon)-approximation guarantee. Table 1 compares the bounds. We state all approximation factors in the one-sided convention κ(v)/c≤κ^(v)≤κ(v)\kappa(v)/c\le\widehat{\kappa}(v)\le\kappa(v), where κ(v)\kappa(v) is the true core number and κ^(v)\widehat{\kappa}(v) is its estimate; Section 2 explains the conversion between conventions used in this paper and prior papers.

Our result. We give a simple and practical batch-dynamic algorithm that improves both the approximation factor and the amortized work. For every 0<ε≤10<\varepsilon\le1 with 1/ε≤nO(1)1/\varepsilon\le n^{O(1)}, it maintains estimates satisfying

κ(v)2+ε≤κ^(v)≤κ(v)for every vertex v\frac{\kappa(v)}{2+\varepsilon}\le\widehat{\kappa}(v)\le\kappa(v)\qquad\text{for every vertex }v

after every batch, using O(ε−5log⁡n)O(\varepsilon^{-5}\log n) expected amortized work per update¹ and deterministic O(ε−3log⁡4n)O(\varepsilon^{-3}\log^4 n) depth per batch. For constant ε\varepsilon, the space is O(m+n)O(m+n). Theorem 3.2 gives the full statement. Thus the algorithm reduces the work from two logarithms to one while improving the previously stated approximation factor from about four to about two. Equivalently, rescaling our estimates gives a two-sided 2+ε\sqrt{2+\varepsilon} approximation.

AlgorithmOne-sided factorWork per updateWork guaranteeDepth per batch
Sun–Chan–Sozio [29]4+ε4+\varepsilonO(log⁡2n)O(\log^2 n)AmortizedSequential
Liu et al. (PLDS) [24]4+ε4+\varepsilonO(log⁡2n)O(\log^2 n)AmortizedO(log⁡2nlog⁡log⁡n)O(\log^2 n\log\log n)
Ghaffari–Koo [16], insertions4+ε4+\varepsilonO(log⁡9n)O(\log^9 n)Worst-caseO(log⁡7n)O(\log^7 n)
Ghaffari–Koo [16], deletions4+ε4+\varepsilonO(log⁡8n)O(\log^8 n)Worst-caseO(log⁡6n)O(\log^6 n)
This paper2+ε2+\varepsilonO(log⁡n)O(\log n)Expected amortizedO(log⁡4n)O(\log^4 n)

Table 1. Fully dynamic core-number bounds for constant ε>0\varepsilon>0. A factor cc means k~(v)/c≤k~(v)≤k(v)\widetilde{k}(v)/c\leq\widetilde{k}(v)\leq k(v) after rescaling estimates and reparameterizing accuracy. Work is per edge update; depth is per batch. The work and depth bounds of PLDS and Ghaffari–Koo hold w.h.p.; our work bound is in expectation and our depth bound is deterministic. The two Ghaffari–Koo rows describe update types of the same fully dynamic algorithm.

The factor of two is also a conditional limit on what a fast dynamic algorithm can achieve. Couto and Fernandes [12] show that, under the Online Matrix–Vector Multiplication (OMv) conjecture, no algorithm with polynomial preprocessing and polylogarithmic update and query time can achieve a one-sided (2−δ)(2-\delta) approximation for any fixed δ>0\delta>0. Our approximation approaches this threshold while using logarithmic expected amortized work.

Densest subgraph and other applications. Our data structure also gives a fully dynamic (1+ε)(1+\varepsilon)-approximation of the densest-subgraph value with O(log⁡n)O(\log n) amortized update time and constant query time, for fixed ε>0\varepsilon>0. To our knowledge, this is the first logarithmic update bound for this approximation guarantee, improving the O(log⁡2n)O(\log^2 n) amortized bound of Chekuri and Quanrud [11]. Their logarithmic-time variant allows an additive error; pure multiplicative approximations with polylogarithmic worst-case updates are also known [10, 16]. The batch-dynamic algorithm achieves O(log⁡n)O(\log n) expected amortized work per update and polylogarithmic depth per batch. It also reports the vertices of a (1+ε)(1+\varepsilon)-approximate densest subgraph G[S]G[S] in O(∣S∣+log⁡2n)O(|S|+\log^2 n) work and O(log⁡n)O(\log n) depth, with the same update bounds. Appendix § 9.§ 1 gives the proof.

The data structure also improves or matches work bounds in the low-arboricity framework for orientations, maximal matching, clique counting, forest decompositions, and coloring. Appendix § 9 gives the reductions and comparisons.

Experimental results. We implement the algorithm and compare it with PLDS and PLDSOpt on the six social and web graphs and the three largest graphs of [24], using insertion, deletion, and mixed batches of 10610^6 updates on 60 threads (§ 5). The implementation uses smaller parameters and a simpler rule for restoring balance than Theorem 3.2. Its accuracy remains provable for every parameter setting, while its work is measured. With parameters that give a guaranteed two-sided error bound of at most 3.8, below the 4.2 guaranteed for PLDS, it is faster than both PLDS and PLDSOpt on every input. On the six social and web graphs, it is 32× faster than PLDS and 4.1× faster than PLDSOpt in geometric mean (from 1.0× to 10.3×), and its average error is lower than that of PLDSOpt on 14 of the 18 combinations of graph and update type. On three graphs with up to 1.8 billion edges, it is 9.2× faster than PLDSOpt. Recomputing all core numbers from scratch after each batch is faster only when a batch changes a large part of the graph, about a fifth of the edges of livejournal.

Technical Overview

We now give an overview of the main idea. Each edge in the undirected graph contributes one unit of load that is divided (fractionally) between its endpoints. The portion assigned to an endpoint is its share of the edge. Together, these shares form a fractional orientation. The load ℓ(v)\ell(v) at vertex vv is the sum of the shares it receives from its incident edges. To determine the edge shares, we store a positive number p(v)p(v), called the pressure, at each vertex vv. For an edge uvuv with p(u)≤p(v)p(u)\leq p(v), vertex vv receives a share of 12(p(u)/p(v))s\frac{1}{2}(p(u)/p(v))^s and uu receives the remaining share 1−12(p(u)/p(v))s1-\frac{1}{2}(p(u)/p(v))^s. We set ss later to obtain the approximation guarantee.

Algorithm. We call the pressures balanced if the load ℓ(v)\ell(v) lies between (1−ε/8)p(v)(1-\varepsilon/8)p(v) and (1+ε/8)p(v)(1+\varepsilon/8)p(v) at every non-isolated vertex. Here ε\varepsilon is the same accuracy parameter as in the (2+ε)(2+\varepsilon)-approximation guarantee. Our algorithm maintains balanced pressures after every batch and uses them to estimate core numbers and support the other applications. We first delete the edges in the batch, reducing the loads at their endpoints. These deletions can leave pressures too high relative to loads, so the parallel rounds described below lower pressures as needed to restore balance. Before inserting new edges, we raise each affected vertex’s pressure to a constant fraction of its number of new incident edges, unless its pressure is already that high. We then insert the new edges, reset isolated vertices to the minimum pressure, and restore balance over parallel rounds. In each round, a vertex whose load is sufficiently above its pressure multiplies its pressure by a factor β>1\beta>1 to reduce its load. Similarly, a vertex whose load is sufficiently below its pressure divides its pressure by β\beta to increase its load. All of the updates within a round use the loads at the start of the round. We choose β=1+O(ε3/log⁡n)\beta=1+O(\varepsilon^3/\log n), so each share changes by only an O(ε)O(\varepsilon) fraction in a round. § 4.2 explains the choice of step size. We repeat these rounds until balance is restored. We prove that balanced pressures approximate core numbers and bound the work needed to restore balance.

Balanced pressures approximate core numbers. We show that, at every non-isolated vertex vv, a balanced pressure p(v)p(v) lies between k(v)/2k(v)/2 and k(v)k(v) to within a multiplicative (1±O(ε))(1\pm O(\varepsilon)) factor. For the lower bound on p(v)p(v), let k=k(v)k=k(v) and choose a vertex uu of minimum pressure in the kk-core. Each of its at least kk neighbors in the core has pressure at least p(u)p(u), so uu receives at least half the load of each edge to the core. Its load is therefore at least k/2k/2, and balance gives p(u)≥(1−O(ε))k/2p(u)\geq(1-O(\varepsilon))k/2. Since vv belongs to this core, p(v)≥p(u)p(v)\geq p(u), giving the lower bound for p(v)p(v).

For the upper bound on p(v)p(v), consider the non-isolated vertices in the prefix ending at vv in a peeling order. Each has at most k(v)k(v) neighbors appearing after it in the peeling order. We weight each vertex by a large power of its pressure and consider the sum of their weighted loads. We show that this sum is at most approximately k(v)k(v) times the sum of the weights. Specifically, the share rule bounds each edge’s contribution to this weighted sum by approximately the weight of its lower-pressure endpoint, which is no greater than the weight of the endpoint peeled first. Thus we can charge each edge to its earlier endpoint, giving the claimed bound on the weighted loads. Using balance, this becomes a bound on the weighted average pressure. Our choice of exponent makes this average close to the largest pressure in the prefix, which is at least p(v)p(v), and thus yields the bound p(v)≤(1+O(ε))k(v)p(v) \le(1+O(\varepsilon))k(v). We obtain the estimated core number k^(v)\widehat{k}(v) by dividing p(v)p(v) by a suitable factor 1+O(ε)1+O(\varepsilon), so that k^(v)≤k(v)\widehat{k}(v) \le k(v).

Amortized work. Our updates follow the multiplicative-weights approach [2, 4], adjusting pressures by small multiplicative factors in response to imbalances. We bound their cost using a nonnegative potential that accounts for both edge updates and the work of restoring balance. For each graph GG, we construct a function FGF_G of the pressures that is convex in their logarithms. Our potential is the current value of FGF_G minus its minimum over any pressure assignment, keeping GG fixed. We show that each moving vertex changes its pressure in a direction that decreases FGF_G. We choose steps small enough that, after all updates in a round, a vertex that raised its pressure still has load above pressure, and one that lowered its pressure still has load below pressure. These inequalities and convexity give a lower bound on the potential decrease over the whole round.

We next bound how much edge updates can increase the potential. We show that the pressure assignment minimizing FGF_G is “perfectly balanced”, i.e., each non-isolated vertex’s load equals its pressure. Since each edge contributes one unit of load, the pressures of the non-isolated vertices sum to the number of edges. We also show that inserting an edge never decreases the minimizing pressures and increases their sum by at most one. Using this bound and the corresponding bound for deletions, we show that each batch increases the potential by at most O(1)O(1) per edge update before the parallel rounds.

The potential starts at zero on the empty graph, and the batches add O(T)O(T) in total over a sequence of TT edge updates. Since the potential remains nonnegative, its total decrease over all rounds is at most O(T)O(T). For fixed ε\varepsilon, we show that each round’s expected work is at most O(log⁡n)O(\log n) times its potential decrease, giving O(Tlog⁡n)O(T\log n) expected work over all rounds.

Parallel rounds and aggregation. To bound the depth per batch, we analyze both the number of rounds and the depth of each round. For the round bound, we use a tighter balance tolerance to select moving vertices than to decide when to stop. With sufficiently small steps, a vertex still unbalanced after tt rounds must have increased or decreased its pressure by a factor of βt\beta^t. Since pressures remain between a positive constant and O(n)O(n), our choice of β\beta limits a batch to O(log⁡2n)O(\log^2 n) rounds for fixed ε\varepsilon.

To implement a round efficiently, we update the loads without scanning every neighbor of a vertex that is updating its pressure (a “moving” vertex). When a vertex changes its pressure, all shares it receives from much lower-pressure neighbors scale by the same factor. We store their total contribution in counters and update it with simple arithmetic, without scanning those neighbors. By allowing a small approximation error, we can also avoid updating those neighbors’ stored loads while the pressure gap remains large. For fixed ε\varepsilon, the moving vertex receives at least a constant share of each edge we scan. Its load is the sum of its edge shares, so the number of scanned edges is at most a constant times its load. The counter updates and neighbor processing have deterministic polylogarithmic depth. Section 3 establishes the properties of balanced pressures and the accuracy of the estimates. Section 4 gives the update algorithm, its data structure, and the work and depth analysis.

Preliminaries

Graphs. We consider undirected graphs without self-loops or parallel edges. For a graph G=(V,E)G=(V,E) we write n=∣V∣n=|V| and m=∣E∣m=|E|. The vertex set is fixed and the edge set changes over time, so mm always denotes the current number of edges. For a vertex vv, N(v)N(v) is its set of neighbors and deg⁡(v)=∣N(v)∣\deg(v)=|N(v)| is its degree. We write ln⁡\ln for the natural logarithm and log⁡\log for the base 2 logarithm.

Cores and core numbers. For an integer k≥0k \ge0, the kk-core of GG is the largest subgraph of GG in which every vertex has degree at least kk [27]. It is well defined because the union of two subgraphs of minimum degree at least kk again has minimum degree at least kk. The core number k(v)k(v) of a vertex vv, also called its coreness, is the largest kk such that vv belongs to the kk-core. Equivalently, k(v)k(v) is the largest kk such that vv lies in some subgraph of GG of minimum degree at least kk. A vertex without edges has core number 0.

All core numbers can be computed in O(n+m)O(n+m) time by peeling [5, 25], i.e., by repeatedly deleting a vertex of minimum degree from the remaining graph. Our analysis uses the following folklore property of the order in which peeling deletes the vertices.

Lemma 2.1 (Peeling order). Repeatedly delete a vertex of minimum degree from the remaining graph, breaking ties by choosing the smallest vertex ID, until no vertex is left. Let v1,…,vnv_1,\ldots,v_n be the vertices in the order of deletion. Then k(v1)≤⋯≤k(vn)k(v_1) \le\cdots\le k(v_n), and every viv_i has at most k(vi)k(v_i) neighbors among vi+1,…,vnv_{i+1},\ldots,v_n.

Approximate core numbers. An algorithm for approximate core numbers produces an estimate k^(v)\widehat{k}(v) for every vertex vv. Following Liu et al. [24], the estimate forms a c-approximation, for a number c≥1c \ge1, if

k(v)c≤k^(v)≤ck(v)for every vertex v.\frac{k(v)}{c} \le\widehat{k}(v) \le c k(v) \qquad\text{for every vertex } v.

The estimates of our algorithm are never larger than the core numbers. We call estimates a one-sided c-approximation if

k(v)c≤k^(v)≤k(v)for every vertex v.\frac{k(v)}{c} \le\widehat{k}(v) \le k(v) \qquad\text{for every vertex } v.

We can easily convert one form into the other. Multiplying a one-sided cc-approximation by c\sqrt{c} gives a c\sqrt{c}-approximation, and dividing a cc-approximation by cc gives a one-sided c2c^2-approximation.

Both conversions keep the ratio between the largest and the smallest value that the guarantee allows for k^(v)\hat{k}(v); this ratio is cc for a one-sided cc-approximation and c2c^2 for a cc-approximation.

Batch-dynamic updates. Initially the graph is empty, and is updated over a sequence of batch updates. Formally, a batch is a pair (D,I)(D,I), where D⊆ED \subseteq E is a set of edges to delete and II is a set of edges not in EE to insert; it changes the edge set from EE to (E∖D)∪I(E \setminus D) \cup I. A batch given as an arbitrary list of insertions and deletions can be brought into this form by grouping the operations by edge with a semisort (defined below) and keeping, for every edge, the outcome of its last operation. Each inserted or deleted edge is an update. After every batch, the algorithm holds an estimate for every vertex.

Work bounds are per update and amortized over the sequence: an algorithm takes O(w)O(w) amortized work per update if every sequence of batches with TT updates in total takes O(Tw)O(Tw) work. Depth bounds are per batch. A batch with a single update is an ordinary dynamic update, so the bounds include the sequential setting in which edges are inserted and deleted one at a time. A graph that is given at the start is inserted as one batch.

Model of computation. We analyze our algorithms in the work-depth model, specifically the binary-forking model with test-and-set of Blelloch et al. [8], with words of O(log⁡n)O(\log n) bits. The work of a computation is the total number of instructions executed, and its depth is the length of the longest chain of dependent instructions. The model is equivalent to the PRAM in work, and depth in it equals PRAM time up to a logarithmic factor [8]. A bound holds with high probability (w.h.p.) if it holds with probability at least 1−n−c1 - n^{-c} for every constant c≥1c \ge1.

Parallel primitives. Given a sequence A=(a1,…,aℓ)A = (a_1, \ldots, a_\ell), prefix sums returns (s1,…,sℓ)(s_1, \ldots, s_\ell), where si=∑j=1iajs_i = \sum_{j=1}^{i} a_j, and reduce returns sℓs_\ell. Given a constant-time predicate pp, filter returns the subsequence of AA satisfying pp, preserving its order. Each primitive takes O(ℓ)O(\ell) work and O(log⁡ℓ)O(\log\ell) depth [9]. Semisort permutes ℓ\ell keyed items into contiguous groups of equal keys, with arbitrary order between groups. Assuming constant-time random hashing, we use a version with O(ℓ)O(\ell) expected work, O(ℓ)O(\ell) space, and deterministic O(log⁡2(ℓ+2))O(\log^2(\ell+ 2)) depth. A parallel dictionary stores key-value pairs and supports batched insertions, deletions, and lookups. Our dictionaries use linear space and process ℓ\ell operations in O(ℓ)O(\ell) expected amortized work, with deterministic O(log⁡n)O(\log n) depth for lookups and O(log⁡2n)O(\log^2 n) depth for updates. These depth bounds use the fact that dictionary and batch sizes are polynomial in nn. Appendix A.1 gives the implementations and proves their expected work and deterministic depth and space bounds.

Balanced Pressures and Core-Number Estimates

Assign each vertex vv a positive number p(v)p(v), called its pressure. Each edge divides one unit of load into two shares, one for each endpoint, according to the ratio of their pressures. Endpoints with equal pressures receive a share of 1/21/2 each. When the pressures differ, the endpoint with lower pressure receives the larger share. The load ℓ(v)\ell(v) of vertex vv is the sum of the shares it receives from its incident edges.

We call pressures balanced when every non-isolated vertex’s load is close to its pressure. We show that balanced pressures approximate core numbers, so the update algorithm in Section 4 can maintain accurate estimates by restoring balance after each batch. We first define balance precisely.

Definition 3.1 (Balanced pressures). Fix an exponent s>0s > 0 and a tolerance 0<σ<1/20 < \sigma< 1/2. Given pressures p(v)≥1/4p(v) \ge1/4 at all vertices, define the endpoint shares of each edge uvuv with p(u)≤p(v)p(u) \le p(v) by

xuv(v)=12(p(u)p(v))s,xuv(u)=1−xuv(v).(1)x_{uv}(v) = \frac{1}{2}\left(\frac{p(u)}{p(v)}\right)^s,\qquad x_{uv}(u) = 1 - x_{uv}(v). \tag*{(1)}

The load at vv is ℓ(v)=∑u∈N(v)xuv(v)\ell(v) = \sum_{u \in N(v)} x_{uv}(v). The pressures are balanced if every non-isolated vertex satisfies

(1−2σ)p(v)≤ℓ(v)≤(1+2σ)p(v),(2)(1 - 2\sigma)p(v) \le\ell(v) \le(1 + 2\sigma)p(v), \tag*{(2)}

and every isolated vertex has pressure 1/41/4.

The accuracy of balanced pressures for estimating the coreness values depends on ss and σ\sigma. The following theorem chooses these parameters to obtain a (2+ε)(2+\varepsilon)-approximation and bounds the work, depth, and space used by the data structure.

Theorem 3.2. Fix n≥2n \ge2 and a rational 0<ε≤10 < \varepsilon\le1 whose numerator and denominator are at most nO(1)n^{O(1)}. There is a parallel data structure for an initially edgeless graph on nn vertices that supports batches of edge insertions and deletions. After every batch, it maintains core-number estimates k^(v)\hat{k}(v) satisfying

k(v)2+ε≤k^(v)≤k(v)\frac{k(v)}{2+\varepsilon} \le\hat{k}(v) \le k(v)

for every vertex vv.

It maintains these estimates using balanced pressures (Definition 3.1) with σ=ε/16\sigma= \varepsilon/16 and s=⌈2ln⁡n/σ2⌉s = \lceil2 \ln n/\sigma^2 \rceil.

After initialization, processing any sequence containing TT edge updates takes O(Tε−5log⁡n)O(T\varepsilon^{-5}\log n) expected work. A batch uses O(ε−3log⁡2n)O(\varepsilon^{-3}\log^2 n) rounds and has depth O(ε−3log⁡4n)O(\varepsilon^{-3}\log^4 n). These bounds are deterministic. The space usage is O(m+n/ε+ε−3log⁡n)O(m + n/\varepsilon+ \varepsilon^{-3}\log n) words.

Section 3.1 establishes the share properties and chooses the exponent ss. Section 3.2 proves the core-number guarantee and derives the estimates. Section 4 gives an algorithm for maintaining balanced pressures and proves its work, depth, and space bounds.

Definitions

Throughout, let n≥2n \ge2 and σ=ε/16≤116\sigma= \varepsilon/16 \le\frac{1}{16}. We choose the share exponent ss at the end of this subsection.

Edge shares. The shares defined in (1) have three properties that we use throughout the analysis.

(S1) The two shares of an edge sum to 1, and the endpoint with the smaller or equal pressure receives at least 1/21/2.

(S2) A vertex’s share does not decrease when its neighbor’s pressure grows or its own pressure shrinks.

(S3) For any factor a≥1a \ge1, if only one endpoint multiplies or divides its pressure by aa, both shares change by a factor of at most asa^s. If both endpoints do so, both shares change by a factor of at most a2sa^{2s}.

(S1) and (S2) follow from the definition. For (S3), fix one endpoint’s pressure and multiply or divide the other’s by a factor a≥1a \ge1. If the pressures do not change order, (1) shows that the smaller share changes by a factor asa^{s}. The other share changes by the same absolute amount, but is at least as large before and after the change, so its multiplicative change is no greater.

If the change reverses the pressure order, apply the argument first until the pressures become equal, then from that point to the final pressure. The two pressure factors multiply to aa, so each share changes by a factor of at most asa^{s} over the whole change. Applying this bound once for each endpoint gives the factor a2sa^{2s}.

Loads and ratios. By (S1), the loads ℓ(v)\ell(v) sum to mm. For a vertex with at least one edge, we call r(v)=ℓ(v)/p(v)r(v)=\ell(v)/p(v) its ratio.

Choosing the exponent. The exponent ss controls how much less load an endpoint receives when its pressure is higher than its neighbor’s. This matters for vertices whose degree is much larger than their core number. For example, the center of an nn-vertex star has core number 1, so our accuracy bound requires its pressure to be at most 1+O(ε)1+O(\varepsilon). The balance constraint then requires its load to be O(1)O(1) as well. With n−1n-1 incident edges, its average share must therefore be O(1/n)O(1/n).

To see how ss affects this load, suppose the leaves have pressure 1 and the center has pressure 1+ε1+\varepsilon. The center’s load is

n−12(1+ε)s\frac{n-1}{2(1+\varepsilon)^s}

At these pressures, keeping the load O(1)O(1) requires (1+ε)s=Ω(n)(1+\varepsilon)^s=\Omega(n), or s=Ω(ε−1log⁡n)s=\Omega(\varepsilon^{-1}\log n). Our accuracy proof for general graphs uses the larger choice s=Θ(ε−2log⁡n)s=\Theta(\varepsilon^{-2}\log n) below. In particular, for the remainder of the description of our analysis and algorithm, we set

s=⌈2ln⁡nσ2⌉.s=\left\lceil\frac{2\ln n}{\sigma^2}\right\rceil.

Balanced Pressures Approximate Core Numbers

With the parameter choices above, balanced pressures approximate core numbers. The following theorem upper and lower bounds p(v)p(v) in terms of k(v)k(v).

Theorem 3.3. If the pressures are balanced, then every vertex vv with at least one edge satisfies

k(v)2(1+2σ)≤p(v)≤1+2σ1−2σk(v).\frac{k(v)}{2(1+2\sigma)}\le p(v)\le\frac{1+2\sigma}{1-2\sigma}k(v).

Proof. Fix a non-isolated vertex vv. For the lower bound, consider the k(v)k(v)-core, which contains vv by the definition of the core number. Choose a vertex uu with the smallest pressure in this core, so p(u)≤p(v)p(u)\le p(v). Each of the at least k(v)k(v) neighbors of uu in the core has pressure at least p(u)p(u), so (S1) gives ℓ(u)≥k(v)/2\ell(u)\ge k(v)/2. Balance then gives

k(v)/2≤ℓ(u)≤(1+2σ)p(u)≤(1+2σ)p(v),k(v)/2\le\ell(u)\le(1+2\sigma)p(u)\le(1+2\sigma)p(v),

and dividing by 1+2σ1+2\sigma gives the lower bound of the theorem.

For the upper bound, let SS consist of vv and all non-isolated vertices that appear before vv in the peeling order. By Lemma 2.1, every u∈Su\in S has k(u)≤k(v)k(u)\le k(v) and at most k(v)k(v) later neighbors. Charging each edge to its earlier endpoint shows that the loads in SS sum to at most k(v)∣S∣k(v)|S|, but this bounds only the average load, which still allows individual pressures to be large. We therefore multiply the load of each u∈Su\in S by p(u)σsp(u)^{\sigma s} before summing. Because the exponent σs\sigma s is large, this emphasizes the vertices with the highest pressures, so the resulting bound applies to p(v)p(v) itself rather than to the average. We first show that

(1−2σ)∑u∈Sp(u)σsp(u)≤∑u∈Sp(u)σsℓ(u)≤(1+σ2)k(v)∑u∈Sp(u)σs.\begin{aligned} (1-2\sigma)\sum_{u\in S}p(u)^{\sigma s}p(u) \le\sum_{u\in S}p(u)^{\sigma s}\ell(u) \\ &\le\left(1+\frac{\sigma}{2}\right)k(v)\sum_{u\in S}p(u)^{\sigma s}. \end{aligned}

The first inequality follows by applying balance, ℓ(u)≥(1−2σ)p(u)\ell(u)\ge(1-2\sigma)p(u), to each term.

For the second inequality, we expand each load ℓ(u)\ell(u) in the middle sum into the shares uu receives from its edges, and group the resulting terms by edge. Consider an edge within SS with endpoint pressures a≤ba\le b. Its two terms add up to

aσs(1−12(a/b)s)+12bσs(a/b)s=aσs(1+12(a/b)s((b/a)σs−1))≤(1+σ2)aσs.\begin{aligned} a^{\sigma s}\left(1-\frac{1}{2}(a/b)^s\right)+\frac{1}{2}b^{\sigma s}(a/b)^s \\ &=a^{\sigma s}\left(1+\frac{1}{2}(a/b)^s\left((b/a)^{\sigma s}-1\right)\right) \\ &\le\left(1+\frac{\sigma}{2}\right)a^{\sigma s}. \end{aligned}

The inequality holds because the concavity of xσx^\sigma gives (b/a)σs−1≤σ((b/a)s−1)(b/a)^{\sigma s}-1\le\sigma((b/a)^s-1), so the term added to 1 in the second line is at most σ2(1−(a/b)s)≤σ2\frac{\sigma}{2}(1-(a/b)^s)\le\frac{\sigma}{2}. Since σs≤bσs\sigma^s\le b^{\sigma s}, the edge’s terms are at most (1+σ/2)p(u)σs(1+\sigma/2)p(u)^{\sigma s} for either endpoint uu, and we charge them to the endpoint that appears earlier in the peeling order. An edge leaving SS has a single term, which is at most p(u)σsp(u)^{\sigma s} for its endpoint u∈Su\in S. That endpoint is the earlier one, because SS contains all non-isolated vertices preceding vv. Each u∈Su\in S is charged for at most k(v)k(v) edges, one for each later neighbor, which proves the second inequality.

To bound p(v)p(v), write

A=∑u∈Sp(u)σsp(u)=∑u∈Sp(u)σs+1A=\sum_{u\in S}p(u)^{\sigma s}p(u)=\sum_{u\in S}p(u)^{\sigma s+1}

for the sum on the left, so the chain above gives (1−2σ)A≤(1+σ/2)k(v)∑u∈Sp(u)σs(1-2\sigma)A\le(1+\sigma/2)k(v)\sum_{u\in S}p(u)^{\sigma s}. The largest pressures in SS dominate AA, in particular, p(v)≤A1/(σs+1)p(v)\le A^{1/(\sigma s+1)} because v∈Sv\in S. So it suffices to upper bound A1/(σs+1)A^{1/(\sigma s+1)}. The power mean inequality gives

∑u∈Sp(u)σs≤∣S∣1/(σs+1)Aσs/(σs+1).\sum_{u\in S}p(u)^{\sigma s}\le|S|^{1/(\sigma s+1)}A^{\sigma s/(\sigma s+1)}.

Substituting this bound for the sum of p(u)σsp(u)^{\sigma s} gives

(1−2σ)A≤(1+σ/2)k(v)∣S∣1/(σs+1)Aσs/(σs+1).(1-2\sigma)A\le(1+\sigma/2)k(v)|S|^{1/(\sigma s+1)}A^{\sigma s/(\sigma s+1)}.

Since A>0A>0, dividing by (1−2σ)Aσs/(σs+1)(1-2\sigma)A^{\sigma s/(\sigma s+1)} gives

A1/(σs+1)≤1+σ/21−2σk(v)∣S∣1/(σs+1).A^{1/(\sigma s+1)}\le\frac{1+\sigma/2}{1-2\sigma}k(v)|S|^{1/(\sigma s+1)}.

Using v∈Sv\in S and ∣S∣≤n|S|\le n, we obtain

p(v)≤A1/(σs+1)≤1+σ/21−2σk(v)n1/(σs+1)≤1+2σ1−2σk(v).\begin{aligned} p(v)\le A^{1/(\sigma s+1)} \\ &\le\frac{1+\sigma/2}{1-2\sigma}k(v)n^{1/(\sigma s+1)} \le\frac{1+2\sigma}{1-2\sigma}k(v). \end{aligned}

The last step uses s≥2ln⁡n/σ2s\ge2\ln n/\sigma^2, so n1/(σs+1)≤eσ/2n^{1/(\sigma s+1)}\le e^{\sigma/2}, and (1+σ/2)eσ/2≤eσ≤1+2σ(1+\sigma/2)e^{\sigma/2}\le e^\sigma\le1+2\sigma.

Core-number estimates. Given balanced pressures, we obtain the core-number estimate k^(v)\widehat{k}(v) for a non-isolated vertex vv by rounding

1−2σ1+2σp(v)(3)\frac{1-2\sigma}{1+2\sigma}p(v) \tag*{(3)}

downward, reducing it by at most a σ/64\sigma/64 fraction. For an isolated vertex, we set k^(v)=0\widehat{k}(v)=0. § 4.1 describes how to perform this rounding.

Theorem 3.3 and the downward rounding of the reported estimate give k^(v)≤k(v)\widehat{k}(v) \le k(v) and, for a non-isolated vertex,

k(v)k^(v)≤2(1+2σ)2(1−2σ)(1−σ/64)≤2+16σ=2+ε.\frac{k(v)}{\widehat{k}(v)} \le\frac{2(1+2\sigma)^2}{(1-2\sigma)(1-\sigma/64)} \le2+16\sigma=2+\varepsilon.

The last inequality holds for 0<σ≤1/160<\sigma\le1/16. Isolated vertices have k^(v)=0=k(v)\widehat{k}(v)=0=k(v).

Maintaining Balanced Pressures

We now show how to maintain balanced pressures after each batch, so that the core-number guarantee of § 3.2 continues to hold. Our algorithm restores balance through small pressure changes made in parallel rounds. To prove our main theorem (Theorem 3.2) and obtain a good parallel batch-dynamic algorithm with low depth and work we must bound the number of rounds per batch and the total work over a sequence of batches.

Overview. We first define approximate loads and bound their error in § 4.1. We use these error bounds to choose movement and stopping thresholds. The thresholds ensure that pressure changes have the correct direction and that stopping guarantees balance for the true loads. § 4.2 gives the batch algorithm, which uses these thresholds to decide which pressures to change and when to stop. The movement tests use a tighter tolerance than the stopping test. § 4.3 uses this gap and the small size of each pressure change to bound the number of rounds.

§ 4.4 describes the vertex data and the Relabel operation for maintaining approximate loads as pressures change. We aggregate neighbor contributions to bound each move’s work in terms of the moving vertex’s load. § 4.5 gives the parallel implementation and proves the work and depth bounds. § 4.6 then relates the repair work to the decrease of a nonnegative potential. The potential starts at zero, and each batch adds only O(1)O(1) per updated edge, which bounds how much it can decrease over all repair rounds. This gives the amortized work bound. § 4.7 combines these results to complete the proof of Theorem 3.2.

Approximate Loads

Changing a vertex’s pressure can change the load at every neighbor. To reduce the work of maintaining loads, we round edge shares near one up to one and sufficiently small shares down to zero. While a share remains in one of these rounding ranges, its contribution to the approximate load stays constant, so the algorithm need not update that contribution.

We first describe how integer pressure indices represent the pressures, and how raises and lowers change them. We then specify the truncation cutoffs and account for numerical rounding. The resulting error bound for the computed ratio of load to pressure will justify the balance tests in § 4.2. § 4.4 explains how to maintain the approximate loads efficiently.

Pressure indices. Our algorithm enforces that every pressure is exactly 1/41/4 times an integer power of a fixed step β>1\beta>1. We choose β\beta in § 4.2. This subsection only uses that 22 is an integer power of β\beta. Each vertex vv therefore has an integer pressure index j(v)≥0j(v)\ge0 with p(v)=βj(v)/4p(v)=\beta^{j(v)}/4. The pressure index is always an integer, and it is our data structure stores. The pressure itself is determined by the index.

Initially, every vertex has pressure index 00, so its pressure is 1/41/4. The algorithm changes a pressure only by changing its index. A raise increases j(v)j(v) by one, which multiplies the pressure by β\beta, and a lower decreases j(v)j(v) by one, which divides the pressure by β\beta. Either change is called a move. The batch algorithm of § 4.2 also changes pressures in two other ways, called jumps and resets, and both again produce an integer index (§ 4.4).

The shares of an edge uvuv depend only on the difference of the two pressure indices, because the ratio in Equation (1) is (p(u)/p(v))=βj(u)−j(v)(p(u)/p(v))=\beta^{j(u)-j(v)}.

Truncating the edge shares. We compute approximate loads by truncating the edge shares, setting shares near one to one and sufficiently small shares to zero. For an edge uvuv with index difference d=j(u)−j(v)d=j(u)-j(v), use the share of vv per edge in two cases: count it as 11 when βsd>2⌈log⁡(64/σ)⌉\beta^{sd}>2^{\lceil\log(64/\sigma)\rceil}, and as 00 when βsd<2−⌈log⁡(64/σ)⌉−⌈log⁡(4n)⌉\beta^{sd}<2^{-\lceil\log(64/\sigma)\rceil-\lceil\log(4n)\rceil}. Let ℓ~(v)\widetilde{\ell}(v) be the sum of these approximate shares. The two cutoffs serve different purposes. Rounding a share near one causes only a small relative error. Ignored shares must be smaller by another factor of nn, because a vertex can have nearly nn of them.

The next lemma shows that the approximate load can exceed the true load by only a small fraction of the true load, or fall below it by only a small additive amount independent of the vertex’s degree.

Lemma 4.1. Every vertex satisfies ℓ(v)−σ/512≤ℓ~(v)≤(1+σ/64)ℓ(v)\ell(v)-\sigma/512 \le\widetilde{\ell}(v)\le(1+\sigma/64)\ell(v).

Proof. A share rounded to one equals 1−12β−sd1-\frac{1}{2}\beta^{-sd}, so it increases by less than 122−⌈log⁡(64/σ)⌉≤σ/128\frac{1}{2}2^{-\lceil\log(64/\sigma)\rceil}\le\sigma/128, at most σ/64\sigma/64 times that share. An ignored share is smaller by another factor of 2⌈log⁡(4n)⌉≥4n2^{\lceil\log(4n)\rceil}\ge4n, so all ignored shares together sum to less than σ/512\sigma/512.

Rounding. To compute pressures and shares in finite precision, we store rounded values of the powers βj\beta^j with 1≤βj<21\le\beta^j<2 and scale them by powers of two as needed. The same table serves both quantities because p(v)=βj(v)/4p(v)=\beta^{j(v)}/4, and every share is determined by βs(j(u)−j(v))\beta^{s(j(u)-j(v))}, which is again a power of β\beta.

We choose the table’s precision so that each computed share differs from its value after truncation by at most a σ/64\sigma/64 fraction. The table approximates each pressure from below, with relative error at most $\sigma/64. We use this rounded value in the balance tests below. For a non-isolated vertex, multiplying it by (1−2σ)/(1+2σ)(1-2\sigma)/(1+2\sigma) gives the core-number estimate. All sums and balance tests use exact integer arithmetic, so they introduce no further rounding error (Appendix § 7.§ 2).

Approximate ratios. We define the approximate ratio used by the algorithm as

r~(v)=computed value of ℓ~(v)computed value of p(v).\widetilde{r}(v)=\frac{\text{computed value of }\widetilde{\ell}(v)}{\text{computed value of }p(v)}.

The following lemma bounds the error in this ratio, including both share truncation and numerical rounding.

Lemma 4.2 (Accuracy of the approximate ratios). At every non-isolated vertex vv, the approximate ratio satisfies

r^(v)≤(1+σ16)r(v),r^(v)≥(1−σ16)r(v)if r(v)≥12.(4)\widehat{r}(v) \le\left(1+\frac{\sigma}{16}\right)r(v), \qquad \widehat{r}(v) \ge\left(1-\frac{\sigma}{16}\right)r(v) \quad\text{if }r(v)\ge\frac{1}{2}. \tag*{(4)}

Proof. Combining truncation and rounding gives

r^≤(1+σ/64)21−σ/64r≤(1+σ/16)r.\widehat{r}\le\frac{(1+\sigma/64)^2}{1-\sigma/64}r\le(1+\sigma/16)r.

If r≥1/2r\ge1/2, then ℓ≥p/2≥1/8\ell\ge p/2\ge1/8, so the truncation error σ/512\sigma/512 is at most (σ/64)ℓ(\sigma/64)\ell. The computed pressure is at most pp, giving

r^≥(1−σ/64)2r≥(1−σ/16)r.\widehat{r}\ge(1-\sigma/64)^2r\ge(1-\sigma/16)r.

Processing a Batch

We now describe how to process a batch of edge insertions and deletions. Before inserting edges, the algorithm performs “jumps” to quickly raise pressures where needed to avoid a long sequence of minute increases at vertices receiving many new edges. Once the edge updates are complete, it restores balance through pressure changes in parallel rounds. We first bound the effect of a single pressure move and define the balance tests in the algorithm, then give the full batch algorithm.

Step size. We set the step size of § 4.1 to

β=21/(s⌈8/σ⌉).\beta=2^{1/\left(s\lceil8/\sigma\rceil\right)}.

By (S3), simultaneous moves by the two endpoints change each share by a factor of at most β2s\beta^{2s}. With our choice, βs=21/⌈8/σ⌉≤2σ/8\beta^s=2^{1/\lceil8/\sigma\rceil}\le2^{\sigma/8}, so this factor is at most 2σ/42^{\sigma/4}.

We prove in Lemma 4.6 that, with these choices, a vertex that raises its pressure still has load above pressure after the round, and one that lowers its pressure still has load below pressure. The round and work analyses use the following bounds:

βs+1≤eσ/8,β2s+1≤eσ/4,\beta^{s+1}\le e^{\sigma/8}, \qquad \beta^{2s+1}\le e^{\sigma/4},
1ln⁡β=O(ε−3log⁡n).(5)\frac{1}{\ln\beta}=O(\varepsilon^{-3}\log n). \tag*{(5)}

The first bound holds because s≥3s\ge3 and ln⁡2<3/4\ln2<3/4 give ln⁡βs+1=(1+1/s)ln⁡2/⌈8/σ⌉≤3/4⋅3/4⋅σ/8\ln\beta^{s+1}=(1+1/s)\ln2/\lceil8/\sigma\rceil\le3/4\cdot3/4\cdot\sigma/8. The second follows from 2s+1≤2(s+1)2s+1\le2(s+1). For the third, 1/ln⁡β=s⌈8/σ⌉/ln⁡21/\ln\beta=s\lceil8/\sigma\rceil/\ln2, and σ=ε/16\sigma=\varepsilon/16 gives s=O(ε−2log⁡n)s=O(\varepsilon^{-2}\log n) and ⌈8/σ⌉=O(ε−1)\lceil8/\sigma\rceil=O(\varepsilon^{-1}).

Balance tests. Each round uses the approximate ratio r^(v)\widehat{r}(v) of every non-isolated vertex vv to answer two questions. The first is whether another round is needed, and the second is which vertices move in it.

We call a non-isolated vertex vv unbalanced if r^(v)>1+32σ\widehat{r}(v)>1+\frac{3}{2}\sigma or r^(v)<1−32σ\widehat{r}(v)<1-\frac{3}{2}\sigma. The algorithm performs another round whenever some vertex is unbalanced, and stops when no vertex is. We choose the tolerance 32σ\frac{3}{2}\sigma because the error in r^(v)\widehat{r}(v) is less than 12σ\frac{1}{2}\sigma at such a vertex, so every vertex that is not unbalanced has true ratio within 1±2σ1\pm2\sigma, as the balance inequality of Definition 3.1 requires.

Within a round, more vertices may move than the unbalanced ones. A vertex that is not unbalanced may still need to move, because the moves of its neighbors change its load. If only unbalanced vertices moved, a vertex that is only barely not unbalanced could become unbalanced through its neighbors’ moves, and repairing it could unbalance its neighbors in turn. Vertices could then keep

unbalancing each other back and forth, and we could not bound the number of rounds. We therefore also move vertices that are close to being unbalanced.

Precisely, every non-isolated vertex with r^(v)>1+σ\widehat{r}(v)>1+\sigma raises its pressure, and every non-isolated vertex with r^(v)<1−σ\widehat{r}(v)<1-\sigma lowers it. § 4.3 proves two properties that explain these choices. First, a vertex that does not move in a round cannot become unbalanced (Lemma 4.4), so a vertex that is unbalanced after a round must have moved in that round. This is why we also move vertices that are not unbalanced, and it leads to the bound on the number of rounds. Second, although the tests use the approximate ratio r^(v)\widehat{r}(v), they translate into bounds on the true ratio r(v)r(v) (Lemma 4.5). A vertex raises its pressure only when its true load exceeds its pressure, and lowers it only when its true load is below its pressure. A vertex that is not unbalanced has true ratio within 1±2σ1\pm2\sigma.

The algorithm. A batch consists of a set DD of edges of the graph, which are deleted, and a set II of edges not in the graph, which are inserted. For a vertex vv, let deg⁡I(v)\deg_I(v) be the number of edges of II at vv. Lines 2–4 of Algorithm 1 raise pressures where needed to prepare for the insertions. We call these pressure increases jumps and explain their purpose below. The algorithm then restores balance in parallel rounds.

We apply the jumps with one call to Relabel and use one call per repair round to apply all its pressure moves. This operation updates the approximate loads along with the pressures. § 4.4 describes the vertex data and the Relabel operation.

Algorithm 1 Process a batch of edge updates
Input: Edges DD to delete and II to insert.
1: Delete the edges of DD.
2: for all vertices vv with deg⁡I(v)>0\deg_I(v)>0 in parallel do
3: p(v)←max⁡{p(v),2⌈log⁡deg⁡I(v)⌉/2}p(v)\leftarrow\max\{p(v),2^{\lceil\log\deg_I(v)\rceil/2}\}
4: end for
5: Insert the edges of II.
6: Set p(v)←1/4p(v)\leftarrow1/4 for every isolated vertex.
7: while some vertex is unbalanced do
8: O←{v:deg⁡(v)>0,r^(v)>1+σ}O\leftarrow\{v:\deg(v)>0,\widehat{r}(v)>1+\sigma\} — Vertices to raise
9: U←{v:deg⁡(v)>0,r^(v)<1−σ}U\leftarrow\{v:\deg(v)>0,\widehat{r}(v)<1-\sigma\} — Vertices to lower
10: for all $v\in O\cup U in parallel do
11: if v∈Ov\in O then
12: p(v)←βp(v)p(v)\leftarrow\beta p(v) — Raise
13: else
14: p(v)←p(v)/βp(v)\leftarrow p(v)/\beta — Lower
15: end if
16: end for
17: Update ℓ^\widehat{\ell} and r^\widehat{r} at all affected vertices — Relabel
18: end while

Table 1 (PDF p. 7).

Each iteration of the loop at line 7 is a round. Lines 8–9 fix the sets OO and UU before any pressure change, so all vertices use the ratios at the start of the round. Line 17 then updates the approximate loads and ratios of the vertices that moved and of their neighbors, using the Relabel operation of § 4.4. Edge updates and jumps also update the approximate loads of the affected vertices. When the repair ends, no vertex is unbalanced. Together with the reset of isolated vertices on line 6, Lemma 4.5(2) in § 4.3 guarantees balanced pressures, so Theorem 3.3 applies. Some vertices may still have rˉ(v)\bar r(v) outside 1±σ1 \pm\sigma when repair stops, but the stopping condition ensures that their loads are close enough to their pressures for the approximation guarantee to hold.

Jumps. A jump on line 3 sets p(v)p(v) to the larger of its current value and 2⌊log⁡deg⁡I(v)⌋/22^{\lfloor\log\deg_I(v)\rfloor}/2; this target lies between deg⁡I(v)/4\deg_I(v)/4 and deg⁡I(v)/2\deg_I(v)/2. Jumps are not needed to bound the number of rounds, which § 4.3 bounds without using them. They keep the total work low. Without jumps, a vertex that receives many new edges would raise its pressure one step at a time over many rounds, and each of these rounds would be expensive. For example, suppose we insert an nn-vertex clique into an empty graph. Without jumps, its vertices would raise their pressures from 1/41/4 to a constant fraction of the clique size, one round at a time. Every round would scan all edges of the clique (§ 4.4), adding a logarithmic factor to the work bound of Theorem 3.2 for fixed ε\varepsilon. A jump raises vv’s pressure to a constant fraction of deg⁡I(v)\deg_I(v) in a single operation.

Deletions need no corresponding step. A vertex that loses many edges lowers its pressure in the following rounds, and § 4.6 shows that these lowers are cheap enough.

The following lemma bounds the pressures and the effect of jumps.

Lemma 4.3. (1) Throughout the algorithm, every pressure lies in [1/4,2n][1/4,2n].

(2) For a batch with insertion set II, let p(v)p(v) be the pressure immediately before the jumps and pˉ(v)\bar p(v) the pressure immediately after them. The jumps increase the sum of pressures by at most ∣I∣|I| and ensure deg⁡I(v)<4pˉ(v)\deg_I(v)<4\bar p(v) for every vertex vv. Every vertex that jumps has p(v)<deg⁡I(v)/2p(v)<\deg_I(v)/2.

Proof. (1) All pressures start at 1/41/4. Suppose they are all at least 1/41/4 before a round. A vertex that could fall below 1/41/4 in a lower has p(v)<β/4p(v)<\beta/4. Every neighbor then has pressure at least p(v)/βp(v)/\beta, so each incident edge gives vv a share of at least β−s/2\beta^{-s}/2. Since βs+1<2\beta^{s+1}<2 by (4), this share exceeds β/4>p(v)\beta/4>p(v). Thus a non-isolated vertex at such a pressure has load above pressure, so it does not lower. Jumps and resets also preserve the lower bound.

For the upper bound, a vertex raises its pressure only when its load exceeds its pressure. The load is at most the vertex’s degree, which is less than nn, so the pressure is below nn before the raise. The raise multiplies it by β≤2\beta\le2, so the new pressure is below 2n2n. After a jump, the pressure is at most deg⁡I(v)/2<n\deg_I(v)/2<n, so the pressure remains below 2n2n.

(2) For a vertex with deg⁡I(v)>0\deg_I(v)>0, the jump target satisfies

deg⁡I(v)4<2⌊log⁡deg⁡I(v)⌋2≤deg⁡I(v)2.\frac{\deg_I(v)}{4}<\frac{2^{\lfloor\log\deg_I(v)\rfloor}}{2}\le\frac{\deg_I(v)}{2}.

Hence pˉ(v)>deg⁡I(v)/4\bar p(v)>\deg_I(v)/4, and a vertex that jumps had p(v)<deg⁡I(v)/2p(v)<\deg_I(v)/2. The lower bound on pˉ(v)\bar p(v) also holds when deg⁡I(v)=0\deg_I(v)=0, since pressures are positive. Each vertex’s pressure increases by at most deg⁡I(v)/2\deg_I(v)/2. Summing this bound counts each inserted edge once, giving a total increase of at most ∣I∣|I|. □\square

Next, we use the bounded range of pressure values to show that each batch requires at most O(ε−3log⁡2n)O(\varepsilon^{-3}\log^2 n) repair rounds. Sections 4.4–4.5 describe the data structure and bound the cost of these rounds, before § 4.6 bounds their total work over a sequence of batches.

Bounding the Number of Rounds

We first prove the two properties of the balance tests that § 4.2 announced. We then analyze how one round of Algorithm 1 changes the true ratio of a vertex that moves, and combine these results to bound the number of rounds. Lemma 4.4 proves that a vertex that does not move in a round cannot become unbalanced.

Lemma 4.4. A non-isolated vertex that does not move in a round has true ratio within 1±43σ1\pm\frac{4}{3}\sigma after the round, and is not unbalanced.

Proof. Let vv be such a vertex, and let rr and r′r' be its true ratios before and after the round. Since vv does not move, 1−σ≤rˉ≤1+σ1-\sigma\le\bar r\le1+\sigma. Since rˉ≥1−σ\bar r\ge1-\sigma, (3) first gives r>1/2r>1/2. Applying both error bounds then gives

1−σ1+σ/16≤r≤1+σ1−σ/16.\frac{1-\sigma}{1+\sigma/16}\le r\le\frac{1+\sigma}{1-\sigma/16}.

and hence ∣r−1∣≤9σ/8|r-1|\le9\sigma/8. Only the neighbors’ pressures change, each by a factor of at most β\beta, so (S3) bounds the change in each share of vv, and hence in its load, by a factor of βs≤eσ/8\beta^s\le e^{\sigma/8}, using (4). The pressure of vv stays fixed, so its ratio changes by at most the same factor. Therefore,

(1−9σ/8)e−σ/8≤r′≤(1+9σ/8)eσ/8.(1-9\sigma/8)e^{-\sigma/8}\le r'\le(1+9\sigma/8)e^{\sigma/8}.

These bounds give ∣r′−1∣<4σ/3|r'-1|<4\sigma/3. They follow from e−x≥1−xe^{-x}\ge1-x and ex≤1/(1−x)e^x\le1/(1-x) for 0≤x<10\le x<1, using 0<σ≤1/160<\sigma\le1/16. For example,

1+9σ/81−σ/8<1+4σ/3⟺σ(1−2σ)>0.\frac{1+9\sigma/8}{1-\sigma/8}<1+4\sigma/3 \qquad\Longleftrightarrow\qquad \sigma(1-2\sigma)>0.

Since r′∈[1/2,2]r'\in[1/2,2], Lemma 4.2 gives ∣rˉ′−r′∣≤σ/8|\bar r'-r'|\le\sigma/8 for the approximate ratio rˉ′\bar r' after the round. Hence ∣rˉ′−1∣<(4/3+1/8)σ<3σ/2|\bar r'-1|<(4/3+1/8)\sigma<3\sigma/2, so vv is not unbalanced after the round. □\square

By the contrapositive of Lemma 4.4, a vertex that is unbalanced after a round must have moved in that round. Lemma 4.7 below strengthens this statement to show that the vertex moved in the same direction in every round so far, which bounds the number of rounds.

The tests use the approximate ratio rˉ(v)\bar r(v), but the rest of the analysis needs statements about the true ratio r(v)r(v). Lemma 4.5 translates each test into a bound on the true ratio.

Lemma 4.5. Let vv be a non-isolated vertex.

(1) If rˉ(v)>1+σ\bar r(v)>1+\sigma, then r(v)>1+78σr(v)>1+\frac{7}{8}\sigma. If rˉ(v)<1−σ\bar r(v)<1-\sigma, then r(v)<1−78σr(v)<1-\frac{7}{8}\sigma.

(2) The following implications hold.

∣r(v)−1∣≤43σ⟹v|r(v)-1|\le\frac{4}{3}\sigma\quad\Longrightarrow\quad v is not unbalanced,

vv is not unbalanced ⟹∣r(v)−1∣≤2σ\quad\Longrightarrow\quad|r(v)-1|\le2\sigma.

Proof. We use the error bound (3) of Lemma 4.2. Whenever 1/2≤r≤21/2\le r\le2, it gives ∣rˉ−r∣≤σr/16≤σ/8|\bar r-r|\le\sigma r/16\le\sigma/8.

(1) Suppose rˉ>1+σ\bar r>1+\sigma. The upper bound in (3) gives r>rˉ/(1+σ/16)>1r>\bar r/(1+\sigma/16)>1. If r≤2r\le2, then r≥rˉ−σ/8>1+78σr\ge\bar r-\sigma/8>1+\frac{7}{8}\sigma, and if r>2r>2 the claim is immediate. Now suppose rˉ<1−σ\bar r<1-\sigma. If r<1/2r<1/2, the claim is immediate, because 12<1−78σ\frac{1}{2}<1-\frac{7}{8}\sigma. Otherwise the lower bound in (3) gives r≤rˉ/(1−σ/16)<1r\le\bar r/(1-\sigma/16)<1, so r≤rˉ+σ/8<1−78σr\le\bar r+\sigma/8<1-\frac{7}{8}\sigma. (2) For the first implication, ∣r−1∣≤4σ/3|r-1| \le4\sigma/3 implies r∈[1/2,2]r \in[1/2,2], so

∣r^−1∣≤∣r−1∣+∣r^−r∣≤(4/3+1/8)σ<3σ/2,|\widehat{r}-1| \le|r-1|+|\widehat{r}-r| \le(4/3+1/8)\sigma< 3\sigma/2,

and the vertex is not unbalanced. For the second implication, a vertex that is not unbalanced satisfies ∣r^−1∣≤3σ/2|\widehat{r}-1| \le3\sigma/2. Equation (3) then rules out r<1/2r<1/2 and r>2r>2, so the same error bound applies:

∣r−1∣≤∣r^−1∣+∣r^−r∣≤(3/2+1/8)σ<2σ.|r-1| \le|\widehat{r}-1|+|\widehat{r}-r| \le(3/2+1/8)\sigma< 2\sigma.

Part (1) shows that a vertex that raises its pressure has ℓ(v)>p(v)\ell(v)>p(v) and a vertex that lowers its pressure has ℓ(v)<p(v)\ell(v)<p(v), so every move brings the pressure toward the true load. The second implication of (5) shows that, when no vertex is unbalanced, every non-isolated vertex satisfies the balance inequality of Definition 3.1.

We next consider a vertex that moves in a round. We show that a move brings its true ratio r=ℓ/pr=\ell/p closer to 1 without crossing 1. A raise therefore leaves load above pressure, and a lower leaves load below pressure, even when neighboring vertices move in the same round.

Lemma 4.6 (One round). Let pp, ℓ\ell, rr denote a vertex’s pressure, load, and ratio before a round, and let p′p', ℓ′\ell', r′r' denote their values after the round. A vertex that raises its pressure satisfies 1+σ/2<r′≤r/β1+\sigma/2<r'\le r/\beta. A vertex that lowers its pressure satisfies βr≤r′<1−σ/2\beta r\le r'<1-\sigma/2.

Proof. When a vertex raises its pressure by a factor of β\beta, each neighbor’s pressure can increase by at most the same factor. The vertex’s shares therefore cannot increase. Thus ℓ′≤ℓ\ell'\le\ell and r′=ℓ′/(βp)≤r/βr'=\ell'/(\beta p)\le r/\beta. Similarly, when a vertex lowers its pressure, its shares cannot decrease, so ℓ′≥ℓ\ell'\ge\ell and r′=βℓ′/p≥βrr'=\beta\ell'/p\ge\beta r.

We next show that a raise leaves load above pressure and a lower leaves load below pressure. A raise requires r^>1+σ\widehat{r}>1+\sigma and a lower requires r^<1−σ\widehat{r}<1-\sigma, using the approximate ratio before the round. Lemma 4.5(1) therefore gives r>1+7σ/8r>1+7\sigma/8 before a raise and r<1−7σ/8r<1-7\sigma/8 before a lower. By (S3), the load changes by a factor of at most β2s\beta^{2s}. The pressure changes by a factor of β\beta, so the ratio changes by a factor of at most β2s+1≤eσ/4\beta^{2s+1}\le e^{\sigma/4}, using (4). Consequently,

r′>e−σ/4(1+7σ/8)≥1+σ/2for a raise,r'>e^{-\sigma/4}(1+7\sigma/8)\ge1+\sigma/2\quad\text{for a raise,}
r′<eσ/4(1−7σ/8)≤1−σ/2for a lower.r'<e^{\sigma/4}(1-7\sigma/8)\le1-\sigma/2\quad\text{for a lower.}

The last inequality in each line follows from e−x≥1−xe^{-x}\ge1-x and ex≤1/(1−x)e^x\le1/(1-x) for 0≤x<10\le x<1, using 0<σ≤1/160<\sigma\le1/16.

We next show that a vertex still unbalanced must have raised its pressure in every round or lowered it in every round. Since each move changes its pressure by a factor of β\beta, the pressure range [1/4,2n][1/4,2n] limits how many such rounds are possible.

Lemma 4.7 (Number of rounds). The repair takes O(ε−3log⁡2n)O(\varepsilon^{-3}\log^2 n) rounds per batch.

Proof. Suppose a non-isolated vertex has r>1+4σ/3r>1+4\sigma/3 after tt rounds. Lemma 4.6 rules out lowering its pressure in the last round, and Lemma 4.4 rules out leaving it unchanged. The vertex must therefore have raised its pressure. Since a raise satisfies r′≤r/βr'\le r/\beta, its ratio before that round was even larger. Repeating this argument backward shows that the vertex raised its pressure in all tt rounds.

The same reasoning shows that a vertex with r<1−4σ/3r<1-4\sigma/3 after tt rounds must have lowered its pressure in every round. A raise would violate Lemma 4.6, an unchanged pressure would violate Lemma 4.4, and a lower satisfies r′≥βrr'\ge\beta r, so the ratio before that round was even smaller.

By Lemma 4.3(1), every pressure stays between 1/41/4 and 2n2n. Thus a vertex can raise its pressure in the same direction for at most log⁡β(8n)=ln⁡(8n)/ln⁡β\log_\beta(8n)=\ln(8n)/\ln\beta consecutive rounds. After more than this many rounds, every non-isolated vertex must satisfy ∣r−1∣≤4σ/3|r-1|\le4\sigma/3. Equation (5) then guarantees that no vertex is unbalanced, so the repair must stop. Substituting 1/ln⁡β=O(ε−3log⁡n)1/\ln\beta=O(\varepsilon^{-3}\log n) from Equation (4) gives O(ε−3log⁡2n)O(\varepsilon^{-3}\log^2 n) rounds. This bound is deterministic and independent of the batch size.

Vertex Storage and Updates

We now describe the information stored at each vertex to maintain approximate loads as pressures change. Our goal is to bound the work of a move in terms of the moving vertex’s load, even when its degree is much larger. We group neighbors by index, handling larger contributions to the load individually and combining smaller contributions in counters.

We first express shares and the truncation cutoffs of Section 4.1 in terms of index differences. Next, we define the neighbor groups and the lists, buckets, and counters stored at each vertex. We then explain which neighbors a pressure move visits and how to update the counters when the vertex’s index changes. We finish by combining these updates into Relabel, the operation used for repair rounds and jumps.

Pressure indices. Recall from Section 4.1 that each vertex stores its pressure index j(v)≥0j(v)\ge0, with p(v)=βj(v)p(v)=\beta^{j(v)}. Let

K=⌈8σ⌉,M=sK,K=\left\lceil\frac{8}{\sigma}\right\rceil,\qquad M=sK,

so that β=21/M\beta=2^{1/M} and βs=21/K\beta^s=2^{1/K}. A raise or lower changes the index by one. A reset returns it to zero. A jump also sets it to an integer, because the jump target is

2⌊log⁡deg⁡I(v)⌋2=βM(1+⌊log⁡deg⁡I(v)⌋)4.\frac{2^{\lfloor\log\deg_I(v)\rfloor}}{2} = \frac{\beta^{M(1+\lfloor\log\deg_I(v)\rfloor)}}{4}.

Lemma 4.3(1) gives 0≤j(v)≤log⁡β(8n)=Mlog⁡(8n)0\le j(v)\le\log_\beta(8n)=M\log(8n).

Shares from indices. Expressed in terms of the index difference d=j(u)−j(v)d=j(u)-j(v), the share of edge uvuv received by vv is

xuv(v)=f(d)={122d/K,d≤0,1−122−d/K,d≥0.(6)x_{uv}(v)=f(d)= \begin{cases} \frac{1}{2}2^{d/K}, & d\le0,\\ 1-\frac{1}{2}2^{-d/K}, & d\ge0. \end{cases} \tag*{(6)}

This is Equation (1) with βs=21/K\beta^s=2^{1/K}. Every KK additional steps of difference between the indices halves the edge share of the endpoint with higher pressure (Figure 1). Since βsd=2d/K\beta^{sd}=2^{d/K}, the truncation rule of Section 4.1 counts a share as 1 exactly when d>Bd>B and as 0 exactly when d<−B−K⌊log⁡(4n)⌋d<-B-K\lfloor\log(4n)\rfloor, where

B=K⌈log⁡64σ⌉.B=K\left\lceil\log\frac{64}{\sigma}\right\rceil.

Rounded powers. In terms of indices, the table of rounded powers from Section 4.1 holds 2j/M2^{j/M} for 0≤j≤M0\le j\le M. It serves both pressures and shares because p(v)=2j(v)/M/4p(v)=2^{j(v)/M}/4 and 2d/K=2sd/M2^{d/K}=2^{sd/M}, using M=sKM=sK.

Share function $f(d)$

Figure 1. The share f(d)f(d) of vv in an edge uvuv, as a function of the index difference d=j(u)−j(v)d=j(u)-j(v).

Vertex data. Fix a vertex vv of index jj. Its high neighbors have index at least j−Bj-B; the others are low. For each high neighbor uu, vertex vv receives a share of at least f(−B)>σ/256f(-B)>\sigma/256 from edge uvuv, so vv has only O(ℓ(v)/σ)O(\ell(v)/\sigma) high neighbors. The next K⌈log⁡(4n)⌉K\lceil\log(4n)\rceil index levels below j−Bj-B form the window of low neighbors whose contributions are retained.

The vertex stores its index and degree, together with

  • a list of its high neighbors and the sum of their approximate shares;

  • its low neighbors in buckets, one per occupied index, with bucket sizes;

  • KK integer counters for the window, described below, and their total contribution to the approximate load.

The two stored sums give ℓ^(v)\widehat{\ell}(v), so we can check in constant time whether vv is unbalanced and whether it raises or lowers its pressure. Each edge has one record at each endpoint; the records point to each other and to their containing list or bucket. Figure 2 shows the storage at vv and the neighbors it visits when moving one index step.

Storage at $v$ and its neighbors

Figure 2. Storage at vv, where j(v)=jj(v)=j. Low neighbors outside the window remain in buckets and contribute zero to ℓ^(v)\widehat{\ell}(v). The thick outline marks the high list and first low bucket, scanned by vv on a one-step move.

Neighbors to visit. When vv changes its index by one, it visits its high list and the bucket just below it, at index j−B−1j-B-1. Every other neighbor that does not move stays more than BB steps below vv, so vv’s approximate contribution at that neighbor remains one before and after the move. Its record there remains in the high list and needs no change.

no change. At vv, these stationary neighbors remain in their buckets, and the window counters update their aggregate contribution. If a neighbor uu skipped by vv also moves, it collects uvuv through its own high list, since vv has a higher old index. The RELABEL operation below rebuilds the collected edge’s records using both endpoints’ new indices. Notice also that whenever vv lies in a neighbor’s low bucket, that neighbor is high at vv and is therefore visited. Thus every bucket record that needs a new index is reached.

The window counters. We use the KK counters to aggregate the shares received by vv from neighbors in its window. Increasing a neighbor’s index by KK within the window doubles its contribution to vv’s load, so we group levels spaced KK apart into the same counter. We number the window levels from zero at the bottom and assign a neighbor uu at offset aK+caK+c, where 0≤c<K0\leq c<K, to counter cc. The share received by vv from edge uvuv is

2−B/K−⌈log⁡(4n)⌉−122c/K.2^{-B/K-\lceil\log(4n)\rceil-1}2^{2c/K}.

The first factor is a power of two common to the whole window, and 22c/K2^{2c/K} is common to all levels assigned to counter cc. Thus counter cc stores the sum of the integer weights 2a2^a for the neighbors at those levels. To recover the window’s contribution, multiply each counter by the table value for 2c/K2^{c/K}, sum, and apply the common factor. Thus the counters preserve the contributions exactly until this final table lookup, with no accumulation of rounding error.

A raise shifts the window up one index. Remove the old bottom bucket, whose members each contribute one to counter 0. Every remaining offset decreases by one: move counter cc to position c−1c-1 for c>0c>0, and move counter 0 to position K−1K-1 and halve it. The halving is exact, because after removing offset zero all remaining contributions to counter 0 are even. A lower reverses the rotation, doubles the counter that wraps around, and adds the new bottom bucket to counter 0. Changes at the top of the window are handled by visiting the high list and the bucket just below it. Recomputing the window sum takes O(K)O(K) work after either shift. For a jump, rebuild the counters from the bucket sizes in the new window, in O(Klog⁡n)O(K\log n) work.

Relabel. RELABEL takes a set of changing vertices and their new indices and applies all these changes together. We call it once for all pressure moves in a repair round or for all initial jumps. It combines the neighbor visits and counter updates to maintain the stored neighbor information and approximate loads. An edge may have two changing endpoints, so we remove its old records before changing indices and rebuild them using the new indices.

Either every change is by one step, as in a repair round, or all changes are upward jumps. The following steps run in order, with the work within each step done in parallel:

(i) Each changing vertex scans its high list and the bucket just below, collecting these edges. Remove duplicates.

(ii) Remove each collected edge’s two records and subtract their contributions from the stored sums and counters.

(iii) Change the indices. Shift each changing vertex’s counters by one step, or rebuild them for a jump, using the bucket sizes after (ii). Recompute its window contribution.

(iv) Reinsert the collected edges using the new indices, adding their contributions to the appropriate lists, buckets, counters and sums. (v) Retest every vertex whose index or sums changed.

The next lemma shows that the counters account for changes on uncollected edges, so the stored approximate loads remain correct.

Lemma 4.8. After Relabel, the stored data again represent the current indices and approximate loads.

Proof. Collected edges are rebuilt explicitly. An uncollected edge cannot have two changing endpoints: the endpoint with the smaller old index would collect it. If just one endpoint vv changes, the other endpoint starts at least B+2B+2 steps below vv’s old index. Since vv lowers by at most one, it remains more than BB steps above that neighbor. The record for vv stays in that neighbor’s high list and contributes one. At vv, the neighbor stays in the same low bucket; the counter shift or rebuild accounts for its new position in the window. Edges with no changing endpoint need no action. □

Parallel Implementation

We now give a parallel implementation and bound the work and depth of edge updates, repair rounds, and jumps. We locate stored records with dictionaries and combine changes to each sum or counter before updating it.

Storage. We store high lists and low buckets in the dictionaries of Section 2. Geometric resizing keeps the work of listing a dictionary proportional to its number of records and adds O(1)O(1) expected amortized work per insertion or deletion. A global table keyed by (vertex, index) locates buckets and their sizes. Another keyed by edge locates the two endpoint records. Keep the vertices with rˉ(v)\bar r(v) outside 1±σ1 \pm\sigma in a table, and the number of unbalanced vertices in a counter.

Edge updates. Insertion adds an edge’s two records to their lists or buckets; deletion removes them. Each record changes one stored sum and possibly one window counter. Group changes to each sum or counter with a semisort and combine them with prefix sums, then update degrees and retest the endpoints. A semisort of the inserted endpoints also gives deg⁡I(v)\deg_I(v). After the insertions, reset isolated endpoints of deleted edges to index zero; they have no records and their counters are zero.

Relabel. Perform the scans in (i) in parallel and use a semisort to remove duplicates. Steps (ii) and (iv) are batches of hash-table operations; group and combine changes to sums and counters as for edge updates. In (iii), we shift the counters in parallel. For a jump, we rebuild the KK counters in parallel by querying each counter’s O(log⁡n)O(\log n) window buckets sequentially. This schedule uses O(K)O(K) scratch space per changing vertex. Remove empty buckets after (iv). Step (v) updates the table of vertices with rˉ(v)\bar r(v) outside 1±σ1 \pm\sigma and reduces the changes to the counter of unbalanced vertices. A round uses all vertices in the table and starts only when that counter is positive.

Lemma 4.9 (Cost). The expected amortized work of Relabel is bounded by charging O((1+ℓ(v))/σ)O((1+\ell(v))/\sigma) to each vertex that moves one step, or O((log⁡n+ℓ(v))/σ)O((\log n+\ell(v))/\sigma) to each vertex that jumps. Loads are measured before the operation. Edge updates cost O(1)O(1) expected amortized work each. Each round takes deterministic O(log⁡2n)O(\log^2 n) depth, as do the edge updates and jumps of a batch.

Proof. Every scanned neighbor contributes at least f(−B−1)≥f(−B)/2>σ/512f(-B-1) \ge f(-B)/2 > \sigma/512, so a changing vertex scans O(ℓ(v)/σ)O(\ell(v)/\sigma) edges. Charge each collected edge to a vertex that collected it. Its records and all resulting tests cost O(1)O(1) expected amortized work. Updating counters costs O(K)=O(1/σ)O(K)=O(1/\sigma) per move, or O(log⁡n)O(\log n) per jump. These charges cover all work, including changes at stationary endpoints.

We group updates and modify records using a constant number of semisorts, batched dictionary operations, prefix sums and reductions. Each has an input of polynomial size in nn and hence deterministic O(log⁡2n)O(\log^2 n) depth. Rebuilding a counter after a jump requires O(log⁡n)O(\log n) sequential lookups, each with expected constant work and deterministic O(log⁡n)O(\log n) depth. Since the KK counters are rebuilt in parallel, the jump also takes O(log⁡2n)O(\log^2 n) depth. □

Amortized Work

We now bound the total repair work over a sequence of batches. We relate the work of each repair round to its decrease in a nonnegative potential that we define shortly. The potential starts at zero. We show that the deletions, jumps, insertions, and resets before repair together increase it by only O(1)O(1) per updated edge. This limits the total potential decrease over all repair rounds, which we use to bound their total work. We defer the proof of the batch increase bound to Appendix A.3.

Lemma 4.9 shows that a move of vertex vv costs O((1+ℓ(v))/σ)O((1+\ell(v))/\sigma) expected amortized work. Since p(v)≥1/4p(v) \ge1/4, this cost is O((p(v)+ℓ(v))/σ)O((p(v)+\ell(v))/\sigma). We therefore bound the sum of p(v)+ℓ(v)p(v)+\ell(v) over all moves, using the values before each round.

The potential. For the analysis, allow pressures to be any real numbers at least 1/41/4. Each move adds or subtracts ln⁡β\ln\beta from ln⁡p(v)\ln p(v). We construct a function whose derivative with respect to ln⁡p(v)\ln p(v) is p(v)−ℓ(v)p(v)-\ell(v). A raise increases the logarithmic pressure when this derivative is negative, and a lower decreases it when the derivative is positive. Define

FG(p)=∑vp(v)+∑uv∈E(G)ϕ(p(u),p(v)),F_G(p)=\sum_v p(v)+\sum_{uv\in E(G)}\phi(p(u),p(v)),
ϕ(a,b)=−ln⁡min⁡(a,b)+12(min⁡(a,b)max⁡(a,b))s.\phi(a,b)=-\ln\min(a,b)+\frac{1}{2}\left(\frac{\min(a,b)}{\max(a,b)}\right)^s.

This function has the desired derivative,

∂FG∂ln⁡p(v)=p(v)−ℓ(v).(7)\frac{\partial F_G}{\partial\ln p(v)}=p(v)-\ell(v). \tag*{(7)}

Indeed, for a≤ba\le b the derivatives of ϕ\phi with respect to ln⁡a\ln a and ln⁡b\ln b are −1+12(a/b)s-1+\frac{1}{2}(a/b)^s and −12(a/b)s-\frac{1}{2}(a/b)^s, the negatives of the two shares. The vertex term therefore contributes p(v)p(v), and summing the edge derivatives gives −ℓ(v)-\ell(v).

We next show that FGF_G is strictly convex in logarithmic pressures. For an edge with endpoint pressures exe^x and eye^y,

ϕ(ex,ey)=−x+y2+∣x−y∣2+e−s∣x−y∣2s.\phi(e^x,e^y)=-\frac{x+y}{2}+\frac{|x-y|}{2}+\frac{e^{-s|x-y|}}{2s}.

The first term is linear. The remaining two terms depend only on t=x−yt=x-y, and their derivative is 12sign⁡(t)(1−e−s∣t∣)\frac{1}{2}\operatorname{sign}(t)(1-e^{-s|t|}). This derivative is nondecreasing, so the edge term is convex. The vertex terms are exponentials in separate coordinates, so their sum is strictly convex, and hence so is FGF_G. The vertex terms also dominate the edge terms as pressures grow, so FGF_G attains a unique minimum. Write pG∗p_G^* for the pressures at this minimum. Our potential is the nonnegative difference

FG(p)−FG(pG∗)≥0.F_G(p)-F_G(p_G^*) \ge0.

The algorithm does not compute pG∗p_G^*. During a repair, the graph and its minimum are fixed, so the potential decreases by exactly the same amount as FGF_G.

Lemma 4.10 (Potential decrease). A repair round decreases the potential by

Ω(σln⁡β∑v moves(p(v)+ℓ(v))),\Omega\left(\sigma\ln\beta\sum_{v\ \mathrm{moves}} (p(v)+\ell(v))\right),

where pressures and loads are taken before the round.

Proof. Use primes for the state after the round. We apply convexity in logarithmic pressures at p′p' to obtain a lower bound on FG(p)−FG(p′)F_G(p)-F_G(p'). Substituting (7) gives

FG(p)−FG(p′)≥∑v(p′(v)−ℓ′(v))ln⁡p(v)p′(v)=ln⁡β∑v moves∣p′(v)−ℓ′(v)∣.F_G(p)-F_G(p') \ge\sum_v (p'(v)-\ell'(v))\ln\frac{p(v)}{p'(v)} = \ln\beta\sum_{v\ \mathrm{moves}} \lvert p'(v)-\ell'(v)\rvert.

For the equality, vertices whose pressures do not change contribute zero. A raise has ln⁡(p/p′)=−ln⁡β\ln(p/p')=-\ln\beta and still has ℓ′>p′\ell'>p' by Lemma 4.6. A lower has ln⁡(p/p′)=ln⁡β\ln(p/p')=\ln\beta and still has p′>ℓ′p'>\ell'. Thus each move contributes ln⁡β∣p′−ℓ′∣\ln\beta\lvert p'-\ell'\rvert.

We now bound ∣p′−ℓ′∣\lvert p'-\ell'\rvert using the pressure and load before the round. For a vertex that raises its pressure, Lemma 4.6 gives ℓ′−p′>σℓ′/(2+σ)\ell'-p'>\sigma\ell'/(2+\sigma). By (S3) and (5), ℓ′≥β−2sℓ≥ℓ/2\ell'\ge\beta^{-2s}\ell\ge\ell/2. Since ℓ>p\ell>p before the raise, we obtain ℓ′−p′=Ω(σ(p+ℓ))\ell'-p'=\Omega(\sigma(p+\ell)).

For a vertex that lowers its pressure, the same lemma gives p′−ℓ′>σp′/2p'-\ell'>\sigma p'/2. We have p′=p/β≥p/2p'=p/\beta\ge p/2 and p>ℓp>\ell before the lower, so again p′−ℓ′=Ω(σ(p+ℓ))p'-\ell'=\Omega(\sigma(p+\ell)). Multiplying these bounds by ln⁡β\ln\beta and summing over all moves in the round proves the result. □

Potential increase before repair. When the graph changes, the minimum value subtracted from FGF_G also changes. To bound the increase in potential, we first establish properties of the minimizing pressures pG∗p_G^*.

At the minimum, an isolated vertex has pressure 1/41/4 because its only term in FGF_G is its own pressure. A non-isolated vertex cannot have pressure 1/41/4 at the minimum. Its load would be at least 1/21/2, making the derivative in (7) negative, so raising its pressure would decrease FGF_G. Its minimizing pressure is therefore strictly above 1/41/4, so the derivative with respect to its logarithmic pressure must vanish. Hence its pressure equals its load. Since the loads sum to the number of edges, we obtain

∑vpG∗(v)=∣E(G)∣+14∣{v:deg⁡G(v)=0}∣.(8)\sum_v p_G^*(v)=|E(G)|+\frac14\lvert\{v:\deg_G(v)=0\}\rvert. \tag*{(8)}

Lemma 4.11 (Pressures at the minimum). (1) If pp is balanced, then every vertex vv satisfies

(1−2σ)p(v)≤pG∗(v)≤(1+2σ)p(v).(1-2\sigma)p(v)\le p_G^*(v)\le(1+2\sigma)p(v).

(2) If G⊆G′G\subseteq G' on the same vertex set, then pG∗(v)≤pG′∗(v)p_G^*(v)\le p_{G'}^*(v) for every vertex vv, and

∑v(pG′∗(v)−pG∗(v))≤∣E(G′)∣−∣E(G)∣.\sum_v\left(p_{G'}^*(v)-p_G^*(v)\right)\le|E(G')|-|E(G)|.

Proof. (1) For the upper bound, choose a vertex vv that maximizes pG∗(v)/p(v)p_G^*(v)/p(v). Every neighbor uu satisfies

pG∗(u)pG∗(v)≤p(u)p(v).\frac{p_G^*(u)}{p_G^*(v)}\le\frac{p(u)}{p(v)}.

The share rule therefore gives vv no more load under pG∗p_G^* than under pp. If vv has an edge, its pressure at the minimum equals its load, so

pG∗(v)≤ℓ(v)≤(1+2σ)p(v).p_G^*(v)\le\ell(v)\le(1+2\sigma)p(v).

If vv is isolated, both pressures are $1/4. Since vv maximizes the ratio, this proves the upper bound at every vertex.

For the lower bound, choose vv minimizing pG∗(v)/p(v)p_G^*(v)/p(v). The neighbor pressure ratios now satisfy the reverse inequality, so vv receives at least as much load under pG∗p_G^* as under pp. For a non-isolated vertex, this gives

pG∗(v)≥ℓ(v)≥(1−2σ)p(v).p_G^*(v)\ge\ell(v)\ge(1-2\sigma)p(v).

An isolated vertex again has pressure 1/41/4 under both assignments. This bounds the minimum ratio and proves the lower bound at every vertex.

(2) Suppose some minimizing pressure decreases when edges are added. Choose vv with the smallest ratio pG′∗(v)/pG∗(v)p_{G'}^*(v)/p_G^*(v), which is then less than 1. The vertex vv must have an edge in GG, since an isolated vertex already has the smallest allowed pressure, 1/41/4. By the choice of vv, each old neighbor's pressure relative to vv is at least as large under pG′∗p_{G'}^* as under pG∗p_G^*. Thus no old edge gives vv less load, and new edges can only add load. At both minima, vv's pressure equals its load, so pG′∗(v)≥pG∗(v)p_{G'}^*(v)\ge p_G^*(v), a contradiction. The total increase bound follows from (8), because adding edges cannot create isolated vertices. □

The next lemma uses these properties to bound the potential increase from the deletions, jumps, insertions, and resets that precede repair. Its proof is in Appendix A.3.

Lemma 4.12 (Potential increase from a batch). For a batch starting from balanced pressures, lines 1–6 of Algorithm 1 increase the potential by at most O(∣D∣+∣I∣)O(|D|+|I|).

Starting from balanced pressures lets us bound the potential increase from deletions by O(∣D∣)O(|D|). Jumps add at most ∣I∣|I|, and resets only decrease the potential. For insertions, jumps keep each vertex's number of new incident edges below four times its pressure. This bounds the potential increase by O(∣I∣)O(|I|) plus a constant times the total increase in minimizing pressures, which Lemma 4.11(2) bounds by ∣I∣|I|.

Corollary 4.13 (Work budget). Over any sequence of TT edge updates starting from the empty graph, the sum of p(v)+ℓ(v)p(v)+\ell(v) over all moves is O(T/(σln⁡β))O(T/(\sigma\ln\beta)). The pressure and load for each move are evaluated before its round.

Proof. Initially the graph is empty and all pressures are 1/41/4, so the potential is zero. Lemma 4.12 bounds the total increase from batches by O(T)O(T). Since the potential never becomes negative, the total decrease during repairs is also at most O(T)O(T). Lemma 4.10 then bounds the sum of p(v)+ℓ(v)p(v)+\ell(v) over all moves by O(T/(σln⁡β))O(T/(\sigma\ln\beta)). □

Combining this corollary with the cost of a move gives

O(Tσ2ln⁡β)=O(Tε−5log⁡n)O\left(\frac{T}{\sigma^2 \ln\beta}\right)=O(T\varepsilon^{-5}\log n)

expected work for the repair moves, using (4). § 4.7 combines this bound with the costs of jumps and edge updates.

Proof of Theorem 3.2

Accuracy. The stopping condition and the reset of isolated vertices ensure balance after every batch. § 3.2 therefore gives k(v)/(2+ε)≤k^(v)≤k(v)k(v)/(2+\varepsilon)\le\widehat{k}(v)\le k(v) for every vertex.

Work. The expected amortized cost of a move is O((p(v)+ℓ(v))/σ)O((p(v)+\ell(v))/\sigma) by Lemma 4.9, since p(v)≥1/4p(v)\ge1/4. Corollary 4.13 therefore bounds the total expected amortized work of the moves by

O(Tσ2ln⁡β)=O(Tε−5log⁡n).O\left(\frac{T}{\sigma^2 \ln\beta}\right)=O(T\varepsilon^{-5}\log n).

A jumping vertex has ℓ(v)≤(1+2σ)p(v)<deg⁡I(v)\ell(v)\le(1+2\sigma)p(v)<\deg_I(v): it was balanced or isolated before the batch, deletions only lower loads, and Lemma 4.3(2) gives p(v)<deg⁡I(v)/2p(v)<\deg_I(v)/2. Thus the expected amortized work of the jumps is O(∣I∣σ−1log⁡n)O(|I|\sigma^{-1}\log n) per batch. Each edge update costs O(1)O(1) expected amortized work. Every round has a move to pay for its overhead. Linearity of expectation over the work of the parallel primitives gives the total work bound.

Depth and space. Lemma 4.7 bounds the number of rounds, and Lemma 4.9 bounds the depth of each round and of the edge updates and jumps. Together they give depth

O(log⁡nln⁡β)⋅O(log⁡2n)=O(ε−3log⁡4n)O\left(\frac{\log n}{\ln\beta}\right)\cdot O(\log^2 n)=O(\varepsilon^{-3}\log^4 n)

per batch deterministically. Each vertex stores K+O(1)K+O(1) numbers, each edge two records, and every nonempty bucket contains a record. Thus the space is O(m+nK)O(m+nK) plus the table of MM rounded powers. The primitives use linear scratch space, and jump counters are rebuilt with O(K)O(K) scratch space per vertex. Initialization zeros the indices and counters in O(nK)O(nK) work. □

Experimental Evaluation

We implement our algorithm as DBP, for “dynamic balanced pressures”, and compare it with four baselines.

  • PLDS and PLDSOpt [24], the parallel batch-dynamic implementations of the level data structure.

  • Sun, The sequential algorithm of Sun et al. [29].

  • Static, which recomputes all core numbers from scratch.

DBP has guaranteed two-sided error bounds between 3.35 and 3.79 on our graphs, below the 4.2 guaranteed for PLDS. PLDSOpt uses fewer levels than PLDS and trades a weaker guarantee for speed. With batches of 10610^6 updates, DBP is 32× faster than PLDS and 4.1× faster than PLDSOpt in geometric mean on six social and web graphs, and 9.2× faster than PLDSOpt on three large graphs with up to 1.8 billion edges. Recomputing from scratch becomes faster than DBP only when a batch changes a large part of the graph, about a fifth of the edges of livejournal.

Implementation

DBP is written in C++ with ParlayLib [6]. It diverges from the theoretical algorithm of Theorem 3.2 in its parameters, its repair rule, the way it stores neighbors, and the estimates it reports. Like the PLDS implementations [24], it departs from the analyzed algorithm in some ways in order to obtain speed improvements in practice. We focus on preserving the provable approximation guarantee from our algorithm, however, due to the changes made we do not give a useful bound on the work of DBP.

Parameters. Theorem 3.2 sets s=⌈2ln⁡n/σ2⌉s=\lceil2\ln n/\sigma^2\rceil, which would be extremely large on our graphs. Instead, DBP uses σ=0.25\sigma=0.25 and the much smaller values s=28s=28 and K=4K=4 (§ 4). We round a share to one when the index difference exceeds bKbK for b=4b=4. Appendix § 8.§ 1 proves a maximum error bound for these parameters, which lies between 3.35 and 3.79 on our graphs.

Repair. Algorithm 1 moves every vertex with r^(v)\widehat{r}(v) outside 1±σ1\pm\sigma by one step per round. The implementation instead repairs in two monotone phases. In each round of the raise phase, every vertex with r^(v)>1+σ\widehat{r}(v)>1+\sigma moves to the largest index at which its approximate load is still at least 1−τσ1-\tau\sigma times its pressure, for τ=0.97\tau=0.97. It overshoots its balance point and ends with r^(v)\widehat{r}(v) just above 1−σ1-\sigma. The phase ends when no vertex has r^(v)>1+23σ\widehat{r}(v)>1+\frac{2}{3}\sigma. The lower phase then moves vertices with r^(v)<1−σ\widehat{r}(v)<1-\sigma symmetrically until no vertex has r^(v)<1−23σ\widehat{r}(v)<1-\frac{2}{3}\sigma. By (S2), raising a vertex cannot decrease the loads of its neighbors. So in the raise phase r^(v)\widehat{r}(v) drops only when vv itself is raised, and each such move leaves r^(v)≥1−τσ\widehat{r}(v)\ge1-\tau\sigma. The phase therefore creates no vertex with r^(v)<1−σ\widehat{r}(v)<1-\sigma. Symmetrically, the lower phase creates no vertex with r^(v)>1+σ\widehat{r}(v)>1+\sigma. When both phases end, no vertex is unbalanced, so the accuracy bounds of the balanced pressure frame work apply. Each phase terminates because indices move in one direction and are bounded.

Neighbor storage. The implementation replaces the structure of § 4 with a plain array of neighbors per vertex and keeps each vertex’s approximate load as one fixed-point number with 32 fractional bits. Thus, a moving vertex simply scans all its neighbors, recomputes its own approximate load from a table indexed by index differences, and atomically adds the change of each neighbor’s share to that neighbor’s load. A move in our practical implementation therefore costs O(deg⁡(v))O(\deg(v)) work instead of O((1+ℓ(v))/σ)O((1+\ell(v))/\sigma). A vertex with at least 4096 neighbors avoids most of this cost by listing separately all neighbors except those far below it, which would contribute nothing to its approximate load even if it moved down

Figure 3. Time per batch against average error when varying the parameters, on dblp with batches of 10510^5 and livejournal with batches of 10610^6, on 44 threads. DBP shows four settings with guaranteed error bounds between 2.6 and 3.8. PLDSOpt varies δ∈{0.2,0.4,0.8,1.6,3.2}\delta\in\{0.2, 0.4, 0.8, 1.6, 3.2\} and PLDS δ∈{0.4,1.6}\delta\in\{0.4, 1.6\}. Points are connected in the order of their parameter. Lower and further left is better.

by a fixed margin. The far neighbors count the vertex with share one, so its moves within the margin do not change their loads, and a move scans only the list. A neighbor joins the list when it rises out of the far range, and the list is rebuilt when the vertex moves down by more than the margin.

Reported estimates. The estimates of Theorem 3.2 never exceed k(v)k(v). To make the comparison with prior work easier, DBP reports two-sided estimates, and as in [24] the error of a vertex vv with k(v)>0k(v)>0 is

max⁡(k^(v)k(v),k(v)k^(v)).\max\left(\frac{\widehat{k}(v)}{k(v)},\frac{k(v)}{\widehat{k}(v)}\right).

For a non-isolated vertex, DBP reports p(v)/c−c+p(v)/\sqrt{c_{-}c_{+}}. Here c−c_{-} and c+c_{+} depend only on the parameters and nn, and Appendix B.1 proves c−k(v)≤p(v)≤c+k(v)c_{-}k(v) \le p(v) \le c_{+}k(v). So every error is at most c+/c−\sqrt{c_{+}/c_{-}}, the bound listed in Table 2.

GraphVerticesEdgeskmax⁡k_{\max}DBP bound
dblp317,0801,049,8661133.35
youtube1,138,4992,990,443513.41
wiki1,094,0182,787,9671243.41
stackoverflow2,584,16428,183,5181983.46
livejournal4,846,60942,851,2373723.50
orkut3,072,441117,185,0832533.47
brain784,262267,844,66912003.39
twitter41,652,2301,202,513,04624883.71
friendster65,608,3661,806,067,1353043.79

Table 2. Graphs, after removing self-loops, duplicate edges, and isolated vertices. The column kmax⁡k_{\max} is the largest core number. The last column is the guaranteed two-sided error bound of DBP (Appendix § 8.§ 1).

Setup

Machine and measurements. We use a GCP machine with two 44-core Intel Xeon Platinum 8481C processors (2.7 GHz), two-way hyper-threading, and 1.4 TiB of memory. Each run uses the cores of one processor, with 60 threads unless stated otherwise. All code is compiled with g++ 15.2 using -O3 and -march=native. The PLDS benchmark driver makes a pass over all vertices after every batch, and we removed it from the timed region. This makes PLDS and PLDSOpt up to twice as fast with small batches.

We report the average time per batch over all batches of a run, excluding the construction of the initial graph. On the six social and web graphs, the times in Table 3 and all Static times are medians of three runs. For the larger graphs, we use a single run. We compute errors against exact core numbers and report their average and maximum over the vertices with k(v)>0k(v)>0, after the last batch for Ins and Mix and after the middle batch for Del.

GraphTypeStaticPLDSPLDSOptDBPSunPLDSPLDSOptDBPSunPLDSPLDSOptDBPSun
Time per batch (ms)Average errorMaximum error
dblpIns10.4110749.711.1154512.661.971.481.034.003.002.831.50
Del1.7944.813.13.46147881.512.371.651.012.006.002.312.00
Mix7.85130568.714.2171421.541.311.381.014.004.002.972.00
youtubeIns20.184968.921.3189901.711.431.181.014.003.003.032.00
Del16.069.329.212.0156761.451.251.301.014.003.003.032.00
Mix25.660067.920.8172591.581.331.221.014.003.003.032.00
wikiIns17.2123261.520.690061.661.521.091.014.173.002.421.52
Del12.677.422.88.68119701.541.451.121.004.004.002.421.38
Mix18.516539.920.787121.531.411.151.014.003.002.421.45
stackoverflowIns69.983999.221.7187292.541.971.151.074.173.002.751.52
Del65.628457.015.4200331.731.491.321.044.004.002.751.47
Mix11066011613.7128632.501.941.151.074.173.002.701.52
livejournalIns132189014734.0262862.621.831.231.074.173.003.111.53
Del12942788.430.5252491.601.281.331.034.004.003.112.00
Mix223136914318.4186872.601.821.231.074.173.003.111.53
orkutIns247213517830.3302603.332.021.241.214.173.002.301.52
Del24398713630.1302911.701.241.251.104.004.002.381.40
Mix395138918317.8190723.322.011.241.204.173.002.301.52
brainIns333170316636.4–3.491.861.27–4.193.003.01–
Del302–21339.0––1.251.24––4.003.01–
Mix441–34015.7––1.861.27––3.003.01–
twitterIns1683187434459.7–3.162.271.25–4.203.003.02–
Del1686–32330.6––1.341.32––4.002.55–
Mix2662–65425.4––2.261.25––3.003.02–
friendsterIns31083244*26934.5––1.951.22––3.003.00–
Del2943–20333.0––1.271.31––4.002.59–
Mix4884–27323.5––1.951.22––3.003.00–

Table 3. Time per batch in milliseconds, and average and maximum error, for batches of 10610^6 updates on 60 threads. Static is the time to recompute all core numbers from scratch after a batch, without building the graph. Sun is the sequential algorithm of Sun et al., which processes the updates one at a time on one thread. Its time is 10610^6 times its average time per update. Bold marks the fastest system and the lowest average error among PLDS, PLDSOpt, and DBP in each row. All errors are two-sided, max⁡(k^(v)/k(v),k(v)/k^(v))\max(\hat{k}(v)/k(v), k(v)/\hat{k}(v)), and the guaranteed error bounds are 4.2 for PLDS and 3.35–3.79 for DBP (Table 2). On the last three graphs, we ran PLDS only for Ins and did not run Sun. *Average over the first 1705 of 1807 batches (Section 5.4).

Graphs and updates. We use the graphs of [24] in Table 2 and the update sequences published with PLDS. Six are social and web graphs from SNAP [23]. The three large graphs are brain, a dense human brain network from NeuroData (https://neurodata.io), twitter, the Twitter follower network [22] made undirected, and friendster, from SNAP. In Ins, all edges are inserted into an empty graph in batches. In Del, all edges are deleted from the full graph in batches. In Mix, one batch with 5⋅1055 \cdot10^{5} insertions and 5⋅1055 \cdot10^{5} deletions is applied to the graph without the inserted edges. The updates of wiki and stackoverflow follow their timestamps, and those of the other graphs are in random order.

Algorithms. All errors in this section are two-sided. In this form, PLDS and Sun et al. guarantee 2+ε2+\varepsilon with suitable parameters, listed as the one-sided 4+ε4+\varepsilon in Table 1. PLDS uses δ=0.4\delta=0.4 and λ=3\lambda=3, the setting chosen in [24], with guaranteed error bound (2+3/λ)(1+δ)=4.2(2+3/\lambda)(1+\delta)=4.2. PLDSOpt uses the same parameters with ⌈log⁡1+ηn/50⌉\lceil\log_{1+\eta} n/50\rceil levels per group, which the PLDS paper describes as trading slightly worse approximation bounds for speed. For the sequential implementation of Sun et al., we use α=1.1\alpha=1.1, which gives its most accurate estimates but has no efficiency guarantee [24]. We omit the exact dynamic algorithms evaluated in [24], which were slower than PLDSOpt there on batches of 10610^{6} updates.

Static recomputation. We also measure the time to recompute all core numbers from scratch after a batch, with the parallel exact algorithm of Dhulipala et al. [13] and the parallel static approximation of [24] with its default parameters, both from GBBS. The approximation is 1.1 to 3.4 times faster than the exact algorithm on every input, and we report its time as Static. Static excludes the time to build the graph, which is longer than the algorithm itself (on livejournal Ins, 0.29 s against 0.13 s per batch), so it is a lower bound on the cost of recomputing.

Batches of a Million Updates

Table 3 lists the results for batches of 10610^{6} updates. On the six social and web graphs, DBP is the fastest system on every input, that is, every combination of graph and update type. It is 32×32\times faster than PLDS in geometric mean (from 5.8×5.8\times to 100×100\times) and 4.1×4.1\times faster than PLDSOpt (from 1.9×1.9\times to 10.3×10.3\times). Its maximum errors, 2.30–3.11, stay within its guaranteed error bounds, while those of PLDSOpt reach 6. The same holds after every batch. The largest value over all batches, 3.34 on orkut, is below its bound of 3.47. The average error of DBP, 1.09–1.65, is lower than that of PLDS (1.45–3.33) on all inputs except dblp and del, and lower than that of PLDSOpt (1.24–2.37) on 14 of the 18 inputs for the six graphs.

The sequential implementation of Sun et al. has lower average error than DBP on every input, 1.00–1.21, but takes 8.7 to 30 μ\mus per update, 420 to 4300 times as long as DBP.

Recomputing from scratch competes with DBP only on the three small graphs, where a batch of 10610^{6} updates is between a third and all of the graph. On dblp, youtube, and wiki, Static takes 0.52 to 1.45 times as long as DBP. On stackoverflow, livejournal, and orkut, DBP is 3.2 to 22 times faster. Static is faster than PLDSOpt on 12 of the 18 inputs and faster than PLDS on all of them. Section 5.6 shows how these comparisons depend on the batch size.

Work. Table 4 counts vertex moves per update, a measure of work that does not depend on how a move is implemented. PLDSOpt moves the fewest vertices. In geometric mean over the 18 inputs, it makes 0.30 times as many moves as DBP and visits 0.27 times as many neighbors, yet DBP is 4.1 times faster. PLDS makes 1.9 times as many moves as DBP and 2.3 times as many neighbor visits but takes 32 times as long. Most of the speedup of DBP therefore comes from cheaper moves. A move in PLDS updates hash tables that store the neighbors of a vertex bucketed by level, while a move in DBP adds to loads stored in plain arrays (§ 5.1).

Large Graphs

The last nine rows of Table 3 are for brain, twitter, and friendster, which have 2.7⋅1082.7 \cdot10^{8} to 1.8⋅1091.8 \cdot10^{9} edges. DBP is faster than PLDSOpt on all nine inputs, by 9.2×9.2\times in geometric mean (from 4.6×4.6\times to 25.8×25.8\times), and 31 to 94 times faster than PLDS on Ins. The gaps are largest for Mix, where PLDSOpt takes 0.27 to 0.65 s for its single batch and DBP 16 to 25 ms. The average error of DBP, 1.22–1.32, is lower than that of PLDSOpt (1.25–2.27) on eight of the nine inputs and lower than that of PLDS (3.16–3.49). Its maximum error, 2.55–3.02, stays within its guaranteed error bounds of 3.39–3.79, while that of PLDSOpt reaches 4.00.

PLDS needs more memory than the other systems. Its peak resident memory is 75 GiB on brain and 1.15 TiB on twitter, while DBP uses at most 346 GiB and PLDSOpt at most 302 GiB. We stopped PLDS on friendster Ins after 1705 of its 1807 batches, when it used 1.24 TiB. Table 3 reports its average over these batches.

GraphIns PLDSIns PLDSOptIns DBPDel PLDSDel PLDSOptDel DBPMix PLDSMix PLDSOptMix DBP
dblp13.00.410.900.180.180.257.320.240.43
youtube3.010.211.110.090.090.541.030.120.60
wiki2.950.110.820.050.050.050.070.020.68
stackoverflow0.970.150.300.100.090.170.320.080.19
livejournal5.850.301.230.260.181.002.130.110.27
orkut3.970.200.600.310.140.510.810.040.08

Table 4. Vertex moves per update for batches of 10610^{6} updates. A move changes the level of a vertex (PLDS, PLDSOpt) or its index (DBP) by any number of steps at once.

Static takes 0.30 to 4.9 s per batch on these graphs, 7.7× to 208× as long as DBP. PLDSOpt is also faster than Static on all nine inputs, by 1.3 to 18 times, but PLDS is slower than Static on all three Ins inputs.

Accuracy and Running Time

Figure 3 varies the parameters on dblp with batches of 10510^{5} and on livejournal with batches of 10610^{6}, as in [24]. PLDS and PLDSOpt vary δ\delta with λ=3\lambda= 3. DBP uses σ∈{0.1,0.15,0.25,0.3}\sigma\in\{0.1, 0.15, 0.25, 0.3\}, with guaranteed error bounds of at most 2.7, 2.9, 3.5, and 3.8 on these two graphs. Table 3 uses σ=0.25\sigma= 0.25, and the other settings also change ss, KK, and bb.

The setting of Table 3 is faster than every setting of PLDS and PLDSOpt in all six panels, taking 0.14 to 0.73 times as long as the fastest, and it is more accurate than every PLDSOpt setting in three panels. The setting with the strongest guarantee, σ=0.1\sigma= 0.1, is more accurate than every PLDSOpt setting on livejournal and takes 0.23 to 0.68 times as long as the fastest. On dblp, whose batches are ten times smaller, its average error is at most 0.01 above that of the most accurate PLDSOpt setting, and it takes 1.2 to 1.3 times as long as the fastest.

Batch Size

Figure 4 shows the time per batch for batches of 10210^{2} to 10610^{6} updates, and up to 10710^{7} for Ins and Del. DBP is 7.7 to 113 times faster than

Figure 4. Time per batch against batch size on 60 threads. We did not run PLDS with batches of 10210^{2} on livejournal.

PLDS at every batch size. It is faster than PLDSOpt at every batch size on stackoverflow, by 1.5 to 9.9 times, and on livejournal except Del with batches of 10210^{2}, where PLDSOpt is 1.4× faster. On dblp, the smallest graph, PLDSOpt is faster with batches of 10210^{2}, by up to 3.0×, and on Del also with 10310^{3}.

Static takes about the same time for every batch size, since it processes the whole graph, while the time of a dynamic system grows with the batch size. Table 5 lists the batch size at which each system becomes slower than Static. PLDS breaks even with batches of 1.3⋅1041.3 \cdot10^{4} to 1.2⋅1051.2 \cdot10^{5} updates, at most 0.3% of the graph, and PLDSOpt with 5.6⋅1055.6 \cdot10^{5} to 1.8⋅1061.8 \cdot10^{6}, 2 to 5%. DBP breaks even only with 5.9⋅1065.9 \cdot10^{6} to 8.7⋅1068.7 \cdot10^{6}, about a fifth of the graph. On stackoverflow Del, it is still faster than Static with batches of 10710^{7}, more than a third of the graph. For Mix, DBP is faster than Static even with all 10610^6 updates in one batch.

GraphTypePLDSPLDSOptDBP
stackoverflowIns1.3⋅1041.3 \cdot10^{4}5.6⋅1055.6 \cdot10^{5}5.9⋅1065.9 \cdot10^{6}
Del7.8⋅1047.8 \cdot10^{4}1.3⋅1061.3 \cdot10^{6}>107> 10^{7}
Mix6.3⋅1046.3 \cdot10^{4}9.3⋅1059.3 \cdot10^{5}never
livejournalIns1.3⋅1041.3 \cdot10^{4}8.7⋅1058.7 \cdot10^{5}8.7⋅1068.7 \cdot10^{6}
Del1.2⋅1051.2 \cdot10^{5}1.8⋅1061.8 \cdot10^{6}8.4⋅1068.4 \cdot10^{6}
Mix7.7⋅1047.7 \cdot10^{4}nevernever

Table 5. Batch size at which recomputing from scratch (Static) becomes faster than each system, interpolated between the measured batch sizes on a log scale. A bound marks a system that is faster than Static at the largest measured batch size, and never marks one that is faster even with all 10610^{6} updates of Mix in one batch.

Number of Threads

Figure 5 shows the time per batch on livejournal for 1 to 88 threads. With 60 threads, DBP is 27, 35, and 23 times faster than with one thread for Ins, Del, and Mix. On dblp, the factors are 18, 20, and 23. Beyond 44 threads, the number of cores, threads share cores through hyper-threading. Going from 44 to 88 threads reduces the time by 6–19% on livejournal, and on dblp its effect ranges from 15% slower to 4% faster. PLDSOpt gains more from parallelism on Ins, a factor of 42 from 1 to 60 threads, but DBP is 6.7 times faster on one thread and faster on 16 threads than PLDSOpt on 88. On one thread (i.e., measuring empirical work-efficiency), DBP also processes updates 24 to 44 times faster than the sequential implementation of Sun et al. on livejournal and 41 to 109 times faster on dblp.

Figure 5. Time per batch on livejournal against the number of threads, with batches of 10610^6. We measured PLDS and PLDSOpt only for Ins. The shaded region uses hyper-threads.

Conclusion

We gave a batch-dynamic algorithm that maintains a one-sided (2+ε)(2+\varepsilon)-approximation of all core numbers with O(ε−5log⁡n)O(\varepsilon^{-5}\log n) expected amortized work per update and polylogarithmic depth per batch. To the best of our knowledge, the best previous guarantees were a factor of 4+ε4+\varepsilon using O(log⁡2n)O(\log^2 n) amortized work. Under the OMv conjecture no algorithm with polylogarithmic update and query time can achieve a factor below two [12].

Our algorithm is based around dynamically maintaining balanced pressures. Edge shares vary smoothly with pressure, so we can restore balance by making small pressure changes in parallel. We use a potential argument to bound the total work over any sequence of batches. The same balanced structure also enables approximating the densest-subgraph value and supports the applications in Appendix § 9. In our experiments, an implementation with a smaller guaranteed error bound than PLDS is 32× faster than PLDS and 4.1× faster than its heuristic variant PLDSOpt in geometric mean on six social and web graphs, and 9.2× faster than PLDSOpt on three graphs with up to 1.8 billion edges.

To keep the presentation simple, we did not try to optimize the dependence of the work on ε\varepsilon; we know that at least one factor of 1/ε1/\varepsilon can be removed from the bound of Theorem 3.2 but at the expense of complicating the presentation. Some interesting questions are to

further simplify the framework presented here, and to implement some of the other applications of the general framework explored in the PLDS paper and other orientation papers, which have so far mostly only been studied in theory. Our practical implementation currently repairs balance with a simple rule that moves vertices directly past their balance points, to just inside the opposite threshold, in monotone phases. Since it does repair all vertices, it gives provable coreness guarantees, but we have no useful bound on its work. Such a bound would cover the version of the algorithm that runs fastest in practice.

Omitted Proofs

Additional Details about Primitives

For small batches, a depth bound that holds with high probability in a primitive’s input size need not hold with high probability in the graph size nn. The implementations below give deterministic depth bounds for every batch size while preserving the expected work bounds. All keys below occupy O(1)O(1) words and admit constant-time comparison and hashing.

Lemma A.1. Semisorting ℓ\ell items takes O(ℓ)O(\ell) expected work, O(ℓ)O(\ell) space, and deterministic O(log⁡2(ℓ+2))O(\log^{2}(\ell+2)) depth.

Proof. We start with the Las Vegas semisort of [18], adapted to binary forking as in [8]. It has linear expected work and space, and logarithmic depth w.h.p. We run independent attempts on copies of the input, aborting an attempt before its depth exceeds Clog⁡(ℓ+2)C\log(\ell+2) or its space exceeds CℓC\ell. For a sufficiently large constant CC, the depth bound and Markov’s inequality for space ensure that each attempt succeeds with probability at least 1/21/2. We reuse the scratch space between attempts, clearing it in linear work and logarithmic depth.

After ⌈2log⁡(ℓ+2)⌉\lceil2\log(\ell+2)\rceil failed attempts, we finish with deterministic parallel mergesort. Each merge takes linear work and logarithmic depth [9], so the sort takes O(ℓlog⁡(ℓ+2))O(\ell\log(\ell+2)) work, linear space, and O(log⁡2(ℓ+2))O(\log^{2}(\ell+2)) depth. Each attempt has linear expected work, the expected number of attempts is at most two, and the probability of needing mergesort is at most (ℓ+2)−2(\ell+2)^{-2}. The total expected work is therefore O(ℓ)O(\ell). Both the capped sequence of attempts and the final sort have deterministic O(log⁡2(ℓ+2))O(\log^{2}(\ell+2)) depth and use linear space. □

Lemma A.2. A dictionary with q+1q+1 keys uses O(q+1)O(q+1) space. A batch of ℓ\ell lookups takes O(ℓ)O(\ell) expected work and deterministic O(log⁡(q+ℓ+2))O(\log(q+\ell+2)) depth. A batch of ℓ\ell updates takes O(ℓ)O(\ell) expected amortized work and deterministic O(log⁡2(q+ℓ+2))O(\log^{2}(q+\ell+2)) depth. Updates use O(q+ℓ+1)O(q+\ell+1) space, and listing all keys takes O(q+1)O(q+1) work and logarithmic depth. The expected work bounds assume that the stored keys and requested operations are independent of the dictionary’s random choices.

Proof. We hash keys into C=Θ(q+1)C=\Theta(q+1) cells using a universal hash function. Each cell stores a sorted array of record pointers, so records keep their addresses when the arrays change. Geometric resizing maintains the capacity bound, with a fresh hash function chosen on each rebuild. For any fixed lookup key, the expected number of keys in its cell is at most 1+q/C=O(1)1+q/C=O(1). Binary search therefore has expected constant work, deterministic logarithmic depth, and constant scratch space.

For an update batch, we group and combine operations by key using Lemma A.1, leaving r≤ℓr\le\ell distinct keys. If r≤Cr\le C, we use the same lemma to group the remaining updates by hash cell. Within each cell, we sort the updates by key with deterministic parallel mergesort, merge them with the old array, and filter out deleted records. If rir_i updates enter cell ii, universality gives

E[∑iri2]≤r+r(r−1)C=O(r).\mathbb{E}\left[\sum_i r_i^2\right]\le r+\frac{r(r-1)}{C}=O(r).

Hence sorting costs O(r)O(r) expected work, since rilog⁡(ri+1)=O(ri2)r_i\log(r_i+1)=O(r_i^2). To bound the work of merging and filtering, let AA be the total number of old records in cells touched by the batch. A union bound over the updated keys gives

E[A]≤r+qrC=O(r).\mathbb{E}[A]\le r+\frac{qr}{C}=O(r).

We merge each touched cell’s array with its updates once, so the merges and subsequent filters take O(A+r)O(A+r) work in total. Since A≤qA\le q, they use O(q+r)O(q+r) space. Processing the cells in parallel gives deterministic O(log⁡2(q+ℓ+2))O(\log^{2}(q+\ell+2)) depth, even if every key hashes to the same cell.

If r>Cr>C, we rebuild the whole dictionary by semisorting its records together with the updates by key, applying the updates, and hashing the surviving keys into a fresh table of proportional capacity. Here q=O(r)q=O(r), so semisorting and applying the updates take O(r)O(r) expected work. The collision calculation above gives the same bound for building the sorted cell arrays. Geometric resizes use the same rebuilding procedure; we charge their linear expected work to the updates since the preceding resize. Every rebuild has deterministic O(log⁡2(q+ℓ+2))O(\log^{2}(q+\ell+2)) depth and uses linear space. To list the records, we scan the cell directory and its arrays in O(q+1)O(q+1) work and logarithmic depth. □

In our algorithm, the graph updates and pressure indices determine the dictionary’s keys and requested operations. Random choices affect their representation and processing order, and exact integer arithmetic ensures that the order does not change any sum or test. The expected work bounds therefore apply throughout the update sequence, and the deterministic depth bounds compose over all rounds.

Finite Precision

Use a table of MM rational numbers obtained by rounding 2i/M2^{i/M} down, for 0≤i<M0 \le i < M, with relative error at most σ/64\sigma/64. A common denominator that is a power of two with O(log⁡n)O(\log n) bits suffices, since 1/ε≤nO(1)1/\varepsilon\le n^{O(1)}. Each entry can be computed with integer arithmetic. Compute 2x/M2^{x/M} as 2⌊x/M⌋2^{\lfloor x/M \rfloor} times the entry for x mod Mx \bmod M. This gives both pressures and shares: p=2j/M/4p = 2^{j/M}/4, and 2d/K=2sd/M2^{d/K} = 2^{sd/M} because M=sKM = sK. Thus pressures round down with relative error at most σ/64\sigma/64. Multiplying this value by (1−2σ)/(1+2σ)(1 - 2\sigma)/(1 + 2\sigma) gives the reported estimate. A share 2−d/K2^{-d/K} has the same relative error. A share 1−122−d/K1 - \frac{1}{2}2^{-d/K} for d>0d > 0 has absolute error at most σ/128\sigma/128, hence relative error at most σ/64\sigma/64, since it is at least 1/21/2.

The window counters use the same table and the power-of-two factor from Section 4.4. The resulting sum has relative error at most σ/64\sigma/64. All computed contributions have a common power-of-two denominator, so sums can be maintained exactly, without accumulating rounding error. A window has K⌈log⁡(4n)⌉K\lceil\log(4n)\rceil levels, so each neighbor adds O(n)O(n) to one counter. Each counter is therefore O(n2)O(n^2). The scaling factors need O(log⁡n)O(\log n) bits as well. Hence every stored number uses O(1)O(1) words and every test is an exact comparison of integers.

The tests and the reported estimates also need σ=ε/16\sigma= \varepsilon/16 in O(1)O(1) words. The tests compare r~(v)\widetilde r(v) with 1±σ1 \pm\sigma and 1±12σ1 \pm\frac{1}{2}\sigma, and the estimate multiplies the rounded pressure by (1−2σ)/(1+2σ)(1 - 2\sigma)/(1 + 2\sigma). Both are exact because Theorem 3.2 takes ε\varepsilon to be a rational number whose numerator and denominator are at most nO(1)n^{O(1)}.

The accuracy guarantee and the bounds of the theorem extend to every 0<ε≤10 < \varepsilon\le1 with 1/ε≤nO(1)1/\varepsilon\le n^{O(1)}. For such an ε\varepsilon, let ε′\varepsilon' be the largest power of two at most ε\varepsilon. It satisfies the assumption of the theorem, and ε/2<ε′≤ε\varepsilon/2 < \varepsilon' \le\varepsilon. Running the data structure with ε′\varepsilon' in place of ε\varepsilon therefore gives estimates that satisfy the guarantee for ε\varepsilon, and increases the work, depth, and space bounds by at most constant factors.

Potential Increase from a Batch

We also need a bound on how much an edge term can change. It decreases in each pressure and satisfies ϕ(ca,cb)=ϕ(a,b)−ln⁡c\phi(ca, cb) = \phi(a, b) - \ln c. Take c=max⁡(a′/a,b′/b)c = \max(a'/a, b'/b), so a′≤caa' \le ca and b′≤cbb' \le cb. Then ϕ(a′,b′)≥ϕ(ca,cb)=ϕ(a,b)−ln⁡c\phi(a', b') \ge\phi(ca, cb) = \phi(a, b) - \ln c, proving

ϕ(a,b)−ϕ(a′,b′)≤ln⁡max⁡(a′a,b′b).(9)\phi(a, b) - \phi(a', b') \le\ln\max\left(\frac{a'}{a}, \frac{b'}{b}\right). \tag*{(9)}

Proof of Lemma 4.12. Let GG, GDG_D, and G′G' be the graphs before the batch, after deletion, and after insertion. Let pp and pˉ\bar p be the pressures before and after the jumps, and write ϕe(p)=ϕ(p(u),p(v))\phi_e(p) = \phi(p(u), p(v)) for the term of edge e=uve = uv.

Deletion. By Lemma 4.11(2), the minimizing pressures decrease by at most ∣D∣|D| in total. Since edge terms do not increase when pressures rise,

FGD(pG∗)−FGD(pGD∗)≤∑v(pG∗(v)−pGD∗(v))≤∣D∣.F_{G_D}(p_G^*) - F_{G_D}(p_{G_D}^*) \le\sum_v \left(p_G^*(v) - p_{G_D}^*(v)\right) \le|D|.

Also pG∗≥(1−2σ)pp_G^* \ge(1 - 2\sigma)p by Lemma 4.11(1), so (9) gives ϕe(pG∗)−ϕe(p)≤−ln⁡(1−2σ)\phi_e(p_G^*) - \phi_e(p) \le-\ln(1 - 2\sigma) for each deleted edge. Therefore

potential change=FGD(pG∗)−FGD(pGD∗)+∑e∈D(ϕe(pG∗)−ϕe(p))≤(1−ln⁡(1−2σ))∣D∣=O(∣D∣).\begin{aligned} \text{potential change} &= F_{G_D}(p_G^*) - F_{G_D}(p_{G_D}^*) \\ &\quad+ \sum_{e \in D}\left(\phi_e(p_G^*) - \phi_e(p)\right) \\ &\le(1 - \ln(1 - 2\sigma))|D| = O(|D|). \end{aligned}

Jumps. Pressures increase by at most ∣I∣|I| in total by Lemma 4.3(2), and edge terms do not increase. Thus jumps add at most ∣I∣|I| to the potential.

Insertion. Let Δ=pGD∗−pG′∗\Delta= p_{G_D}^* - p_{G'}^*. Lemma 4.11 gives Δ≥0\Delta\ge0, ∑vΔ(v)≤∣I∣\sum_v \Delta(v) \le|I|, and pGD∗≤pG∗≤(1+2σ)p≤(1+2σ)pˉp_{G_D}^* \le p_G^* \le(1 + 2\sigma)p \le(1 + 2\sigma)\bar p. Hence

ln⁡pGD∗(w)pˉ(w)≤ln⁡(1+2σ+Δ(w)pˉ(w))≤2σ+Δ(w)pˉ(w).\ln\frac{p_{G_D}^*(w)}{\bar p(w)} \le\ln\left(1 + 2\sigma+ \frac{\Delta(w)}{\bar p(w)}\right) \le2\sigma+ \frac{\Delta(w)}{\bar p(w)}.

Since FGD(pGD∗)≥min⁡FGDF_{G_D}(p_{G_D}^*) \ge\min F_{G_D}, insertion adds at most ∑e∈I(ϕe(pˉ)−ϕe(pGD∗))\sum_{e \in I}(\phi_e(\bar p) - \phi_e(p_{G_D}^*)) to the potential. By (9), each summand is bounded by the larger endpoint log-ratio. Sum the inequality and use deg⁡I(w)<4pˉ(w)\deg_I(w) < 4\bar p(w) to get

potential increase≤2σ∣I∣+∑wdeg⁡I(w)Δ(w)pˉ(w)≤(4+2σ)∣I∣.\text{potential increase} \le2\sigma|I| + \sum_w \frac{\deg_I(w)\Delta(w)}{\bar p(w)} \le(4 + 2\sigma)|I|.

Isolated vertices. Resetting their pressures to 1/41/4 lowers their only terms in FG′F_{G'}. In total the potential increases by O(∣D∣+∣I∣)O(|D| + |I|). □\square

Deterministic Sequential Implementation

The pressure updates and their potential analysis are deterministic. We can implement them sequentially with the same amortized time bound as the expected work bound in Theorem 3.2, retaining its accuracy and space bounds and using the same initialization. Execute the same rounds and the same remove–change–reinsert phases of RELABEL; only the storage and bookkeeping change.

Replace high lists and the contents of low buckets by doubly linked lists, using the existing pointers to edge records for constant-time removal. Keep each vertex’s occupied buckets in index order, with a finger search tree that supports O(log⁡n)O(\log n) search and O(1)O(1) amortized insertion or deletion at a known position [20]. A record moved by a one-step round goes to the bucket at its old index or an adjacent index, or to one of constantly many indices at the high/low boundary. Keep emptied buckets until the round ends so that old pointers remain valid. A pointer at the window boundary similarly handles its one-index shifts. Thus ordinary moves need no general tree searches. Use mark bits to collect each edge once, update sums directly, and maintain the moving vertices in a linked list with membership flags. Clear marks only on the records visited.

External edge updates locate records in a balanced search tree keyed by edge; internal moves use pointers. Updates and jumps may search buckets, costing O(log⁡n)O(\log n) per record. Rebuilding a jumping vertex’s counters visits at most O(Klog⁡n)O(K\log n) occupied indices in its new window. The amortized cost per one-step move is O(1+ℓ(v)/σ)O(1 + \ell(v)/\sigma). An edge update costs O(log⁡n)O(\log n), and a jump costs O((1+ℓ(v))σ−1log⁡n)O((1 + \ell(v))\sigma^{-1}\log n). As in Section 4.7, ℓ(v)<deg⁡I(v)\ell(v) < \deg_I(v) at each jumping vertex, so all jumps cost O(∣I∣σ−1log⁡n)O(|I|\sigma^{-1}\log n) per batch. Corollary 4.13 pays for the ordinary updates exactly as before. The total time for TT updates is therefore O(Tε−5log⁡n)O(T\varepsilon^{-5}\log n), deterministically, after initialization.

Details for the Experiments

Accuracy for Fixed Exponents

The proof of Theorem 3.3 uses the large exponent ss only in its last step. The following version holds for every ss and for every balance tolerance.

Lemma B.1. Let 0<λ−≤1≤λ+0 < \lambda_- \le1 \le\lambda_+, and suppose that every non-isolated vertex vv satisfies λ−p(v)≤ℓ(v)≤λ+p(v)\lambda_-p(v) \le\ell(v) \le\lambda_+p(v). Then every such vertex satisfies

k(v)2λ+≤p(v)≤32λ−k(v)n1/(s+1).\frac{k(v)}{2\lambda_+} \le p(v) \le\frac{3}{2\lambda_-}k(v)n^{1/(s+1)}.

Proof. The lower bound is proved as in Theorem 3.3. For the upper bound, repeat that proof with weight psp^s in place of pσp^\sigma. For an edge with pressures a≤ba \le b and t=(b/a)st = (b/a)^s, the weighted contribution is

as(1−12t)+bs⋅12t=as(1+t−12t)≤32as.a^s\left(1-\frac{1}{2t}\right)+b^s\cdot\frac{1}{2t} =a^s\left(1+\frac{t-1}{2t}\right)\le\frac{3}{2}a^s.

The charging argument then gives

λ−∑u∈Sp(u)s+1≤32k∑u∈Sp(u)s,\lambda_-\sum_{u\in S}p(u)^{s+1}\le\frac{3}{2}k\sum_{u\in S}p(u)^s,

and the power mean inequality gives p(v)≤32λ−k∣S∣1/(s+1)p(v)\le\frac{3}{2\lambda_-}k|S|^{1/(s+1)} as before. □

The implementation. The repair of Section 5.1 stops when every non-isolated vertex has approximate ratio within 1±32σ1\pm\frac{3}{2}\sigma. Its approximate loads have the cutoffs of Section 4.4 with B=bK~B=b\widetilde K for a smaller bb. A share is counted as one when the index difference exceeds BB and is ignored when the difference is below −B−K⌈log⁡(4n)⌉-B-K\lceil\log(4n)\rceil. Let η=2−b\eta=2^{-b}. A share counted as one is at least 12\frac{1}{2} and is overcounted by less than η/2\eta/2, so by a factor less than 1+η1+\eta. Each ignored share is less than η/(8n)\eta/(8n), so less than η/8\eta/8 is ignored in total. Each share is rounded to a multiple of 2−322^{-32}, which changes a load by at most n2−33n2^{-33}. Since every pressure is at least 14\frac{1}{4}, every non-isolated vertex satisfies the hypothesis of Lemma B.1 with

λ+=1+32σ+η2+4n2−33,λ−=1−32σ−4n2−331+η.\lambda_+=1+\frac{3}{2}\sigma+\frac{\eta}{2}+4n2^{-33}, \qquad \lambda_-=\frac{1-\frac{3}{2}\sigma-4n2^{-33}}{1+\eta}.

The lemma gives the interval c−k(v)≤p(v)≤c+k(v)c_-k(v)\le p(v)\le c_+k(v) with c−=1/(2λ+)c_-=1/(2\lambda_+) and c+=3n1/(s+1)/(2λ−)c_+=3n^{1/(s+1)}/(2\lambda_-). Reporting p(v)/c−c+p(v)/\sqrt{c_-c_+} bounds the two-sided error by c+/c−\sqrt{c_+/c_-}, where nn is the number of vertex identifiers of the input. For DBP (σ=0.25\sigma=0.25, s=28s=28, b=4b=4) this bound is between 3.35 and 3.79 on the graphs of Table 2.

Applications

The applications below use the balanced pressures maintained by the data structure of Theorem 3.2.

Write α\alpha for arboricity (the minimum number of forests covering the edges) and ρ=max⁡∅≠S⊆V∣E(S)∣/∣S∣\rho=\max_{\emptyset\ne S\subseteq V}|E(S)|/|S| for the maximum subgraph density; thus ρ≤α\rho\le\alpha. Table 6 gives bounds for fixed ε>0\varepsilon>0 and clique size k≥3k\ge3. In amortized update bounds, α\alpha denotes the maximum arboricity over the update sequence; forest and color counts use the current arboricity. Note that none of the applications require knowledge of the arboricity as input.

Batch-dynamic problemOur workEarlier work
Acyclic orientation, d+(v)≤(2+ε)k(v)d^{+}(v) \le(2+\varepsilon)k(v)O(log⁡n)O(\log n)O(log⁡2n)O(\log^{2} n), factor 4+ε4+\varepsilon
(1+ε)(1+\varepsilon)-approximate densest subgraphO(log⁡n)O(\log n)O(log⁡2n)O(\log^{2} n), sequential [11]
Maximal matchingO(α+log⁡n)O(\alpha+\log n)O(α+log⁡2n)O(\alpha+\log^{2} n)
Exact kk-clique countO(αk−2log⁡n)O(\alpha^{k-2}\log n)O(αk−2log⁡2n)O(\alpha^{k-2}\log^{2} n)
Partition into O(α)O(\alpha) forestsO(log⁡n)O(\log n)O(log⁡2n)O(\log^{2} n)
Implicit 2O(α)2^{O(\alpha)}-coloringO(log⁡n)O(\log n)O(log⁡2n)O(\log^{2} n)
Explicit O(αlog⁡n)O(\alpha\log n)-coloringO(log⁡n)O(\log n)O(log⁡2n)O(\log^{2} n)

Table 6. Expected amortized work per update for constant accuracy. Earlier bounds use PLDS [24], except for density. Forests and implicit coloring apply the same reductions to PLDS. Explicit coloring assumes an oblivious adversary. All updates have polylogarithmic depth; initialization is charged separately. Our density structure answers value queries in O(1)O(1) work and reports a vertex set SS in O(∣S∣+log⁡2n)O(|S|+\log^{2}n) work and O(log⁡n)O(\log n) depth.

Densest Subgraph

The maximum pressure estimates density more accurately than core numbers. The reason is that threshold sets replace the peeling order in the weighted proof of Theorem 3.3.

Lemma C.1. If the graph has an edge and pressures are balanced, then

ρ1+2σ≤max⁡vp(v)≤1+2σ1−2σρ.\frac{\rho}{1+2\sigma}\le\max_v p(v)\le\frac{1+2\sigma}{1-2\sigma}\rho.

Proof. Put P=max⁡vp(v)P=\max_v p(v). Every edge internal to a densest set contributes one unit of load to that set. Balance therefore gives ρ≤(1+2σ)P\rho\le(1+2\sigma)P.

For the upper bound, set w(v)=p(v)σsw(v)=p(v)^{\sigma s} at non-isolated vertices and zero elsewhere. Any nonnegative weights satisfy

∑uv∈Emin⁡{w(u),w(v)}=∫0∞∣E({v:w(v)≥t})∣ dt≤ρ∑vw(v).\sum_{uv\in E}\min\{w(u),w(v)\}=\int_0^\infty|E(\{v:w(v)\ge t\})|\,dt\le\rho\sum_v w(v).

The edge inequality from Theorem 3.3 and balance now give, with both sums over non-isolated vertices,

(1−2σ)∑vp(v)σs+1≤(1+σ/2)ρ∑vp(v)σs.(1-2\sigma)\sum_v p(v)^{\sigma s+1}\le(1+\sigma/2)\rho\sum_v p(v)^{\sigma s}.

The same power-mean calculation as in that theorem yields

P≤1+σ/21−2σρ1/(σs+1)≤1+2σ1−2σρ.P\le\frac{1+\sigma/2}{1-2\sigma}\rho^{1/(\sigma s+1)}\le\frac{1+2\sigma}{1-2\sigma}\rho.

Here PP is attained at a non-isolated vertex, by the lower bound in Theorem 3.3 and the isolated pressure 1/41/4. □

Report (1−2σ)/(1+2σ)(1-2\sigma)/(1+2\sigma) times the maximum rounded pressure, or zero if the graph is edgeless. On a nonempty graph, Lemma C.1 and rounding give

ρ1+ε≤ρ^≤ρ,ρρ^≤(1+2σ)2(1−2σ)(1−σ/64)≤1+8σ≤1+ε.\frac{\rho}{1+\varepsilon}\le\widehat\rho\le\rho,\qquad \frac{\rho}{\widehat\rho}\le\frac{(1+2\sigma)^2}{(1-2\sigma)(1-\sigma/64)}\le1+8\sigma\le1+\varepsilon.

The penultimate inequality is the same parameter check used for coreness in Section 3.2, divided by two.

Maintain counts by index and a pointer to the largest occupied index. A round changes the maximum by at most one; a jump caused by dd inserted edges raises its index by at most MdMd. After isolated vertices reset, scan down past empty indices. The pointer starts at zero, so upward steps pay for all downward steps: total extra work is O(MT)O(MT) plus the number of moves. Value queries take constant time. The O(Mlog⁡n)O(M\log n)-entry array adds O(ε−3log⁡2n)O(\varepsilon^{-3}\log^2 n) space and initialization work; its scan delay is absorbed by Theorem 3.2. Update work remains O(ε−5log⁡n)O(\varepsilon^{-5}\log n) expected amortized, or deterministic sequential time by Appendix § 7.§ 4.

Reporting vertices. On a graph with an edge, put P=max⁡vp(v)P=\max_v p(v). For each index jj, let Sj={v:deg⁡(v)>0, j(v)≥j}S_j=\{v:\deg(v)>0,\ j(v)\ge j\}, and let D=max⁡j:Sj≠∅∣E(Sj)∣/∣Sj∣D=\max_{j:S_j\ne\varnothing}|E(S_j)|/|S_j|. Every nonempty set {v:w(v)≥t}\{v:w(v)\ge t\} with t>0t>0 in the proof of Lemma C.1 is some SjS_j. The upper-bound argument therefore holds with DD in place of ρ\rho, giving

D≥1−2σ1+2σP≥ρ≥ρ1+ε.D\ge\frac{1-2\sigma}{1+2\sigma}P\ge\rho\ge\frac{\rho}{1+\varepsilon}.

A reporting query returns the vertices of a set attaining DD; if the graph is edgeless, it returns the empty set.

To find this set, we maintain at each index jj a dictionary of its non-isolated vertices, their count aja_j, and the number bjb_j of edges uvuv with min⁡{j(u),j(v)}=j\min\{j(u),j(v)\}=j. Then

∣Sj∣=∑i≥jai,∣E(Sj)∣=∑i≥jbi.|S_j|=\sum_{i\ge j}a_i,\qquad|E(S_j)|=\sum_{i\ge j}b_i.

On a reporting query, suffix sums and a reduction identify the largest index maximizing the ratio of these counts over nonempty SjS_j. Listing the vertex dictionaries at or above that index reports the set. There are O(Mlog⁡n)O(M\log n) indices, so the query takes deterministic O(∣Sj∣+ε−3log⁡2n)O(|S_j|+\varepsilon^{-3}\log^{2}n) work and O(log⁡n)O(\log n) depth. Only reporting queries scan all indices.

Edge insertions and deletions update the edge counts, and index changes update the vertex dictionaries and counts. Vertices enter or leave these dictionaries when graph updates change whether they are isolated. During RELABEL, we update the edge counts when collected edges are removed and reinserted. As in the proof of Lemma 4.8, an uncollected edge either has two stationary endpoints or a changing higher endpoint whose lower endpoint stays fixed. Its minimum endpoint index is therefore unchanged, so all changes to bjb_j are covered by edges already processed. Grouping and combining counter changes with the existing parallel primitives preserves the update work and depth bounds. The added dictionaries and counts use O(n+Mlog⁡n)O(n+M\log n) space and initialization work.

For fixed ε\varepsilon, this improves the O(ε−4log⁡2n)O(\varepsilon^{-4}\log^{2}n) amortized bound of Chekuri–Quanrud [11]; their logarithmic-time bound allows an additive error. Pure multiplicative approximations with polylogarithmic worst-case updates are also known [10, 16], and Chekuri et al. [10, Lemma 7.1] support vertex reporting in time proportional to the output size. We have not tried to optimize the additive polylogarithmic overhead of our reporting queries.

Orientation, Matching, and Cliques

Orient each edge from the smaller pair (j(v),id⁡(v))(j(v),\operatorname{id}(v)) to the larger. This is acyclic, and every outgoing edge contributes at least 1/21/2 to its tail. By balance, Theorem 3.3, and Lemma C.1,

d+(v)≤2ℓ(v)≤2(1+2σ)21−2σmin⁡{k(v),ρ}≤(2+ε)min⁡{k(v),ρ}.d^{+}(v)\le2\ell(v)\le\frac{2(1+2\sigma)^2}{1-2\sigma}\min\{k(v),\rho\}\le(2+\varepsilon)\min\{k(v),\rho\}.

In particular, maximum outdegree is at most (2+ε)α(2+\varepsilon)\alpha.

Reporting changes. Each reversal appears among the edges collected by RELABEL (Lemma 4.8). The scan bound and Corollary 4.13 give O(Tlog⁡n)O(T\log n) reversals over TT updates. Remember each touched edge’s old direction and report its net change, keeping flips distinct from real edge updates. Remove obsolete orientation records before adding final ones. Each intermediate graph lies within the old row DAG and inherits its outdegree bound. Reporting costs constant expected work per collected edge.

Maximal matching. The PLDS reduction [24 Section 9] spends constant work per flip and O(α)O(\alpha) work per real update. More precisely, if batch tt has size btb_t, let αt\alpha_t be the maximum of one of the arboricities before and after that batch. The total expected work is

O(Tlog⁡n+∑tbtαt).O\left(T\log n+\sum_t b_t\alpha_t\right).

Space is O(m+n)O(m+n). The resulting O(α+log⁡n)O(\alpha+\log n) bound matches Belloch et al. [7]; the displayed bound also tracks changes in arboricity.

Clique counting. The acyclic-orientation reduction of PLDS [24 Section 10] spends O(αk−2)O(\alpha^{k-2}) work per flip or real update. There are O(Tlog⁡n)O(T\log n) such events, giving O(Tαk−2log⁡n)O(T\alpha^{k-2}\log n) expected work and O(mαk−2+n)O(m\alpha^{k-2}+n) space. In particular, triangles take O(αlog⁡n)O(\alpha\log n) amortized work. This matches the sequential orientation-based bound reported in [14]. The maximum arboricity is needed for this work argument: a total flip bound alone does not bound flips weighted by a changing arboricity.

Forests and Colorings

Forest partition. Store each vertex’s outgoing edges in compact slots 0,…,d+(v)−10,\ldots,d^{+}(v)-1. Edges in slot ii form a forest: they have outdegree at most one, so an undirected cycle would have to be directed, contradicting acyclicity. A deletion fills its hole with the last edge; batches pair holes with surviving suffix entries using prefix sums. This costs constant amortized work per change, giving at most ⌈(2+ε)α⌉\lceil(2+\varepsilon)\alpha\rceil forests with O(log⁡n)O(\log n) expected amortized update work and O(m+n)O(m+n) space. This is the acyclic case of the orientation-to-forests reduction of Henzinger et al. [19].

Implicit coloring. Apply local Cole–Vishkin coloring to each directed forest, as described in [15 Section 1.2]. Each color depends on O(log⁡∗n)O(\log^{*} n) successors. A successor lookup takes constant time. Give sinks color zero and retain three colors for other vertices. Adjacent vertices differ in the coordinate of their edge’s forest, so the vector of colors is proper. Coordinates above a vertex’s outdegree are zero. This gives 2O(α)2^{O(\alpha)} colors and O((1+α)log⁡∗n)O((1+\alpha)\log^{*}n) query work, with the forest partition’s update and space bounds. Independent queries run in O(log⁡n+log⁡∗n)O(\log n+\log^{*}n) depth.

Explicit coloring. Color each fine level jj separately, using disjoint palettes. Put pj=βj/4p_j = \beta^j/4. Balance bounds each same-level degree by 2(1+2σ)pj2(1 + 2\sigma)p_j, so a fixed degree cap ⌈4pj⌉\lceil4p_j\rceil suffices (using rounded pressures changes only constants). Apply Ghaffari–Koo’s (Δ+1)(\Delta+ 1)-coloring algorithm [17 Theorem 1.3]. For oblivious updates, it uses constant expected work per update and polylogarithmic depth. Each instance contains all vertices, with those outside its level isolated. A vertex reports its current level’s color.

Every changed edge is an external update or is collected by Relabel. Deletions precede insertions, preserving each degree cap. There are O(Tlog⁡n)O(T \log n) edge and reporting-level changes, determined independently of the random colors. The coloring theorem therefore gives O(Tlog⁡n)O(T \log n) expected work. For largest occupied index JJ, the palette has ∑j=0J(⌈4pj⌉+1)=O(MpJ)=O(αlog⁡n)\sum_{j=0}^{J}(\lceil4p_j\rceil+ 1) = O(Mp_J) = O(\alpha\log n) colors. The O(log⁡2n)O(\log^2 n) instances store nn vertices each, using O(m+nlog⁡2n)O(m + n\log^2 n) space and O(nlog⁡2n)O(n\log^2 n) initialization work.

References

  1. [1]José Ignacio Alvarez-Hamelin, Luca Dall’Asta, Alain Barrat, and Alessandro Vespignani. 2005. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems, Vol. 18. MIT Press. https://proceedings.neurips.cc/paper_files/paper/2005/file/b19aa25ff58940d974234b48391b9549-Paper.pdf
  2. [2]Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing 8, 6 (2012), 121–164. doi:10.4086/toc.2012.v008a006DOI
  3. [3]Gary D. Bader and Christopher W. V. Hogue. 2003. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4, Article 2 (2003). doi:10.1186/1471-2105-4-2DOI
  4. [4]Nikhil Bansal and Anupam Gupta. 2019. Potential-Function Proofs for Gradient Methods. Theory of Computing 15, 4 (2019), 1–32. doi:10.4086/toc.2019.v015a004DOI
  5. [5]Vladimir Batagelj and Matjaž Zaveršnik. 2003. An O(m) algorithm for cores decomposition of networks. CoRR, cs/DS/0310049.arxiv.org/abs/cs/0310049
  6. [6]Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib – A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 507–509. doi:10.1145/3350755.3400254
  7. [7]Guy E. Blelloch, Andrew Braddy, Laxman Dhulipala, Jeremy T. Fineman, Kishen Gowda, and Chase Hutton. 2026. Faster parallel batch-dynamic algorithms for low out-degree orientation. arXiv:2602.17811v3. To appear in SODA 2027. https://arxiv.org/abs/2602.17811v3
  8. [8]Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2020. Optimal parallel algorithms in the binary-forking model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). arXiv:1903.04650.DOI
  9. [9]Guy E. Blelloch, Phillip B. Gibbons, and Harsha Vardhan Simhadri. 2010. Low depth cache-oblivious algorithms. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).DOI
  10. [10]Chandra Chekuri, Aleksander Björn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn. 2024. Adaptive out-orientations with applications. In ACM–SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 3062–3088. doi:10.1137/1.9781611977912.110DOI
  11. [11]Chandra Chekuri and Kent Quanrud. 2022. (1 − ε)-approximate fully dynamic densest subgraph: Linear space and faster update time. arXiv:2210.02611. https://arxiv.org/abs/2210.02611
  12. [12]Yan S. Couto and Cristina G. Fernandes. 2025. Hardness of dynamic core and truss decompositions. In Workshop on Approximation and Online Algorithms (WAOA). Springer, Cham, Switzerland, 64–80. Full version: arXiv:2509.13584v2, 2026. doi:10.1007/978-3-032-06706-7_5DOI
  13. [13]Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2017. Jullienne: A Framework for Parallel Graph Algorithms Using Work-efficient Bucketing. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 293–304. doi:10.1145/3087556.3087580DOI
  14. [14]Laxman Dhulipala, Quanrud, C. Liu, Julian Shun, and Shangdi Yu. 2021. Parallel batch-dynamic k-clique counting. In Symposium on Algorithmic Principles of Computer Systems (APOCS). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 129–143. Full version: arXiv:2003.13585. doi:10.1137/1.9781611976489.10DOI
  15. [15]Mohsen Ghaffari and Christoph Grunau. 2024. Dynamic O(arboricity) coloring in polylogarithmic worst-case time. In ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery, New York, NY, USA, 1184–1191. Full version: arXiv:2410.19536. doi:10.1145/3618260.3649782DOI
  16. [16]Mohsen Ghaffari and Jaehyun Koo. 2025. Parallel batch-dynamic coreness decomposition with worst-case guarantees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Association for Computing Machinery, New York, NY, USA, 225–239. doi:10.1145/3694906.3743328DOI
  17. [17]Mohsen Ghaffari and Jaehyun Koo. 2026. Dynamic graph coloring: Sequential, parallel, and distributed. arXiv:2512.09218v3. To appear in SODA 2027. https://arxiv.org/abs/2512.09218v3
  18. [18]Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. 2015. A top-down parallel semisort. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 24–34. doi:10.1145/2755573.2755597DOI
  19. [19]Monika Neumann, Stefan Neumann, and Andreas Wiese. 2020. Explicit and implicit dynamic coloring of graphs with bounded arboricity. In International Colloquium on Automata, Languages, and Programming (ICALP). Full version: arXiv:2002.10142.arxiv.org/abs/2002.10142
  20. [20]Scott Huddleston and Kurt Mehlhorn. 1982. A new data structure for representing sorted lists. Acta Informatica 17 (1982), 157–184. https://people.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlhorn-ActaInformatica.pdfDOI
  21. [21]Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H. Eugene Stanley, and Hernán A. Makse. 2010. Identification of influential spreaders in complex networks. Nature Physics 6 (2010), 888–893. doi:10.1038/nphys1746DOI
  22. [22]Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a Social Network or a News Media? In International Conference on World Wide Web (WWW). 591–600. doi:10.1145/1772690.1772751DOI
  23. [23]Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.
  24. [24]Quanquan C. Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2022. Parallel batch-dynamic algorithms for k-core decomposition and related graph problems. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Full version: arXiv:2106.03824v4.
  25. [25]David W. Matula and Leland L. Beck. 1983. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30, 3 (1983), 417–427.DOI
  26. [26]François Rousseau and Michalis Vazirgiannis. 2015. Main core retention on graph-of-words for single-document keyword extraction. In Advances in Information Retrieval (ECIR) (Lecture Notes in Computer Science, Vol. 9022). Springer, 382–393. doi:10.1007/978-3-319-16354-3_42
  27. [27]Stephen B. Seidman. 1983. Network structure and minimum degree. Social Networks 5, 3 (1983), 269–287.DOI
  28. [28]Mauro Sozio and Aristides Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 939–948. doi:10.1145/1835804.1853923DOI
  29. [29]Bintao Sun, T.-H. Hubert Chan, and Mauro Sozio. 2020. Fully dynamic approximate k-core decomposition in hypergraphs. ACM Transactions on Knowledge Discovery from Data 14, 4, Article 39 (2020), 21 pages. doi:10.1145/3385416DOI

Paper details

vlnc:W_9pwt223y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents