Pith. sign in

REVIEW 3 major objections 4 minor 90 references

Parallel $k$-Core Decomposition: Theory and Practice

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A simple parallel framework computes exact $k$-core decompositions in $O(n+m)$ work, and its tuned implementation is the fastest among four state-of-the-art parallel codes on 23 of 25 test graphs.

desk verdict Strong practical parallel k-core paper with a clean work-efficient framework, but the sampling correctness proof has a real gap around mid-round crossings. read the letter →

arxiv 2502.08042 v2 pith:RVITWUBK submitted 2025-02-12 cs.DS cs.DC

Youzhe Liu , Xiaojun Dong , Yan Gu , Yihan Sun This is my paper · ORCID
classification cs.DScs.DC MSC 05C8568W1068R10
keywords k-coredecompositionparallelalgorithmswork-efficiencygraphpeelingsamplingschemegranularitycontrolhierarchicalbucketing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that work-efficient parallel $k$-core decomposition can be achieved by a simple frontier-peeling framework, without the heavy bucketing machinery previously thought necessary. The key observation is that maintaining an active set and spending time proportional to that set in each round sums to $O(n+m)$ over all rounds, because every vertex appears in as many active sets as its coreness value. To make the framework fast in practice, the paper adds three mechanisms: a sampling scheme that reduces atomic-operation contention on high-degree vertices, vertical granularity control that processes small local queues to hide scheduling overhead on low-degree vertices, and a hierarchical bucketing structure for graphs with large coreness values. If these claims hold, the result is a single parallel algorithm that avoids the worst-case slowdowns each existing baseline suffers on some graph type.

What carries the argument

The load-bearing identity is the active-set summation $\sum_{i=0}^{k_{\max}} |A_i| = \sum_{v\in V}(1+\kappa(v)) \le n+m$, which bounds the cost of re-scanning the active set once per round. Algorithm 1 extracts a frontier $F$ of vertices whose induced degree equals $k$, assigns them coreness $k$, peels them by decrementing neighbors' induced degrees, and then packs the active set down to vertices with induced degree above $k$. The three practical techniques are implementations of these steps: sampling replaces atomic decrements on high-degree vertices with probabilistic sample counts; vertical granularity control runs a bounded local search inside each subround to merge small tasks; and the hierarchical bucketing structure organizes vertices by exponentially growing degree ranges so frontier extraction costs $O(\log d(v))$ per vertex instead of $O(d(v)/b+b)$.

What would settle it

Construct a graph with a high-degree vertex whose induced degree drops below $k$ in the middle of a subround, run Algorithm 4 with the stated sample-rate parameters, and inspect the final coreness values; a single vertex peeled one round late (coreness overestimated by 1) would disprove the whp correctness claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1: in the frontier-based peeling framework of Algorithm 1, if peeling a frontier $F$ costs $O(|F| + \sum_{v\in F} d(v))$ and each round's initial-frontier extraction and active-set refinement cost $O(|A|)$, then the total work is $O(n+m)$. The proof rests on the identity $\sum_{i=0}^{k_{\max}} |A_i| = \sum_{v\in V} (1+\kappa(v)) \le n+m$, since coreness never exceeds degree. The paper then shows that an online peeling version with a sampling scheme for high-degree vertices, a local-search vertical granularity control for low-degree vertices, and a hierarchical bucketing structure preserves this work bound while improving parallelism and burdened span. On a 96-core machine the implementation is the fastest on 23 of 25 graphs, with speedups up to $315\times$ over ParK, $33.4\times$ over PKC, and $52.5\times$ over Julienne, and self-relative speedups of roughly $7.5$--$86\times$.

Load-bearing premise

The sampling proof assumes the only dangerous event is a vertex whose true remaining degree is already below $k$ when round $k$ begins; a vertex that crosses below $k$ during the round is not explicitly bounded in the analysis.

Editorial extensions

