A Fast Order-Based Approach for Core Maintenance

III. THE PRELIMINARIES

• A k-core is a maximal subgraph whose vertices each have degree at least k, and edge updates change any affected vertex’s core number by at most one.The preliminaries also constrain affected vertices to relevant subcores and state that their induced subgraph is connected.Source: §I · p. 1, §III · p. 3

I. INTRODUCTION

• Core maintenance updates the core numbers of affected vertices after edge changes; a good method should limit update-to-update performance variation and the costs of finding affected vertices and maintaining its index.The affected set is denoted V* and its core numbers are recomputed.Source: §I · p. 1
• Traversal insertion can visit more than 1,000 vertices for a nonsmall proportion of updates, while the order-based algorithm visits at most 100 on each tested graph.The traversal algorithm also has high index-maintenance cost because a core-number change can require updating pcd values across many vertices.Source: §I · pp. 1–2
• Up to 2,083 times faster than traversal insertion, the proposed order-based algorithms maintain core numbers for evolving graphs.The introduction reports extensive performance studies and names OrderInsert and OrderRemoval.Source: §I · p. 2
• The new OrderInsert and OrderRemoval algorithms maintain a k-order—one of the vertex sequences a core-decomposition algorithm can produce—as edges change.The work focuses on edge updates; vertex insertion and removal are simulated by sequences of edge updates.Source: §I · p. 2

II. RELATED WORK

• Prior work identifies the affected set V* as connected within the relevant subcore; the traversal algorithm is state of the art, while other approaches include quadratic and semi-external methods.The cited related-work discussion distinguishes CPU-time optimization from a semi-external algorithm aimed at reducing I/O cost.Source: §II · p. 2

IV. THE TRAVERSAL ALGORITHM

• The traversal method uses mcd(u) to count neighbors with core numbers at least core(u), while pcd(u) excludes same-core neighbors whose mcd equals their core number.Both measures support reasoning about whether a vertex can remain in a target core.Source: §IV · p. 3

A. The Traversal Insertion Algorithm

• Insertion uses DFS from the lower-core endpoint, tracking candidate degrees and evicting vertices that cannot belong to the new (K + 1)-core.Eviction propagation decreases neighbors’ candidate degrees; vertices visited but not evicted form V∗.Source: A. The Traversal Insertion Algorithm · p. 4
• The traversal insertion example visits 1,999 vertices although only u0 needs an update.The DFS evicts the other vertices it visits before identifying V∗ = {u0}.Source: A. The Traversal Insertion Algorithm · p. 4
• More than 10% of vertices in both Patents and Orkut have pure-cores larger than 10,000, contributing to potentially large insertion search spaces.The visited set for an inserted edge is bounded by the pure-cores of its endpoints.Source: A. The Traversal Insertion Algorithm · p. 4

B. The Traversal Removal Algorithm

• Removal repeatedly removes vertices with core(w) = K and cd(w) < K, decreasing neighbors’ candidate degrees until no further vertices qualify.The resulting set V∗ is the set of removed vertices.Source: B. The Traversal Removal Algorithm · p. 4
• Maintaining pcd can dominate traversal insertion and removal, because a core-number decrease may affect pcd values beyond the updated vertices.In the worst case, affected vertices may number O(sum_{v∈nbr(V∗)} deg(v)).Source: B. The Traversal Removal Algorithm · pp. 4–5

V. AN ORDER-BASED ALGORITHM

• The k-order follows CoreDecomp’s removal order and is maintained as edges change, avoiding recomputation of that order during core maintenance.Vertices with lower core numbers precede those with higher core numbers; equal-core vertices follow the applicable CoreDecomp order.Source: §V · p. 5
• The order-based method develops new algorithms for both edge insertions and removals to improve core-maintenance performance.The paper excludes vertex insertion and removal, treating them as sequences of edge updates.Source: §V · p. 5
• For each vertex in O_k, the maintained order requires deg+(v) ≤ k, where deg+(v) counts neighbors appearing after v.This invariant characterizes the k-order and guides its maintenance.Source: §V · p. 5

A. An Algorithm Overview

