WorksComputer Science
Batch-Dynamic Coreness and Applications with Logarithmic Work via Balanced Pressures
Abstract
We give a parallel algorithm that maintains a one-sided -approximation of all core numbers under batches of edge insertions and deletions. For fixed , the expected amortized work is per edge update, and each batch has deterministic polylogarithmic depth. This improves on the previously known -approximation and 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 -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 faster than that implementation in geometric mean and faster than a state-of-the-art heuristic baseline. On three graphs with up to 1.8 billion edges, it is 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 -core is the largest subgraph in which every vertex has degree at least , and the core number (or coreness) is the largest for which belongs to the -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 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 -approximation with amortized update time for constant . Liu et al. [24] introduced the parallel level data structure (PLDS), obtaining the same approximation guarantee with 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 -approximation guarantee. Table 1 compares the bounds. We state all approximation factors in the one-sided convention , where is the true core number and 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 with , it maintains estimates satisfying
after every batch, using expected amortized work per update¹ and deterministic depth per batch. For constant , the space is . 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 approximation.
Table 1. Fully dynamic core-number bounds for constant . A factor means 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 approximation for any fixed . Our approximation approaches this threshold while using logarithmic expected amortized work.
Densest subgraph and other applications. Our data structure also gives a fully dynamic -approximation of the densest-subgraph value with amortized update time and constant query time, for fixed . To our knowledge, this is the first logarithmic update bound for this approximation guarantee, improving the 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 expected amortized work per update and polylogarithmic depth per batch. It also reports the vertices of a -approximate densest subgraph in work and 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 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 at vertex is the sum of the shares it receives from its incident edges. To determine the edge shares, we store a positive number , called the pressure, at each vertex . For an edge with , vertex receives a share of and receives the remaining share . We set later to obtain the approximation guarantee.
Algorithm. We call the pressures balanced if the load lies between and at every non-isolated vertex. Here is the same accuracy parameter as in the -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 to reduce its load. Similarly, a vertex whose load is sufficiently below its pressure divides its pressure by to increase its load. All of the updates within a round use the loads at the start of the round. We choose , so each share changes by only an 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 , a balanced pressure lies between and to within a multiplicative factor. For the lower bound on , let and choose a vertex of minimum pressure in the -core. Each of its at least neighbors in the core has pressure at least , so receives at least half the load of each edge to the core. Its load is therefore at least , and balance gives . Since belongs to this core, , giving the lower bound for .
For the upper bound on , consider the non-isolated vertices in the prefix ending at in a peeling order. Each has at most 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 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 , and thus yields the bound . We obtain the estimated core number by dividing by a suitable factor , so that .
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 , we construct a function of the pressures that is convex in their logarithms. Our potential is the current value of minus its minimum over any pressure assignment, keeping fixed. We show that each moving vertex changes its pressure in a direction that decreases . 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 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 per edge update before the parallel rounds.
The potential starts at zero on the empty graph, and the batches add in total over a sequence of edge updates. Since the potential remains nonnegative, its total decrease over all rounds is at most . For fixed , we show that each round’s expected work is at most times its potential decrease, giving 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 rounds must have increased or decreased its pressure by a factor of . Since pressures remain between a positive constant and , our choice of limits a batch to rounds for fixed .
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 , 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 we write and . The vertex set is fixed and the edge set changes over time, so always denotes the current number of edges. For a vertex , is its set of neighbors and is its degree. We write for the natural logarithm and for the base 2 logarithm.
Cores and core numbers. For an integer , the -core of is the largest subgraph of in which every vertex has degree at least [27]. It is well defined because the union of two subgraphs of minimum degree at least again has minimum degree at least . The core number of a vertex , also called its coreness, is the largest such that belongs to the -core. Equivalently, is the largest such that lies in some subgraph of of minimum degree at least . A vertex without edges has core number 0.
All core numbers can be computed in 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 be the vertices in the order of deletion. Then , and every has at most neighbors among .
Approximate core numbers. An algorithm for approximate core numbers produces an estimate for every vertex . Following Liu et al. [24], the estimate forms a c-approximation, for a number , if
The estimates of our algorithm are never larger than the core numbers. We call estimates a one-sided c-approximation if
We can easily convert one form into the other. Multiplying a one-sided -approximation by gives a -approximation, and dividing a -approximation by gives a one-sided -approximation.
Both conversions keep the ratio between the largest and the smallest value that the guarantee allows for ; this ratio is for a one-sided -approximation and for a -approximation.
Batch-dynamic updates. Initially the graph is empty, and is updated over a sequence of batch updates. Formally, a batch is a pair , where is a set of edges to delete and is a set of edges not in to insert; it changes the edge set from to . 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 amortized work per update if every sequence of batches with updates in total takes 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 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 for every constant .
Parallel primitives. Given a sequence , prefix sums returns , where , and reduce returns . Given a constant-time predicate , filter returns the subsequence of satisfying , preserving its order. Each primitive takes work and depth [9]. Semisort permutes keyed items into contiguous groups of equal keys, with arbitrary order between groups. Assuming constant-time random hashing, we use a version with expected work, space, and deterministic depth. A parallel dictionary stores key-value pairs and supports batched insertions, deletions, and lookups. Our dictionaries use linear space and process operations in expected amortized work, with deterministic depth for lookups and depth for updates. These depth bounds use the fact that dictionary and batch sizes are polynomial in . 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 a positive number , 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 each. When the pressures differ, the endpoint with lower pressure receives the larger share. The load of vertex 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 and a tolerance . Given pressures at all vertices, define the endpoint shares of each edge with by
The load at is . The pressures are balanced if every non-isolated vertex satisfies
and every isolated vertex has pressure .
The accuracy of balanced pressures for estimating the coreness values depends on and . The following theorem chooses these parameters to obtain a -approximation and bounds the work, depth, and space used by the data structure.
Theorem 3.2. Fix and a rational whose numerator and denominator are at most . There is a parallel data structure for an initially edgeless graph on vertices that supports batches of edge insertions and deletions. After every batch, it maintains core-number estimates satisfying
for every vertex .
It maintains these estimates using balanced pressures (Definition 3.1) with and .
After initialization, processing any sequence containing edge updates takes expected work. A batch uses rounds and has depth . These bounds are deterministic. The space usage is words.
Section 3.1 establishes the share properties and chooses the exponent . 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 and . We choose the share exponent 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 .
(S2) A vertex’s share does not decrease when its neighbor’s pressure grows or its own pressure shrinks.
(S3) For any factor , if only one endpoint multiplies or divides its pressure by , both shares change by a factor of at most . If both endpoints do so, both shares change by a factor of at most .
(S1) and (S2) follow from the definition. For (S3), fix one endpoint’s pressure and multiply or divide the other’s by a factor . If the pressures do not change order, (1) shows that the smaller share changes by a factor . 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 , so each share changes by a factor of at most over the whole change. Applying this bound once for each endpoint gives the factor .
Loads and ratios. By (S1), the loads sum to . For a vertex with at least one edge, we call its ratio.
Choosing the exponent. The exponent 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 -vertex star has core number 1, so our accuracy bound requires its pressure to be at most . The balance constraint then requires its load to be as well. With incident edges, its average share must therefore be .
To see how affects this load, suppose the leaves have pressure 1 and the center has pressure . The center’s load is
At these pressures, keeping the load requires , or . Our accuracy proof for general graphs uses the larger choice below. In particular, for the remainder of the description of our analysis and algorithm, we set
Balanced Pressures Approximate Core Numbers
With the parameter choices above, balanced pressures approximate core numbers. The following theorem upper and lower bounds in terms of .
Theorem 3.3. If the pressures are balanced, then every vertex with at least one edge satisfies
Proof. Fix a non-isolated vertex . For the lower bound, consider the -core, which contains by the definition of the core number. Choose a vertex with the smallest pressure in this core, so . Each of the at least neighbors of in the core has pressure at least , so (S1) gives . Balance then gives
and dividing by gives the lower bound of the theorem.
For the upper bound, let consist of and all non-isolated vertices that appear before in the peeling order. By Lemma 2.1, every has and at most later neighbors. Charging each edge to its earlier endpoint shows that the loads in sum to at most , but this bounds only the average load, which still allows individual pressures to be large. We therefore multiply the load of each by before summing. Because the exponent is large, this emphasizes the vertices with the highest pressures, so the resulting bound applies to itself rather than to the average. We first show that
The first inequality follows by applying balance, , to each term.
For the second inequality, we expand each load in the middle sum into the shares receives from its edges, and group the resulting terms by edge. Consider an edge within with endpoint pressures . Its two terms add up to
The inequality holds because the concavity of gives , so the term added to 1 in the second line is at most . Since , the edge’s terms are at most for either endpoint , and we charge them to the endpoint that appears earlier in the peeling order. An edge leaving has a single term, which is at most for its endpoint . That endpoint is the earlier one, because contains all non-isolated vertices preceding . Each is charged for at most edges, one for each later neighbor, which proves the second inequality.
To bound , write
for the sum on the left, so the chain above gives . The largest pressures in dominate , in particular, because . So it suffices to upper bound . The power mean inequality gives
Substituting this bound for the sum of gives
Since , dividing by gives
Using and , we obtain
The last step uses , so , and .
Core-number estimates. Given balanced pressures, we obtain the core-number estimate for a non-isolated vertex by rounding
downward, reducing it by at most a fraction. For an isolated vertex, we set . § 4.1 describes how to perform this rounding.
Theorem 3.3 and the downward rounding of the reported estimate give and, for a non-isolated vertex,
The last inequality holds for . Isolated vertices have .
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 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 times an integer power of a fixed step . We choose in § 4.2. This subsection only uses that is an integer power of . Each vertex therefore has an integer pressure index with . 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 , so its pressure is . The algorithm changes a pressure only by changing its index. A raise increases by one, which multiplies the pressure by , and a lower decreases by one, which divides the pressure by . 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 depend only on the difference of the two pressure indices, because the ratio in Equation (1) is .
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 with index difference , use the share of per edge in two cases: count it as when , and as when . Let 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 , because a vertex can have nearly 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 .
Proof. A share rounded to one equals , so it increases by less than , at most times that share. An ignored share is smaller by another factor of , so all ignored shares together sum to less than .
Rounding. To compute pressures and shares in finite precision, we store rounded values of the powers with and scale them by powers of two as needed. The same table serves both quantities because , and every share is determined by , which is again a power of .
We choose the table’s precision so that each computed share differs from its value after truncation by at most a 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 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
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 , the approximate ratio satisfies
Proof. Combining truncation and rounding gives
If , then , so the truncation error is at most . The computed pressure is at most , giving
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
By (S3), simultaneous moves by the two endpoints change each share by a factor of at most . With our choice, , so this factor is at most .
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:
The first bound holds because and give . The second follows from . For the third, , and gives and .
Balance tests. Each round uses the approximate ratio of every non-isolated vertex 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 unbalanced if or . The algorithm performs another round whenever some vertex is unbalanced, and stops when no vertex is. We choose the tolerance because the error in is less than at such a vertex, so every vertex that is not unbalanced has true ratio within , 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 raises its pressure, and every non-isolated vertex with 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 , they translate into bounds on the true ratio (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 .
The algorithm. A batch consists of a set of edges of the graph, which are deleted, and a set of edges not in the graph, which are inserted. For a vertex , let be the number of edges of at . 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 to delete and to insert. |
| 1: Delete the edges of . |
| 2: for all vertices with in parallel do |
| 3: |
| 4: end for |
| 5: Insert the edges of . |
| 6: Set for every isolated vertex. |
| 7: while some vertex is unbalanced do |
| 8: — Vertices to raise |
| 9: — Vertices to lower |
| 10: for all $v\in O\cup U in parallel do |
| 11: if then |
| 12: — Raise |
| 13: else |
| 14: — Lower |
| 15: end if |
| 16: end for |
| 17: Update and 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 and 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 outside 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 to the larger of its current value and ; this target lies between and . 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 -vertex clique into an empty graph. Without jumps, its vertices would raise their pressures from 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 . A jump raises ’s pressure to a constant fraction of 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 .
(2) For a batch with insertion set , let be the pressure immediately before the jumps and the pressure immediately after them. The jumps increase the sum of pressures by at most and ensure for every vertex . Every vertex that jumps has .
Proof. (1) All pressures start at . Suppose they are all at least before a round. A vertex that could fall below in a lower has . Every neighbor then has pressure at least , so each incident edge gives a share of at least . Since by (4), this share exceeds . 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 , so the pressure is below before the raise. The raise multiplies it by , so the new pressure is below . After a jump, the pressure is at most , so the pressure remains below .
(2) For a vertex with , the jump target satisfies
Hence , and a vertex that jumps had . The lower bound on also holds when , since pressures are positive. Each vertex’s pressure increases by at most . Summing this bound counts each inserted edge once, giving a total increase of at most .
Next, we use the bounded range of pressure values to show that each batch requires at most 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 after the round, and is not unbalanced.
Proof. Let be such a vertex, and let and be its true ratios before and after the round. Since does not move, . Since , (3) first gives . Applying both error bounds then gives
and hence . Only the neighbors’ pressures change, each by a factor of at most , so (S3) bounds the change in each share of , and hence in its load, by a factor of , using (4). The pressure of stays fixed, so its ratio changes by at most the same factor. Therefore,
These bounds give . They follow from and for , using . For example,
Since , Lemma 4.2 gives for the approximate ratio after the round. Hence , so is not unbalanced after the round.
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 , but the rest of the analysis needs statements about the true ratio . Lemma 4.5 translates each test into a bound on the true ratio.
Lemma 4.5. Let be a non-isolated vertex.
(1) If , then . If , then .
(2) The following implications hold.
is not unbalanced,
is not unbalanced .
Proof. We use the error bound (3) of Lemma 4.2. Whenever , it gives .
(1) Suppose . The upper bound in (3) gives . If , then , and if the claim is immediate. Now suppose . If , the claim is immediate, because . Otherwise the lower bound in (3) gives , so . (2) For the first implication, implies , so
and the vertex is not unbalanced. For the second implication, a vertex that is not unbalanced satisfies . Equation (3) then rules out and , so the same error bound applies:
Part (1) shows that a vertex that raises its pressure has and a vertex that lowers its pressure has , 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 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 , , denote a vertex’s pressure, load, and ratio before a round, and let , , denote their values after the round. A vertex that raises its pressure satisfies . A vertex that lowers its pressure satisfies .
Proof. When a vertex raises its pressure by a factor of , each neighbor’s pressure can increase by at most the same factor. The vertex’s shares therefore cannot increase. Thus and . Similarly, when a vertex lowers its pressure, its shares cannot decrease, so and .
We next show that a raise leaves load above pressure and a lower leaves load below pressure. A raise requires and a lower requires , using the approximate ratio before the round. Lemma 4.5(1) therefore gives before a raise and before a lower. By (S3), the load changes by a factor of at most . The pressure changes by a factor of , so the ratio changes by a factor of at most , using (4). Consequently,
The last inequality in each line follows from and for , using .
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 , the pressure range limits how many such rounds are possible.
Lemma 4.7 (Number of rounds). The repair takes rounds per batch.
Proof. Suppose a non-isolated vertex has after 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 , its ratio before that round was even larger. Repeating this argument backward shows that the vertex raised its pressure in all rounds.
The same reasoning shows that a vertex with after 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 , so the ratio before that round was even smaller.
By Lemma 4.3(1), every pressure stays between and . Thus a vertex can raise its pressure in the same direction for at most consecutive rounds. After more than this many rounds, every non-isolated vertex must satisfy . Equation (5) then guarantees that no vertex is unbalanced, so the repair must stop. Substituting from Equation (4) gives 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 , with . Let
so that and . 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
Lemma 4.3(1) gives .
Shares from indices. Expressed in terms of the index difference , the share of edge received by is
This is Equation (1) with . Every additional steps of difference between the indices halves the edge share of the endpoint with higher pressure (Figure 1). Since , the truncation rule of Section 4.1 counts a share as 1 exactly when and as 0 exactly when , where
Rounded powers. In terms of indices, the table of rounded powers from Section 4.1 holds for . It serves both pressures and shares because and , using .

Figure 1. The share of in an edge , as a function of the index difference .
Vertex data. Fix a vertex of index . Its high neighbors have index at least ; the others are low. For each high neighbor , vertex receives a share of at least from edge , so has only high neighbors. The next index levels below 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;
integer counters for the window, described below, and their total contribution to the approximate load.
The two stored sums give , so we can check in constant time whether 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 and the neighbors it visits when moving one index step.

Figure 2. Storage at , where . Low neighbors outside the window remain in buckets and contribute zero to . The thick outline marks the high list and first low bucket, scanned by on a one-step move.
Neighbors to visit. When changes its index by one, it visits its high list and the bucket just below it, at index . Every other neighbor that does not move stays more than steps below , so ’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 , these stationary neighbors remain in their buckets, and the window counters update their aggregate contribution. If a neighbor skipped by also moves, it collects through its own high list, since has a higher old index. The RELABEL operation below rebuilds the collected edge’s records using both endpoints’ new indices. Notice also that whenever lies in a neighbor’s low bucket, that neighbor is high at and is therefore visited. Thus every bucket record that needs a new index is reached.
The window counters. We use the counters to aggregate the shares received by from neighbors in its window. Increasing a neighbor’s index by within the window doubles its contribution to ’s load, so we group levels spaced apart into the same counter. We number the window levels from zero at the bottom and assign a neighbor at offset , where , to counter . The share received by from edge is
The first factor is a power of two common to the whole window, and is common to all levels assigned to counter . Thus counter stores the sum of the integer weights for the neighbors at those levels. To recover the window’s contribution, multiply each counter by the table value for , 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 to position for , and move counter 0 to position 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 work after either shift. For a jump, rebuild the counters from the bucket sizes in the new window, in 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 changes, the other endpoint starts at least steps below ’s old index. Since lowers by at most one, it remains more than steps above that neighbor. The record for stays in that neighbor’s high list and contributes one. At , 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 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 outside 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 . 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 counters in parallel by querying each counter’s window buckets sequentially. This schedule uses scratch space per changing vertex. Remove empty buckets after (iv). Step (v) updates the table of vertices with outside 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 to each vertex that moves one step, or to each vertex that jumps. Loads are measured before the operation. Edge updates cost expected amortized work each. Each round takes deterministic depth, as do the edge updates and jumps of a batch.
Proof. Every scanned neighbor contributes at least , so a changing vertex scans edges. Charge each collected edge to a vertex that collected it. Its records and all resulting tests cost expected amortized work. Updating counters costs per move, or 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 and hence deterministic depth. Rebuilding a counter after a jump requires sequential lookups, each with expected constant work and deterministic depth. Since the counters are rebuilt in parallel, the jump also takes 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 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 costs expected amortized work. Since , this cost is . We therefore bound the sum of over all moves, using the values before each round.
The potential. For the analysis, allow pressures to be any real numbers at least . Each move adds or subtracts from . We construct a function whose derivative with respect to is . A raise increases the logarithmic pressure when this derivative is negative, and a lower decreases it when the derivative is positive. Define
This function has the desired derivative,
Indeed, for the derivatives of with respect to and are and , the negatives of the two shares. The vertex term therefore contributes , and summing the edge derivatives gives .
We next show that is strictly convex in logarithmic pressures. For an edge with endpoint pressures and ,
The first term is linear. The remaining two terms depend only on , and their derivative is . 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 . The vertex terms also dominate the edge terms as pressures grow, so attains a unique minimum. Write for the pressures at this minimum. Our potential is the nonnegative difference
The algorithm does not compute . During a repair, the graph and its minimum are fixed, so the potential decreases by exactly the same amount as .
Lemma 4.10 (Potential decrease). A repair round decreases the potential by
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 to obtain a lower bound on . Substituting (7) gives
For the equality, vertices whose pressures do not change contribute zero. A raise has and still has by Lemma 4.6. A lower has and still has . Thus each move contributes .
We now bound using the pressure and load before the round. For a vertex that raises its pressure, Lemma 4.6 gives . By (S3) and (5), . Since before the raise, we obtain .
For a vertex that lowers its pressure, the same lemma gives . We have and before the lower, so again . Multiplying these bounds by and summing over all moves in the round proves the result. □
Potential increase before repair. When the graph changes, the minimum value subtracted from also changes. To bound the increase in potential, we first establish properties of the minimizing pressures .
At the minimum, an isolated vertex has pressure because its only term in is its own pressure. A non-isolated vertex cannot have pressure at the minimum. Its load would be at least , making the derivative in (7) negative, so raising its pressure would decrease . Its minimizing pressure is therefore strictly above , 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
Lemma 4.11 (Pressures at the minimum). (1) If is balanced, then every vertex satisfies
(2) If on the same vertex set, then for every vertex , and
Proof. (1) For the upper bound, choose a vertex that maximizes . Every neighbor satisfies
The share rule therefore gives no more load under than under . If has an edge, its pressure at the minimum equals its load, so
If is isolated, both pressures are $1/4. Since maximizes the ratio, this proves the upper bound at every vertex.
For the lower bound, choose minimizing . The neighbor pressure ratios now satisfy the reverse inequality, so receives at least as much load under as under . For a non-isolated vertex, this gives
An isolated vertex again has pressure 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 with the smallest ratio , which is then less than 1. The vertex must have an edge in , since an isolated vertex already has the smallest allowed pressure, . By the choice of , each old neighbor's pressure relative to is at least as large under as under . Thus no old edge gives less load, and new edges can only add load. At both minima, 's pressure equals its load, so , 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 .
Starting from balanced pressures lets us bound the potential increase from deletions by . Jumps add at most , 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 plus a constant times the total increase in minimizing pressures, which Lemma 4.11(2) bounds by .
Corollary 4.13 (Work budget). Over any sequence of edge updates starting from the empty graph, the sum of over all moves is . The pressure and load for each move are evaluated before its round.
Proof. Initially the graph is empty and all pressures are , so the potential is zero. Lemma 4.12 bounds the total increase from batches by . Since the potential never becomes negative, the total decrease during repairs is also at most . Lemma 4.10 then bounds the sum of over all moves by . □
Combining this corollary with the cost of a move gives
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 for every vertex.
Work. The expected amortized cost of a move is by Lemma 4.9, since . Corollary 4.13 therefore bounds the total expected amortized work of the moves by
A jumping vertex has : it was balanced or isolated before the batch, deletions only lower loads, and Lemma 4.3(2) gives . Thus the expected amortized work of the jumps is per batch. Each edge update costs 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
per batch deterministically. Each vertex stores numbers, each edge two records, and every nonempty bucket contains a record. Thus the space is plus the table of rounded powers. The primitives use linear scratch space, and jump counters are rebuilt with scratch space per vertex. Initialization zeros the indices and counters in 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 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 , which would be extremely large on our graphs. Instead, DBP uses and the much smaller values and (§ 4). We round a share to one when the index difference exceeds for . 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 outside by one step per round. The implementation instead repairs in two monotone phases. In each round of the raise phase, every vertex with moves to the largest index at which its approximate load is still at least times its pressure, for . It overshoots its balance point and ends with just above . The phase ends when no vertex has . The lower phase then moves vertices with symmetrically until no vertex has . By (S2), raising a vertex cannot decrease the loads of its neighbors. So in the raise phase drops only when itself is raised, and each such move leaves . The phase therefore creates no vertex with . Symmetrically, the lower phase creates no vertex with . 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 work instead of . 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 and livejournal with batches of , on 44 threads. DBP shows four settings with guaranteed error bounds between 2.6 and 3.8. PLDSOpt varies and PLDS . 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 . To make the comparison with prior work easier, DBP reports two-sided estimates, and as in [24] the error of a vertex with is
For a non-isolated vertex, DBP reports . Here and depend only on the parameters and , and Appendix B.1 proves . So every error is at most , the bound listed in Table 2.
| Graph | Vertices | Edges | DBP bound | |
| dblp | 317,080 | 1,049,866 | 113 | 3.35 |
| youtube | 1,138,499 | 2,990,443 | 51 | 3.41 |
| wiki | 1,094,018 | 2,787,967 | 124 | 3.41 |
| stackoverflow | 2,584,164 | 28,183,518 | 198 | 3.46 |
| livejournal | 4,846,609 | 42,851,237 | 372 | 3.50 |
| orkut | 3,072,441 | 117,185,083 | 253 | 3.47 |
| brain | 784,262 | 267,844,669 | 1200 | 3.39 |
| 41,652,230 | 1,202,513,046 | 2488 | 3.71 | |
| friendster | 65,608,366 | 1,806,067,135 | 304 | 3.79 |
Table 2. Graphs, after removing self-loops, duplicate edges, and isolated vertices. The column 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 , after the last batch for Ins and Mix and after the middle batch for Del.
| Graph | Type | Static | PLDS | PLDSOpt | DBP | Sun | PLDS | PLDSOpt | DBP | Sun | PLDS | PLDSOpt | DBP | Sun |
| Time per batch (ms) | Average error | Maximum error | ||||||||||||
| dblp | Ins | 10.4 | 1107 | 49.7 | 11.1 | 15451 | 2.66 | 1.97 | 1.48 | 1.03 | 4.00 | 3.00 | 2.83 | 1.50 |
| Del | 1.79 | 44.8 | 13.1 | 3.46 | 14788 | 1.51 | 2.37 | 1.65 | 1.01 | 2.00 | 6.00 | 2.31 | 2.00 | |
| Mix | 7.85 | 1305 | 68.7 | 14.2 | 17142 | 1.54 | 1.31 | 1.38 | 1.01 | 4.00 | 4.00 | 2.97 | 2.00 | |
| youtube | Ins | 20.1 | 849 | 68.9 | 21.3 | 18990 | 1.71 | 1.43 | 1.18 | 1.01 | 4.00 | 3.00 | 3.03 | 2.00 |
| Del | 16.0 | 69.3 | 29.2 | 12.0 | 15676 | 1.45 | 1.25 | 1.30 | 1.01 | 4.00 | 3.00 | 3.03 | 2.00 | |
| Mix | 25.6 | 600 | 67.9 | 20.8 | 17259 | 1.58 | 1.33 | 1.22 | 1.01 | 4.00 | 3.00 | 3.03 | 2.00 | |
| wiki | Ins | 17.2 | 1232 | 61.5 | 20.6 | 9006 | 1.66 | 1.52 | 1.09 | 1.01 | 4.17 | 3.00 | 2.42 | 1.52 |
| Del | 12.6 | 77.4 | 22.8 | 8.68 | 11970 | 1.54 | 1.45 | 1.12 | 1.00 | 4.00 | 4.00 | 2.42 | 1.38 | |
| Mix | 18.5 | 165 | 39.9 | 20.7 | 8712 | 1.53 | 1.41 | 1.15 | 1.01 | 4.00 | 3.00 | 2.42 | 1.45 | |
| stackoverflow | Ins | 69.9 | 839 | 99.2 | 21.7 | 18729 | 2.54 | 1.97 | 1.15 | 1.07 | 4.17 | 3.00 | 2.75 | 1.52 |
| Del | 65.6 | 284 | 57.0 | 15.4 | 20033 | 1.73 | 1.49 | 1.32 | 1.04 | 4.00 | 4.00 | 2.75 | 1.47 | |
| Mix | 110 | 660 | 116 | 13.7 | 12863 | 2.50 | 1.94 | 1.15 | 1.07 | 4.17 | 3.00 | 2.70 | 1.52 | |
| livejournal | Ins | 132 | 1890 | 147 | 34.0 | 26286 | 2.62 | 1.83 | 1.23 | 1.07 | 4.17 | 3.00 | 3.11 | 1.53 |
| Del | 129 | 427 | 88.4 | 30.5 | 25249 | 1.60 | 1.28 | 1.33 | 1.03 | 4.00 | 4.00 | 3.11 | 2.00 | |
| Mix | 223 | 1369 | 143 | 18.4 | 18687 | 2.60 | 1.82 | 1.23 | 1.07 | 4.17 | 3.00 | 3.11 | 1.53 | |
| orkut | Ins | 247 | 2135 | 178 | 30.3 | 30260 | 3.33 | 2.02 | 1.24 | 1.21 | 4.17 | 3.00 | 2.30 | 1.52 |
| Del | 243 | 987 | 136 | 30.1 | 30291 | 1.70 | 1.24 | 1.25 | 1.10 | 4.00 | 4.00 | 2.38 | 1.40 | |
| Mix | 395 | 1389 | 183 | 17.8 | 19072 | 3.32 | 2.01 | 1.24 | 1.20 | 4.17 | 3.00 | 2.30 | 1.52 | |
| brain | Ins | 333 | 1703 | 166 | 36.4 | – | 3.49 | 1.86 | 1.27 | – | 4.19 | 3.00 | 3.01 | – |
| Del | 302 | – | 213 | 39.0 | – | – | 1.25 | 1.24 | – | – | 4.00 | 3.01 | – | |
| Mix | 441 | – | 340 | 15.7 | – | – | 1.86 | 1.27 | – | – | 3.00 | 3.01 | – | |
| Ins | 1683 | 1874 | 344 | 59.7 | – | 3.16 | 2.27 | 1.25 | – | 4.20 | 3.00 | 3.02 | – | |
| Del | 1686 | – | 323 | 30.6 | – | – | 1.34 | 1.32 | – | – | 4.00 | 2.55 | – | |
| Mix | 2662 | – | 654 | 25.4 | – | – | 2.26 | 1.25 | – | – | 3.00 | 3.02 | – | |
| friendster | Ins | 3108 | 3244* | 269 | 34.5 | – | – | 1.95 | 1.22 | – | – | 3.00 | 3.00 | – |
| Del | 2943 | – | 203 | 33.0 | – | – | 1.27 | 1.31 | – | – | 4.00 | 2.59 | – | |
| Mix | 4884 | – | 273 | 23.5 | – | – | 1.95 | 1.22 | – | – | 3.00 | 3.00 | – |
Table 3. Time per batch in milliseconds, and average and maximum error, for batches of 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 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, , 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 insertions and 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 with suitable parameters, listed as the one-sided in Table 1. PLDS uses and , the setting chosen in [24], with guaranteed error bound . PLDSOpt uses the same parameters with 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 , 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 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 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 faster than PLDS in geometric mean (from to ) and faster than PLDSOpt (from to ). 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 s 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 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 to edges. DBP is faster than PLDSOpt on all nine inputs, by in geometric mean (from to ), 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.
| Graph | Ins PLDS | Ins PLDSOpt | Ins DBP | Del PLDS | Del PLDSOpt | Del DBP | Mix PLDS | Mix PLDSOpt | Mix DBP |
| dblp | 13.0 | 0.41 | 0.90 | 0.18 | 0.18 | 0.25 | 7.32 | 0.24 | 0.43 |
| youtube | 3.01 | 0.21 | 1.11 | 0.09 | 0.09 | 0.54 | 1.03 | 0.12 | 0.60 |
| wiki | 2.95 | 0.11 | 0.82 | 0.05 | 0.05 | 0.05 | 0.07 | 0.02 | 0.68 |
| stackoverflow | 0.97 | 0.15 | 0.30 | 0.10 | 0.09 | 0.17 | 0.32 | 0.08 | 0.19 |
| livejournal | 5.85 | 0.30 | 1.23 | 0.26 | 0.18 | 1.00 | 2.13 | 0.11 | 0.27 |
| orkut | 3.97 | 0.20 | 0.60 | 0.31 | 0.14 | 0.51 | 0.81 | 0.04 | 0.08 |
Table 4. Vertex moves per update for batches of 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 and on livejournal with batches of , as in [24]. PLDS and PLDSOpt vary with . DBP uses , with guaranteed error bounds of at most 2.7, 2.9, 3.5, and 3.8 on these two graphs. Table 3 uses , and the other settings also change , , and .
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, , 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 to updates, and up to 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 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 , where PLDSOpt is 1.4× faster. On dblp, the smallest graph, PLDSOpt is faster with batches of , by up to 3.0×, and on Del also with .
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 to updates, at most 0.3% of the graph, and PLDSOpt with to , 2 to 5%. DBP breaks even only with to , about a fifth of the graph. On stackoverflow Del, it is still faster than Static with batches of , more than a third of the graph. For Mix, DBP is faster than Static even with all updates in one batch.
| Graph | Type | PLDS | PLDSOpt | DBP |
| stackoverflow | Ins | |||
| Del | ||||
| Mix | never | |||
| livejournal | Ins | |||
| Del | ||||
| Mix | never | never |
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 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 . 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 -approximation of all core numbers with expected amortized work per update and polylogarithmic depth per batch. To the best of our knowledge, the best previous guarantees were a factor of using 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 ; we know that at least one factor of 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 . The implementations below give deterministic depth bounds for every batch size while preserving the expected work bounds. All keys below occupy words and admit constant-time comparison and hashing.
Lemma A.1. Semisorting items takes expected work, space, and deterministic 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 or its space exceeds . For a sufficiently large constant , the depth bound and Markov’s inequality for space ensure that each attempt succeeds with probability at least . We reuse the scratch space between attempts, clearing it in linear work and logarithmic depth.
After failed attempts, we finish with deterministic parallel mergesort. Each merge takes linear work and logarithmic depth [9], so the sort takes work, linear space, and 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 . The total expected work is therefore . Both the capped sequence of attempts and the final sort have deterministic depth and use linear space. □
Lemma A.2. A dictionary with keys uses space. A batch of lookups takes expected work and deterministic depth. A batch of updates takes expected amortized work and deterministic depth. Updates use space, and listing all keys takes 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 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 . 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 distinct keys. If , 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 updates enter cell , universality gives
Hence sorting costs expected work, since . To bound the work of merging and filtering, let be the total number of old records in cells touched by the batch. A union bound over the updated keys gives
We merge each touched cell’s array with its updates once, so the merges and subsequent filters take work in total. Since , they use space. Processing the cells in parallel gives deterministic depth, even if every key hashes to the same cell.
If , 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 , so semisorting and applying the updates take 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 depth and uses linear space. To list the records, we scan the cell directory and its arrays in 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 rational numbers obtained by rounding down, for , with relative error at most . A common denominator that is a power of two with bits suffices, since . Each entry can be computed with integer arithmetic. Compute as times the entry for . This gives both pressures and shares: , and because . Thus pressures round down with relative error at most . Multiplying this value by gives the reported estimate. A share has the same relative error. A share for has absolute error at most , hence relative error at most , since it is at least .
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 . All computed contributions have a common power-of-two denominator, so sums can be maintained exactly, without accumulating rounding error. A window has levels, so each neighbor adds to one counter. Each counter is therefore . The scaling factors need bits as well. Hence every stored number uses words and every test is an exact comparison of integers.
The tests and the reported estimates also need in words. The tests compare with and , and the estimate multiplies the rounded pressure by . Both are exact because Theorem 3.2 takes to be a rational number whose numerator and denominator are at most .
The accuracy guarantee and the bounds of the theorem extend to every with . For such an , let be the largest power of two at most . It satisfies the assumption of the theorem, and . Running the data structure with in place of therefore gives estimates that satisfy the guarantee for , 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 . Take , so and . Then , proving
Proof of Lemma 4.12. Let , , and be the graphs before the batch, after deletion, and after insertion. Let and be the pressures before and after the jumps, and write for the term of edge .
Deletion. By Lemma 4.11(2), the minimizing pressures decrease by at most in total. Since edge terms do not increase when pressures rise,
Also by Lemma 4.11(1), so (9) gives for each deleted edge. Therefore
Jumps. Pressures increase by at most in total by Lemma 4.3(2), and edge terms do not increase. Thus jumps add at most to the potential.
Insertion. Let . Lemma 4.11 gives , , and . Hence
Since , insertion adds at most to the potential. By (9), each summand is bounded by the larger endpoint log-ratio. Sum the inequality and use to get
Isolated vertices. Resetting their pressures to lowers their only terms in . In total the potential increases by .
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 search and 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 per record. Rebuilding a jumping vertex’s counters visits at most occupied indices in its new window. The amortized cost per one-step move is . An edge update costs , and a jump costs . As in Section 4.7, at each jumping vertex, so all jumps cost per batch. Corollary 4.13 pays for the ordinary updates exactly as before. The total time for updates is therefore , deterministically, after initialization.
Details for the Experiments
Accuracy for Fixed Exponents
The proof of Theorem 3.3 uses the large exponent only in its last step. The following version holds for every and for every balance tolerance.
Lemma B.1. Let , and suppose that every non-isolated vertex satisfies . Then every such vertex satisfies
Proof. The lower bound is proved as in Theorem 3.3. For the upper bound, repeat that proof with weight in place of . For an edge with pressures and , the weighted contribution is
The charging argument then gives
and the power mean inequality gives as before. □
The implementation. The repair of Section 5.1 stops when every non-isolated vertex has approximate ratio within . Its approximate loads have the cutoffs of Section 4.4 with for a smaller . A share is counted as one when the index difference exceeds and is ignored when the difference is below . Let . A share counted as one is at least and is overcounted by less than , so by a factor less than . Each ignored share is less than , so less than is ignored in total. Each share is rounded to a multiple of , which changes a load by at most . Since every pressure is at least , every non-isolated vertex satisfies the hypothesis of Lemma B.1 with
The lemma gives the interval with and . Reporting bounds the two-sided error by , where is the number of vertex identifiers of the input. For DBP (, , ) 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 for arboricity (the minimum number of forests covering the edges) and for the maximum subgraph density; thus . Table 6 gives bounds for fixed and clique size . In amortized update bounds, 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 problem | Our work | Earlier work |
| Acyclic orientation, | , factor | |
| -approximate densest subgraph | , sequential [11] | |
| Maximal matching | ||
| Exact -clique count | ||
| Partition into forests | ||
| Implicit -coloring | ||
| Explicit -coloring |
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 work and reports a vertex set in work and 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
Proof. Put . Every edge internal to a densest set contributes one unit of load to that set. Balance therefore gives .
For the upper bound, set at non-isolated vertices and zero elsewhere. Any nonnegative weights satisfy
The edge inequality from Theorem 3.3 and balance now give, with both sums over non-isolated vertices,
The same power-mean calculation as in that theorem yields
Here is attained at a non-isolated vertex, by the lower bound in Theorem 3.3 and the isolated pressure . □
Report times the maximum rounded pressure, or zero if the graph is edgeless. On a nonempty graph, Lemma C.1 and rounding give
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 inserted edges raises its index by at most . 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 plus the number of moves. Value queries take constant time. The -entry array adds space and initialization work; its scan delay is absorbed by Theorem 3.2. Update work remains expected amortized, or deterministic sequential time by Appendix § 7.§ 4.
Reporting vertices. On a graph with an edge, put . For each index , let , and let . Every nonempty set with in the proof of Lemma C.1 is some . The upper-bound argument therefore holds with in place of , giving
A reporting query returns the vertices of a set attaining ; if the graph is edgeless, it returns the empty set.
To find this set, we maintain at each index a dictionary of its non-isolated vertices, their count , and the number of edges with . Then
On a reporting query, suffix sums and a reduction identify the largest index maximizing the ratio of these counts over nonempty . Listing the vertex dictionaries at or above that index reports the set. There are indices, so the query takes deterministic work and 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 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 space and initialization work.
For fixed , this improves the 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 to the larger. This is acyclic, and every outgoing edge contributes at least to its tail. By balance, Theorem 3.3, and Lemma C.1,
In particular, maximum outdegree is at most .
Reporting changes. Each reversal appears among the edges collected by RELABEL (Lemma 4.8). The scan bound and Corollary 4.13 give reversals over 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 work per real update. More precisely, if batch has size , let be the maximum of one of the arboricities before and after that batch. The total expected work is
Space is . The resulting 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 work per flip or real update. There are such events, giving expected work and space. In particular, triangles take 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 . Edges in slot 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 forests with expected amortized update work and 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 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 colors and query work, with the forest partition’s update and space bounds. Independent queries run in depth.
Explicit coloring. Color each fine level separately, using disjoint palettes. Put . Balance bounds each same-level degree by , so a fixed degree cap suffices (using rounded pressures changes only constants). Apply Ghaffari–Koo’s -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 edge and reporting-level changes, determined independently of the random colors. The coloring theorem therefore gives expected work. For largest occupied index , the palette has colors. The instances store vertices each, using space and initialization work.
References
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.
- [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]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]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]Stephen B. Seidman. 1983. Network structure and minimum degree. Social Networks 5, 3 (1983), 269–287.DOI
- [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]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