If this is right

  • The simplified Julienne implementation is work-efficient, and the existing $O(m+k_{\max} n)$ online algorithms become work-efficient once they maintain an active set.
  • Sampling lowers the contention on a high-degree vertex from $O(d(v))$ to $O(\kappa(v)+\log n)$ while keeping the algorithm exact with high probability.
  • Vertical granularity control reduces the number of subrounds by 5--40$\times$ on tested graphs and cuts the burdened span by up to about 147$\times$ relative to Julienne.
  • The hierarchical bucketing structure reduces per-vertex maintenance cost from $O(d(v)/b+b)$ to $O(\log d(v))$, and stays competitive with a single bucket on sparse graphs.
  • The full implementation is the fastest parallel code on 23 of 25 graphs, always beating the best sequential time by 7.3--84$\times$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The active-set summation argument is generic enough that the same framework should transfer to other peeling-based computations such as degeneracy ordering, nucleus decomposition, or D-core decomposition, where a round-based frontier loop scans a shrinking set.
  • A sharper correctness analysis would explicitly bound the mid-round crossing case, where a sampled vertex falls below $k$ after the round-start validation but before the active-set refinement; this is the natural stress test for the high-probability guarantee.
  • The burdened-span reduction suggests a reusable design principle: any synchronous peeling implementation with many subrounds should benefit from bounded local queues that merge small tasks, even outside $k$-core decomposition.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes a parallel k-core decomposition algorithm built on a simple frontier-based framework (Alg. 1). It claims an O(n+m)-work bound under natural assumptions (Thm. 3.1), and then introduces three practical optimizations: a sampling scheme for high-degree vertices (Sec. 4.1), vertical granularity control (VGC) to reduce subround synchronization overhead (Sec. 4.2), and a hierarchical bucketing structure (HBS) (Sec. 5). The experimental section compares the implementation against Julienne, ParK, and PKC on 25 real-world and synthetic graphs, reporting that it is fastest on 23 of 25 graphs and giving speedups of up to 315x over ParK.

Significance. If the theoretical claims are correct, the paper is a valuable contribution: Thm. 3.1 is a clean formalization of why simple active-set maintenance yields work efficiency, and the three optimizations address real bottlenecks that the experiments document carefully. The evaluation is extensive, including ablations for each technique, self-relative speedups, burdened-span measurements, and a heatmap over all eight combinations of the techniques. The code is released. However, the formal correctness and work-efficiency of the sampling-enabled algorithm are not established as written: the correctness proof covers only one failure mode, and the cost analysis of repeated resampling is incomplete. These points are load-bearing because sampling is one of the three main techniques and the paper's central claim is work efficiency.

major comments (3)
  1. [Sec. 4.1.3, Thm. 4.2; Alg. 4 lines 5-11] Theorem 4.2 only analyzes vertices whose true induced degree is already below k at the start of round k. A vertex can instead cross from d* >= k to d* <= k during the round while it is in sample mode. If its sample counter has not reached mu, the vertex is not placed in C (Alg. 5, line 7), and the stale dtilde[v] keeps it in A at line 11. In round k+1, Validate may fail and Resample adds the vertex to F, after which coreness k+1 is assigned, even though the correct coreness is k. The probability of this mid-round event is not bounded anywhere in the proof. The Las Vegas restart discussion in Sec. 4.1.4 is informal and is not part of Alg. 4; it does not specify a check that runs before an incorrect coreness is written. A star graph gives a concrete instance: the center remains in sample mode while the leaves are peeled in round k=1, and if fewer than mu successful samples are collected, the center is subsequently assigned coreness 2 instead of 1. The analysis needs to validate/resample after the active set is refined, or else explicitly bound the mid-round crossing probability in the whp argument.
  2. [Sec. 4.1.5; Alg. 5, Resample lines 19-21] The claim that sampling preserves the O(n+m) work bound is not justified. Resample(v,k,F) scans the full neighbor list N(v) each time it is called, because it must count active neighbors. A vertex can be resampled many times: whenever cnt reaches mu, SetSampler re-enters sample mode as long as r*dtilde[v] > k and dtilde[v] > threshold, and each resampling reduces dtilde[v] only by a constant factor r. For a vertex with original degree d(v), this can happen Theta(log d(v)) times before dtilde[v] falls to the constant threshold, giving Theta(d(v) log d(v)) work for that vertex. The sentence 'the total cost to recount the true induced degree of v is O(d(v))' is therefore false without an additional amortized argument, for example, resampling in time proportional to the current active degree or maintaining a compact list of active neighbors. As written, Theorem 3.1 does not apply to Algorithm 4 because the cost of Resample is not charged in the theorem's Peel assumption.
  3. [Sec. 4.1.1, Alg. 4 line 5] The validation loop is written as 'parallel_foreach v in V : v is in sample mode', which as written appears to scan all of V in every round and would cost O(n) per round, hence O(kmax * n) total. Section 4.1.5 asserts that the validation cost is proportional to the number of vertices in sample mode and is therefore bounded by the active-set size, but no data structure is described that enumerates sample-mode vertices in that time. Please state explicitly that sample-mode vertices are maintained in a separate set (for example, the parallel hash bag) and that SetSampler and Resample update that set; otherwise the O(n+m) work bound for Algorithm 4 does not follow from the pseudocode as given.