• For insertion, only vertices in O_K after u can be candidates for V∗, and reachability along edges that follow the k-order narrows the search.Not every reachable vertex is necessarily in V∗.Source: A. An Algorithm Overview · p. 6
• After insertion, vertices in V∗ from O_K move to the beginning of O_{K+1}, with only visited vertices potentially changing positions.The resulting order is guaranteed to be a valid k-order.Source: A. An Algorithm Overview · p. 6
• After removal, vertices in V∗ move from O_K to the end of O_{K−1}, while the original vertices in O_{K−1} remain in place.The resulting order is guaranteed to be a valid k-order.Source: A. An Algorithm Overview · p. 6

B. The Order-Insertion Algorithm

• If deg+(u) ≤ K after insertion, no vertex in OK needs a core-number update; vertices before u are also excluded from V* when deg+(u) > K.The algorithm therefore focuses its candidate search on vertices after u in OK when the threshold is exceeded.Source: B. The Order-Insertion Algorithm · p. 6
• A vertex is a potential candidate when deg+(w) + deg*(w) > K; as the k-order is scanned, Case-2b exclusions can remove candidates and trigger cascading degree updates.At completion, the candidate set VC equals V*, the vertices whose core numbers increase from K to K + 1.Source: B. The Order-Insertion Algorithm · pp. 6–7
• The algorithm rebuilds O′K by appending vertices that cannot join the new (K + 1)-core, then inserts VC at the beginning of OK+1 while preserving their original relative order.Vertices in VC have their core numbers increased by 1.Source: B. The Order-Insertion Algorithm · p. 7
• Insertion work is O(∑v∈V+ deg(v) · log max{|OK|, |OK+1|}), where V+ contains vertices entering Case-1 or Case-2b.The paper defines V+ as the set of vertices that enter those two branches.Source: B. The Order-Insertion Algorithm · p. 8
• For an inserted edge (u, v), V+ is bounded by oc(u) when core(u) < core(v), and by oc(u) ∪ oc(v) when their core numbers are equal.The order-core consists of vertices reachable along paths whose edges follow the k-order.Source: B. The Order-Insertion Algorithm · p. 8
• For 90% of vertices, order-core size is in the hundreds or less, while traversal’s pc and sc are in the order of 10,000 or less.The paper reports that order-core size has much smaller variation than pc and sc.Source: B. The Order-Insertion Algorithm · p. 9
• After inserting 100,000 edges one by one into each graph, the reported ratios for our algorithm were smaller than 4 for all graphs.Source: B. The Order-Insertion Algorithm · p. 9

C. The Order-Removal Algorithm

• For each affected vertex w, OrderRemoval updates deg+ for w and its neighbors, then moves w from OK to the end of OK−1.The algorithm processes affected vertices in the order they were inserted into V* and updates mcd to reflect the core change.Source: C. The Order-Removal Algorithm · p. 9
• Unlike traversal removal, OrderRemoval maintains OK and OK−1 rather than pcd values, which the paper says are costly to maintain.The traversal-removal routine is retained to find V*; k-order maintenance is described as more efficient.Source: C. The Order-Removal Algorithm · p. 9
• Maintaining the k-order takes O(log |OK| · ∑w∈V* degK(w) + |V*| · log |OK−1|) time in the worst case.degK(w) counts neighbors of w whose core number is K and is usually small.Source: C. The Order-Removal Algorithm · p. 9

VI. IMPLEMENTATION

• Small deg+ first consistently performs better than large deg+ first and random deg+ first across all 11 tested graphs.The heuristic appends the vertex with minimum deg+ to Ok−1 during generation and is described as compatible with linear-time generation.Source: §VI · p. 9
• An order-statistics tree supports rank and order queries in O(log |Ok|), using a one-to-one mapping from vertices to tree nodes.Positions can be adjusted after an order change with local rotations; the stated adjustment cost is O(|V+| log |Ok|).Source: §VI · p. 10
• The min-heap B stores (rank(w), w) pairs for vertices with deg*(w) ≠ 0 or deg+(w) > K, returning the next vertex in O(1) time.Heap insertion and arbitrary removal each take O(log |B|) time.Source: §VI · p. 10