minor comments (4)
  1. [Sec. 4.1.1] There is a typo: 'Another case to ressample v' should be 'resample v'.
  2. [Alg. 5, line 6] The line 'atomic_inc(sigma[u].cnt) with probability sigma[u].rate' is ambiguous: it should specify whether the random draw happens before the atomic increment and whether concurrent increments that fail the draw simply do nothing. A brief implementation note would remove the ambiguity.
  3. [Sec. 4.2] The statement that VGC 'does not change work-efficiency' should include a short argument that a vertex cannot be enqueued twice in the local queue or in both a local queue and Fnext under concurrent decrements; the current text asserts uniqueness without proving it.
  4. [Sec. 4.1.5] The contention bound 'O(kappa[v] + log n)' should clarify that the threshold in SetSampler is a fixed implementation constant and should be included in the asymptotic statement (or stated as a tunable parameter whose value does not affect the asymptotic bound).

Circularity Check

0 steps flagged · score 1.0 of 10

No load-bearing circularity: central work-efficiency proof is self-contained; self-citations are minor, with a non-circular correctness-gap caveat in the sampling theorem.

full rationale

The paper's central theoretical claim, Theorem 3.1, is derived from a direct accounting: each vertex appears in exactly one frontier, the peel cost is assumed to be proportional to the frontier's total degree, and the active-set costs telescope via sum_v (1 + coreness(v)) <= sum_v (1 + degree(v)) = O(n + m). No parameter is fitted to a predicted quantity, and the exact empirical choices (r = 0.1, mu = Theta(log n), VGC queue size 128, HBS threshold 16) do not carry the O(n + m) claim. The sampling correctness proof in Theorem 4.2 is a standard Chernoff argument: the sample rate is chosen so that, if the true induced degree falls below k at the start of a round, the accumulated sample count violates Validate whp. The threshold in Validate is a design choice derived from the rate, not an input-equivalent conclusion. The paper does contain self-citations: VGC is attributed to the same group's earlier work [24, 72], and parallel hash bags to [25, 72], but these techniques are empirically evaluated against the paper's own plain baseline and the theoretical work-efficiency/correctness results do not reduce to those citations. No uniqueness theorem or ansatz is imported from the authors' prior work to force the algorithmic choice. One non-circular gap should be noted: Section 4.1.3 restricts the dangerous event to a sampled vertex whose true induced degree is already below k 'at the beginning of round k', and the proof does not explicitly bound vertices that cross below k mid-round, are not resampled in that round, and could then be peeled at round k+1. This is a correctness gap in the whp guarantee, not a circular dependency, and it does not raise the circularity score.

Assumptions & free parameters 6 free parameters · 7 assumptions · 0 invented entities

The central work-efficiency claim rests on standard parallel primitives and the degree-based bound on coreness. The sampling and VGC performance claims rest on several empirical parameters whose values are chosen by hand, plus a correctness argument that has a gap. No new physical entities are introduced.

free parameters (6)
  • r (resample factor) = 0.10
    When a sampled vertex's estimated induced degree drops to r times its value at last resample, the sampler is reset. Chosen by hand in Section 4.1.2.
  • mu (target sample count) = 4(c+2) ln n with c > 2
    Theoretical parameter controlling the sample count and error probability; set as Theta(log n) in Alg. 5.
  • VGC local queue size = 128
    Local search processes up to this many vertices sequentially before returning to the parallel frontier; set empirically in Section 4.2.
  • HBS activation threshold theta = 16
    Average-degree threshold above which the hierarchical bucket structure is used; switching happens when a theta-core is reached (Section 5.3).
  • First single-key buckets in HBS = 8
    The first eight buckets hold single degree values before exponential ranges begin; implementation choice in Section 5.2.
  • Sampling mode degree threshold = not specified
    SetSampler enters sample mode only when d_tilde[v] exceeds this named constant; the value is not stated in the paper.
assumptions (7)
  • standard math Chernoff bound for sums of independent Bernoulli trials
    Used in Lemma 4.1 to bound underestimation of induced degree from samples.
  • domain assumption Work-span model with binary fork-join and randomized work stealing
    Defined in Section 2; all complexity claims are stated in this model.
  • domain assumption Atomic increment/decrement and bag insertion have constant work
    Used throughout the online peeling analysis; Section 2 acknowledges contention costs separately.
  • domain assumption Burdened span with omega = 15,000 captures scheduling overhead
    Borrowed from Cilkview and used in Section 4.2 to argue VGC improves parallelism.
  • standard math Coreness of a vertex is at most its original degree
    Used in the proof of Theorem 3.1 to bound the sum of active set sizes.
  • standard math Parallel hash bag supports expected O(1) insertion and O(t) extraction
    Assumed for HBS buckets and frontier maintenance in Sections 2 and 5.
  • domain assumption A vertex whose induced degree reaches k during a round will be inserted into exactly one frontier or local queue
    Relied on by the online peeling algorithm and VGC to avoid duplicates and ensure each vertex is peeled once.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parallel $k$-Core Decomposition: Theory and Practice." pith.science (2026). https://pith.science/paper/RVITWUBK

@misc{pith2026250208042,
  author       = {Pith},
  title        = {Pith review of: Parallel $k$-Core Decomposition: Theory and Practice},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RVITWUBK}},
  note         = {Machine review of arXiv:2502.08042}
}
abstract

This paper proposes efficient solutions for $k$-core decomposition with high parallelism. The problem of $k$-core decomposition is fundamental in graph analysis and has applications across various domains. However, existing algorithms face significant challenges in achieving work-efficiency in theory and/or high parallelism in practice, and suffer from various performance bottlenecks. We present a simple, work-efficient parallel framework for $k$-core decomposition that is easy to implement and adaptable to various strategies for improving work-efficiency. We introduce two techniques to enhance parallelism: a sampling scheme to reduce contention on high-degree vertices, and vertical granularity control (VGC) to mitigate scheduling overhead for low-degree vertices. Furthermore, we design a hierarchical bucket structure to optimize performance for graphs with high coreness values. We evaluate our algorithm on a diverse set of real-world and synthetic graphs. Compared to state-of-the-art parallel algorithms, including ParK, PKC, and Julienne, our approach demonstrates superior performance on 23 out of 25 graphs when tested on a 96-core machine. Our algorithm shows speedups of up to 315$\times$ over ParK, 33.4$\times$ over PKC, and 52.5$\times$ over Julienne.

Figures

Figures reproduced from arXiv: 2502.08042 by the authors.