• The experiments compare the order-based algorithms with traversal algorithms on 11 large real graphs.The traversal algorithms use the enhancement from, which exploits higher-hop neighborhoods to improve pcd pruning at higher maintenance cost.Source: §VII · p. 10
• The 11 datasets cover temporal, social, citation, web, road, and location-based social graphs.Directed graphs are converted to undirected graphs for testing.Source: §VII · p. 10
• The study evaluates 11 real large graphs, comparing new order-based algorithms with traversal algorithms; implementations use C++ compiled with g++ at -O2 and run on Linux with an Intel i7-4790 and 32 GB memory.Source: §VII · p. 10

• The tests use 100,000 edges per graph, selecting the latest edges for timestamped graphs and randomly sampling edges from the others.The selected edges cover a wide range of k-cores.Source: A. Order-Based vs Traversal · p. 11
• 2,083 times: OrderInsert's speedup over traversal insertion on Pokec, with OrderInsert faster across all tested datasets.Even with higher hop counts, traversal takes 810.00s (h = 6) on Patents and 1.08s (h = 7) on CA, still slower than OrderInsert.Source: A. Order-Based vs Traversal · p. 11
• OrderRemoval outperforms Trav-2 on every tested dataset except CA.CA's average degree is 2.82; OrderRemoval performs especially well on Pokec and Orkut, which have the highest average degrees among the datasets.Source: A. Order-Based vs Traversal · p. 11
• The order-based algorithm uses O(n) space, about five times Trav-2's space in the current implementation.Index creation takes about twice as long, including initial core-number computation; the paper describes index creation as a one-time cost.Source: A. Order-Based vs Traversal · p. 11

• OrderInsert's time grows smoothly while the number of edges increases rapidly in the vertex-sampling tests.The tests use the largest three datasets and measure time to insert 100,000 sampled edges.Source: B. Scalability Testing · p. 11
• In edge-sampling tests, OrderInsert performs well while the number of vertices increases rapidly.The study samples vertices and edges at rates from 20% to 100%, then samples 100,000 edges from each resulting subgraph.Source: B. Scalability Testing · p. 11
• The paper omits scalability tests for OrderRemoval because it relies only on V* and its neighbors.The authors state that scalability is therefore not an issue for OrderRemoval.Source: B. Scalability Testing · p. 11

• OrderInsert's performance remains well bounded across 100 groups of 100,000 reinserted edges on Patents, Orkut, and LiveJournal.The study first randomly samples 10,000,000 edges and partitions them into groups.Source: C. Stability Testing · p. 12
• Orkut's group-level results fluctuate frequently as the number of vertices needing core-number updates varies across groups.The study reports this variation in the number of updated vertices alongside the timing results.Source: C. Stability Testing · p. 12
• With random edge removals after insertions at probabilities 0.1 and 0.2, the measured total-time results are similar.The measurement includes the time spent removing edges.Source: C. Stability Testing · p. 12

VIII. CONCLUSIONS

• The study aims to reduce the computational cost of computing k-cores as graph edges are dynamically inserted or removed.Source: §VIII · p. 12
• Across 11 large real graphs, OrderInsert outperforms the traversal insertion algorithm by up to 3 orders of magnitude.The reported performance studies evaluate the proposed approach on those graphs.Source: §VIII · p. 12
• The algorithm maintains a k-order that helps identify vertices needing core-number updates and incurs small overhead when edges are inserted or removed.Source: §VIII · p. 12

APPENDIX PROOF OF THEOREMS AND LEMMAS

• Lemma 5.1’s removal order ensures each processed vertex has remaining degree below k + 1.Source: APPENDIX PROOF OF THEOREMS AND LEMMAS · p. 13
• The Lemma 5.2 and 5.3 sketches use degree bounds to show vertices in OK do not enter the (K + 1)-core after the stated insertion conditions.Source: APPENDIX PROOF OF THEOREMS AND LEMMAS · p. 13
• Algorithm 2’s complexity is O((sum over v in V+ of deg(v)) · log max{|OK|, |OK+1|}).Source: APPENDIX PROOF OF THEOREMS AND LEMMAS · p. 13
• For Theorem 5.4, identifying V* takes O(sum over w in V* of deg(w)) time, with additional costs for maintaining OK and OK−1.The maintenance bound includes terms involving degK(w) and logarithms of the order-set sizes.Source: APPENDIX PROOF OF THEOREMS AND LEMMAS · p. 13

APPENDIX INDEX CREATION TIME COMPARISON

• Table III compares index-creation time in seconds.Source: Table III · p. 13