Figure 1
Figure 1. ). The 𝑘-core decomposition of a graph𝐺 identifies a sequence of non-empty subgraphs 𝐺0,𝐺1, . . . ,𝐺𝑘max for all possible 𝑘 values, where 𝐺𝑖 is the 𝑖-core of 𝐺. The coreness of a vertex, denoted as 𝜅[𝑣], is the maximum value of 𝑘 such that 𝑣 is in 𝐺𝑘 . The coreness of a graph, denoted as 𝑘max, is the maximum coreness among all vertices. The output of the 𝑘-core decomposition is the coreness for each vertex, which ca… view at source ↗
Figure 2
Figure 2. Speedup of ParK [18], PKC [38], Julienne [19, 20], and our algorithm, over to the best sequential time (our sequential time or the BZ algorithm time [10]) on 14 representative graphs. Higher is better. Full results are in Tab. 2. Numbers below 2 are given on the bars, meaning the parallel code is no more than 2× faster than a sequential one. structure (or equivalently, using a single bucket) as in our proposed frame… view at source ↗
Figure 3
Figure 3. The peeling process on a grid with and without using VGC. In this example, the queue size is 4. Note that the execution of VCG is not deterministic, and (b) shows a possible execution. contention to handle a specific vertex 𝑣 is 𝑂(𝜅[𝑣] + log𝑛). For high￾degree vertices, this is much smaller than 𝑂(𝑑 (𝑣)), which is the number of concurrent updates to ˜𝑑 [𝑣] without sampling. 4.2 Vertical Granularity Control Our secon… view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: The execution of the hierarchical bucketing structure for [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Relative running time of ParK [18], PKC [38] and Julienne [19, 20] normalized to our running time (red dotted line) on all graphs. Lower is better. The bars are truncated at 4 for better visualization. The text on the bars are actual relative running time. We first stu…
Figure 6
Figure 6. Figure 6: Speedup of VGC and sampling over a plain implementation. Higher is better. [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 8
Figure 8. Figure 8: Relative running time of different bucketing strategies, [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Burdened span [37] speedup of our algorithm (with and without VGC) over Julienne [19, 20] (red dotted line, always= 1) on all graphs. Higher is better. The bars are truncated at 18 for better visualization. The text on the bars are actual burdened span speedup. 1 2 4 1…
Figure 10
Figure 10. Figure 10: Self-relative speedup on dense graphs and sparse graphs. [PITH_FULL_IMAGE:figures/full_fig_p013_10.png]
Figure 12
Figure 12. Figure 12: Comparison of our adapted subgraph finding algorithm [PITH_FULL_IMAGE:figures/full_fig_p016_12.png]
Figure 13
Figure 13. Figure 13: Heatmap of our 8 versions of algorithms (with and without [PITH_FULL_IMAGE:figures/full_fig_p016_13.png]
Figure 11
Figure 11. Figure 11: Running time comparison w/ and w/o sampling. [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 14
Figure 14. Figure 14: Burdened span [37] speedup of our algorithm (with and without VGC) over Julienne [19, 20] (green dotted line, always= 1) on all graphs. Higher is better. The bars are truncated at 18 for better visualization. The text on the bars are actual burdened span speedup. When…
Figure 15
Figure 15. Figure 15: Running time speedup of our algorithm (with and without VGC) over [PITH_FULL_IMAGE:figures/full_fig_p018_15.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

90 extracted references · 64 canonical work pages

  1. [1]

    OpenCilk

    2020. OpenCilk. https://www.opencilk.org/

    2020

  2. [2]

    Umut A Acar, Naama Ben-David, and Mike Rainey. 2017. Contention in Struc- tured Concurrency: Provably Efficient Dynamic Non-Zero Indicators for Nested Parallelism. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 75–88

    2017

  3. [3]

    Akhlaque Ahmad, Lyuheng Yuan, Da Yan, Guimu Guo, Jieyang Chen, and Chengcui Zhang. 2023. Accelerating k-Core Decomposition by a GPU. In 2023 IEEE 39th International Conference on Data Engineering (ICDE) . IEEE, 1818–1831

    2023

  4. [4]

    Hidayet Aksu, Mustafa Canim, Yuan-Chi Chang, Ibrahim Korpeoglu, and Özgür Ulusoy. 2014. Distributed 𝑘-Core View Materialization and Maintenance for Large Dynamic Graphs. IEEE Transactions on Knowledge and Data Engineering 26, 10 (2014), 2439–2452

    2014

  5. [5]

    Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, Michael Mitzenmacher, John D

    Dan A. Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, Michael Mitzenmacher, John D. Owens, and Nina Amenta. 2009. Real-time parallel hashing on the GPU. ACM Trans. Graph. (2009)

    2009

  6. [6]

    Sabeur Aridhi, Martin Brugnara, Alberto Montresor, and Yannis Velegrakis. 2016. Distributed k-core decomposition and maintenance in large dynamic graphs. In Proceedings of the 10th ACM international conference on distributed and event-based systems. 161–168

    2016

  7. [7]

    Nimar S Arora, Robert D Blumofe, and C Greg Plaxton. 2001. Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems (TOCS) 34, 2 (2001), 115–144

    2001

  8. [8]

    Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: membership, growth, and evolution. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 44–54

    2006

Show all 90 references
  1. [9]

    Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509–512

    1999

  2. [10]

    Vladimir Batagelj and Matjaz Zaversnik. 2003. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049 (2003)

    2003 arXiv

  3. [11]

    Blelloch, Jeremy T

    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). 89–102

    2020

  4. [12]

    Blumofe and Charles E

    Robert D. Blumofe and Charles E. Leiserson. 1998. Space-Efficient Scheduling of Multithreaded Computations. SIAM J. on Computing 27, 1 (1998)

    1998

  5. [13]

    Marián Boguná, Romualdo Pastor-Satorras, Albert Dí az Guilera, and Alex Arenas

  6. [14]

    Kate Burleson-Lesser, Flaviano Morone, Maria S Tomassone, and Hernán A Makse

  7. [15]

    James Cheng, Yiping Ke, Shumo Chu, and M Tamer Özsu. 2011. Efficient core decomposition in massive networks. In IEEE International Conference on Data Engineering (ICDE). IEEE, 51–62

    2011

  8. [16]

    Yizong Cheng, Chen Lu, and Nan Wang. 2013. Local k-core clustering for gene networks. In 2013 IEEE International Conference on Bioinformatics and Biomedicine. IEEE, 9–15

    2013

  9. [17]

    Deming Chu, Fan Zhang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2022. Hierarchical core decomposition in parallel: From construction to subgraph search. In 2022 IEEE 38th International Conference on Data Engineering (ICDE) . IEEE, 1138–1151

    2022

  10. [18]

    Naga Shailaja Dasari, Ranjan Desh, and Mohammad Zubair. 2014. ParK: An efficient algorithm for k-core decomposition on multicore processors. In 2014 IEEE International Conference on Big Data (Big Data) . IEEE, 9–16

    2014

  11. [19]

    Blelloch, and Julian Shun

    Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2017. Julienne: A Frame- work for Parallel Graph Algorithms using Work-efficient Bucketing. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) . 293–304

    2017

  12. [20]

    Blelloch, and Julian Shun

    Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2021. Theoretically efficient parallel graph algorithms can be fast and scalable. ACM Transactions on Parallel Computing (TOPC) 8, 1 (2021), 1–70

    2021

  13. [21]

    Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. 2022. Differential privacy from locally adjustable graph al- gorithms: k-core decomposition, low out-degree ordering, and densest subgraphs. In IEEE Symposium on Foundations of Com...

    2022

  14. [22]

    Xiangyun Ding, Xiaojun Dong, Yan Gu, Yihan Sun, and Youzhe Liu. 2023. Efficient Parallel Output-Sensitive Edit Distance. In European Symposium on Algorithms (ESA)

    2023

  15. [23]

    Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun. 2024. Parallel Integer Sort: Theory and Practice. InACM Symposium on Principles and Practice of Parallel Programming (PPOPP)

    2024

  16. [24]

    Xiaojun Dong, Yan Gu, Yihan Sun, and Letong Wang. 2024. Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    2024

  17. [25]

    Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang. 2021. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) . 184–197

    2021

  18. [26]

    Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun. 2023. High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    2023

  19. [27]

    Arnold I Emerson, Simeon Andrews, Ikhlak Ahmed, Thasni KA Azis, and Joel A Malek. 2015. K-core decomposition of a protein domain co-occurrence network reveals lower cancer mutation rates for interior cores. Journal of clinical bioin- formatics 5 (2015), 1–11

    2015

  20. [28]

    Hossein Esfandiari, Silvio Lattanzi, and Vahab Mirrokni. 2018. Parallel and streaming algorithms for k-core decomposition. In International Conference on Machine Learning (ICML). PMLR, 1397–1406

    2018

  21. [29]

    Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and Santiago Marco. 2015. Reser- voir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sensors and Actuators B: Chemical 215 (2015), 618–629

    2015

  22. [30]

    Kasimir Gabert, Ali Pinar, and Ümit V Çatalyürek. 2022. Batch dynamic algorithm to find k-core hierarchies. In Proceedings of the 5th ACM SIGMOD Joint Interna- tional Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). 1–10

    2022

  23. [31]

    Javier García-Algarra, Juan Manuel Pastor, Jos é María Iriondo, and Javier Galeano

  24. [32]

    Christos Giatsidis, Dimitrios M Thilikos, and Michalis Vazirgiannis. 2011. Evalu- ating cooperation in communities with the k-core structure. In 2011 International conference on advances in social networks analysis and mining . IEEE, 87–93

    2011

  25. [33]

    Christos Giatsidis, Dimitrios M Thilikos, and Michalis Vazirgiannis. 2013. D-cores: measuring collaboration of directed graphs based on degeneracy. Knowledge and information systems 35, 2 (2013), 311–343

    2013

  26. [34]

    Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin

  27. [35]

    Joseph E Gonzalez, Reynold S Xin, Ankur Dave, Daniel Crankshaw, Michael J Franklin, and Ion Stoica. 2014. GraphX: Graph processing in a distributed dataflow framework. In USENIX conference on Operating Systems Design and Implementa- tion (OSDI). 599–613

    2014

  28. [36]

    Blelloch

    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

    2015

  29. [37]

    Yuxiong He, Charles E Leiserson, and William M Leiserson. 2010. The Cilkview scalability analyzer. In ACM Symposium on Parallelism in Algorithms and Archi- tectures (SPAA). 145–156

    2010

  30. [38]

    Humayun Kabir and Kamesh Madduri. 2017. Parallel k-core decomposition on multicore platforms. In 2017 IEEE international parallel and distributed processing symposium workshops (IPDPSW). IEEE, 1482–1491

    2017

  31. [39]

    Wissam Khaouid, Marina Barsky, Venkatesh Srinivasan, and Alex Thomo. 2015. K-core decomposition of large networks on a single PC. Proceedings of the VLDB Endowment 9, 1 (2015), 13–23

    2015

  32. [40]

    Valerie King, Alex Thomo, and Quinton Yong. 2022. Computing (1+ epsilon)- approximate degeneracy in sublinear time.arXiv preprint arXiv:2211.04627 (2022)

    2022 arXiv

  33. [41]

    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, 11 (2010), 888–893

    2010

  34. [42]

    Pranav S Konduri. 2022. An Implementation of the Parallel K-core Decomposition Algorithm in GraphBLAS. Ph. D. Dissertation

    2022

  35. [43]

    Yi-Xiu Kong, Gui-Yuan Shi, Rui-Jie Wu, and Yi-Cheng Zhang. 2019. k-core: Theories and applications. Physics Reports 832 (2019), 1–32

    2019

  36. [44]

    Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In International World Wide Web Conference (WWW). 591–600. 14

    2010

  37. [45]

    YongChul Kwon, Dylan Nunley, Jeffrey P Gardner, Magdalena Balazinska, Bill Howe, and Sarah Loebman. 2010. Scalable clustering algorithm for N-body simulations in a shared-nothing cluster. In International Conference on Scientific and Statistical Database Management . Springer, 132–150

    2010

  38. [46]

    Longlong Li, Hu Chen, Ping Li, Jie Han, Guanghui Wang, and Gong Zhang. 2021. The k-core decomposition algorithm under the framework of GraphBLAS. In 2021 IEEE High Performance Extreme Computing Conference (HPEC) . IEEE, 1–7

    2021

  39. [47]

    Qingxia Li and Wenhong Wei. 2013. A parallel single-source shortest path algorithm based on bucket structure. In 2013 25th Chinese Control and Decision Conference (CCDC). IEEE, 3445–3450

    2013

  40. [48]

    Xuankun Liao, Qing Liu, Jiaxin Jiang, Xin Huang, Jianliang Xu, and Byron Choi

  41. [49]

    Quanquan C Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun

  42. [50]

    Quanquan C Liu, Julian Shun, and Igor Zablotchi. 2024. Parallel k-Core De- composition with Batched Updates and Asynchronous Reads. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 286–300

    2024

  43. [51]

    Youzhe Liu, Xiaojun Dong, Yan Gu, and Yihan Sun. 2024. Implementation for parallel k-core decomposition. https://github.com/ucrparlay/Parallel-KCore

    2024

  44. [52]

    Wensheng Luo, Yixiang Fang, Chunxu Lin, and Yingli Zhou. 2024. Efficient Parallel D-Core Decomposition at Scale. Proceedings of the VLDB Endowment 17, 10 (2024), 2654–2667

    2024

  45. [53]

    Wensheng Luo, Zhuo Tang, Yixiang Fang, Chenhao Ma, and Xu Zhou. 2023. Scalable algorithms for densest subgraph discovery. In2023 IEEE 39th International Conference on Data Engineering (ICDE) . IEEE, 287–300

    2023

  46. [54]

    Fragkiskos D Malliaros, Christos Giatsidis, Apostolos N Papadopoulos, and Michalis Vazirgiannis. 2020. The core decomposition of networks: Theory, algo- rithms and applications. The VLDB Journal 29, 1 (2020), 61–92

    2020

  47. [55]

    In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Re- lated Graph Problems. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 191–204

  48. [56]

    Amir Mehrafsa, Sean Chester, and Alex Thomo. 2020. Vectorising k-core decom- position for gpu acceleration. In Proceedings of the 32nd International Conference on Scientific and Statistical Database Management . 1–4

    2020

  49. [57]

    Robert Meusel, Oliver Lehmberg, Christian Bizer, and Sebastiano Vigna. 2014. Web Data Commons — Hyperlink Graphs. http://webdatacommons.org/ hyperlinkgraph

    2014

  50. [58]

    Alberto Montresor, Francesco De Pellegrini, and Daniele Miorandi. 2011. Dis- tributed k-core decomposition. In Proceedings of the 30th annual ACM SIGACT- SIGOPS symposium on principles of distributed computing . 207–208

    2011

  51. [59]

    Flaviano Morone, Gino Del Ferraro, and Hernán A Makse. 2019. The k-core as a predictor of structural collapse in mutualistic ecosystems. Nature physics 15, 1 (2019), 95–102

    2019

  52. [60]

    Donald Nguyen, Andrew Lenharth, and Keshav Pingali. 2014. Deterministic Galois: On-demand, Portable and Parameterless. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASP- LOS)

    2014

  53. [61]

    Matula and Leland L

    David W. Matula and Leland L. Beck. 1983. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30, 3 (1983), 417–427

    1983

  54. [62]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI Conference on Artificial Intelligence. https://networkrepository.com

    2015

  55. [63]

    Ahmet Erdem Saríyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and Ümit V Çatalyürek. 2013. Streaming algorithms for k-core decomposition. Proceedings of the VLDB Endowment 6, 6 (2013), 433–444

    2013

  56. [64]

    Ahmet Erdem Sarıyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and Ümit V Çatalyürek. 2016. Incremental k-core decomposition: algorithms and evaluation. The VLDB Journal 25 (2016), 425–447

    2016

  57. [65]

    Stephen B. Seidman. 1983. Network structure and minimum degree. Social networks 5, 3 (1983), 269–287

    1983

  58. [66]

    Jessica Shi, Laxman Dhulipala, and Julian Shun. 2021. Parallel clique counting and peeling algorithms. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA). SIAM, 135–146

    2021

  59. [67]

    OpenStreetMap contributors. 2010. OpenStreetMap. https://www.openstreetmap. org/

    2010

  60. [68]

    Blelloch

    Julian Shun and Guy E. Blelloch. 2013. Ligra: A Lightweight Graph Processing Framework for Shared Memory. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 135–146

    2013

  61. [69]

    Julian Shun and Guy E Blelloch. 2014. Phase-concurrent hash tables for determin- ism. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) . 96–107

    2014

  62. [70]

    Shiwen Sun, Xiaoxiao Liu, Li Wang, and Chengyi Xia. 2020. New link attack strategies of complex networks based on k-core decomposition.IEEE Transactions on Circuits and Systems II: Express Briefs 67, 12 (2020), 3157–3161

    2020

  63. [71]

    Alok Tripathy, Fred Hohman, Duen Horng Chau, and Oded Green. 2018. Scalable k-core decomposition for static graphs using a dynamic graph data structure. In 2018 IEEE International Conference on Big Data (Big Data) . IEEE, 1134–1141

    2018

  64. [72]

    Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun. 2023. Parallel Strong Con- nectivity Based on Faster Reachability. ACM SIGMOD International Conference on Management of Data (SIGMOD) 1, 2 (2023), 1–29

    2023

  65. [73]

    Jessica Shi, Laxman Dhulipala, and Julian Shun. 2023. Theoretically and prac- tically efficient parallel nucleus decomposition. In Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing . 7–8

    2023

  66. [74]

    Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun. 2021. GeoGraph: A Framework for Graph Processing on Geometric Data. ACM SIGOPS Operating Systems Review 55, 1 (2021), 38–46

    2021

  67. [75]

    Dong Wen, Lu Qin, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. 2018. I/o efficient core graph decomposition: application to degeneracy ordering. IEEE Transactions on Knowledge and Data Engineering 31, 1 (2018), 75–90

    2018

  68. [76]

    Stefan Wuchty and Eivind Almaas. 2005. Peeling the yeast protein network. Proteomics 5, 2 (2005), 444–449

    2005

  69. [77]

    Jaewon Yang and Jure Leskovec. 2015. Defining and evaluating network commu- nities based on ground-truth. Knowledge and Information Systems 42, 1 (2015), 181–213

    2015

  70. [78]

    Belt and Road

    Hongguang Yao, Huihui Xiao, and Wei Wei. 2022. Study on the Hierarchical Structure of the “Belt and Road” Aviation Network Based on K-Core Analysis. Discrete Dynamics in Nature and Society 2022, 1 (2022), 2349523

    2022

  71. [79]

    Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D Owens. 2016. Gunrock: A high-performance graph processing library on the GPU. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 1–12

    2016

  72. [80]

    Heng Zhang, Haibo Hou, Libo Zhang, Hongjun Zhang, and Yanjun Wu. 2017. Accelerating core decomposition in large temporal networks using gpus. In International Conference on Neural Information Processing . Springer, 893–903

    2017

  73. [81]

    Haohua Zhang, Hai Zhao, Wei Cai, Jie Liu, and Wanlei Zhou. 2010. Using the k- core decomposition to analyze the static structure of large-scale software systems. The Journal of Supercomputing 53 (2010), 352–369

    2010

  74. [82]

    Chen Zhao, Ting Yu, Zhigao Zheng, Yuanyuan Zhu, Song Jin, Bo Du, and Dacheng Tao. 2024. PICO: Accelerating All k-Core Paradigms on GPU. In Proceedings of the 8th Asia-Pacific Workshop on Networking . 221–222

    2024

  75. [83]

    Chen Zhao, Ting Yu, Zhigao Zheng, Yuanyuan Zhu, Song Jin, Bo Du, and Dacheng Tao. 2024. SpeedCore: Space-efficient and Dependency-aware GPU Parallel Frame- work for Core Decomposition. In International Conference on Parallel Processing (ICPP). 555–564

    2024

  76. [84]

    Yu Zheng, Like Liu, Longhao Wang, and Xing Xie. 2008. Learning transportation mode from raw gps data for geographic applications on the web. In International World Wide Web Conference (WWW). 247–256. 15 1632 64 128 256 k values 0.0 0.1 0.2 0.3 0.4 0.5 Running time (s) OK (0.52...

    2008

  77. [85]

    Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017. Finding critical users for social network engagement: The collapsed k-core problem. In AAAI Conference on Artificial Intelligence , Vol. 31

    2017

  78. [2004]

    Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 70, 5 (2004), 056122

    Models of social networks based on social distance attachment. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 70, 5 (2004), 056122

    2004

  79. [2012]

    In USENIX conference on Operating Systems Design and Implementation (OSDI)

    PowerGraph: distributed Graph-Parallel computation on natural graphs. In USENIX conference on Operating Systems Design and Implementation (OSDI) . 17–30

  80. [2017]

    PeerJ 5 (2017), e3321

    Ranking of critical species to preserve the functionality of mutualistic networks using the k-core decomposition. PeerJ 5 (2017), e3321

    2017

  81. [2020]

    Scientific reports 10, 1 (2020), 3357

    K-core robustness in ecological and financial networks. Scientific reports 10, 1 (2020), 3357

    2020

  82. [2022]

    Distributed d-core decomposition over large directed graphs.arXiv preprint arXiv:2202.05990 (2022)

    2022 arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.