Pith. sign in

REVIEW 3 major objections 6 minor 109 references

Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs

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

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

Pith's one-line read Replacing per-vertex hashtables with 8-slot sketches cuts GPU label-propagation memory by 44-98x with only a few points of modularity loss.

desk verdict Solid engineering result: replacing per-vertex hashtables with 8-slot MG sketches cuts GPU LPA working memory to O(|V|), demonstrated on 3.8B edges; the speed/quality numbers are in-sample and need scoping. read the letter →

arxiv 2411.19901 v1 pith:QN7TADEH submitted 2024-11-29 cs.DC cs.SI

Subhajit Sahu This is my paper · ORCID
classification cs.DCcs.SI
keywords communitydetectionlabelpropagationGPUMisra-GriessketchBoyer-Moorememoryefficiencylargegraphsmodularity
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

Label Propagation Algorithm (LPA) is a fast way to find communities in large graphs, but the best parallel LPA implementations pay for speed with memory: they keep per-thread or per-vertex hashtables whose total size grows with the number of edges. This paper argues that those hashtables can be replaced by fixed-size sketches—weighted Boyer-Moore (one candidate) and weighted Misra-Gries (eight candidates)—that summarize the most important neighboring community labels. The resulting GPU implementation, $\nu$MG8-LPA, uses 98x less memory than the multicore GVE-LPA and 44x less than the GPU $\nu$-LPA, is 2.4x faster than GVE-LPA and only 1.1x slower than $\nu$-LPA, and loses 4.7%/2.9% modularity relative to those baselines. Because the working set is now proportional to the number of vertices rather than edges, graphs with billions of edges fit on a single GPU. The claim is attractive if one cares about processing large graphs on shared-memory systems where the input graph itself already consumes most of the available memory.

What carries the argument

The load-bearing object is the weighted Misra-Gries (MG) sketch: a fixed-size summary of up to $k=8$ (candidate label, accumulated weight) pairs maintained in GPU shared memory. A neighbor's label-weight pair $(c,w)$ is accumulated by incrementing the matching slot if $c$ is present, otherwise inserting into a free slot, otherwise decrementing every slot's weight by $w$. This keeps the labels with total weight exceeding $K_i/(k+1)$ among the candidates, where $K_i$ is the vertex's weighted degree. The paper uses warp-level vote functions (group.ballot, group.all) to coordinate the eight threads that own the eight slots, uses partial per-group sketches for high-degree vertices and merges them via the mergeability of MG summaries, and skips the second scan by directly taking the maximum-weight slot as the new label. Together these choices reduce the per-iteration working set from $O(|E|)$ to $O(|V|)$ and keep the sketch updates in fast shared memory.

What would settle it

Run $\nu$MG8-LPA on a graph whose communities have near-equal sizes and where many vertices have degrees below $k+1$, with and without the second scan; if the modularity gap between single-scan and double-scan exceeds the 4.7% figure reported on the 13 graphs, the single-scan claim does not hold beyond the tested set. A more direct test: instrument per-vertex disagreements between the sketch's max-slot label and the true argmax of neighbor weights; the fraction of disagreeing vertices is the quantity the single-scan claim implicitly assumes is negligible.

Watch

Extended reading notes

Core claim

The central discovery is that LPA's per-vertex vote over neighbor labels can be computed from a stream summary instead of an exact frequency map. The authors define a weighted Misra-Gries sketch with $k=8$ slots, where each slot holds a candidate community label and an accumulated edge weight; labels are inserted or evicted by decrementing all slot weights when the sketch is full. They implement this on a GPU with warp-level ballot primitives, assigning one thread per slot, giving each low-degree vertex its own thread group and splitting high-degree vertices across thread groups whose partial sketches are merged afterward (aided by the fact that Misra-Gries summaries are mergeable). They then show that a second scan over the neighbors to recompute exact weights of the top-$k$ candidates is unnecessary: picking the highest-weight slot directly gives nearly identical modularity. The result is a space complexity of $O(|V|)$ excluding the input graph, versus $O(|E|)$ for the per-vertex hashtables of $\nu$-LPA, which is what lets a 3.8-billion-edge graph (sk-2005) run on a single A100 GPU that previously ran out of memory.

Load-bearing premise

The single-scan shortcut assumes that the label with the highest sketch weight is almost always the same as the label with the highest true connecting weight, a property tested only on the same 13 graphs used for the headline results; road and k-mer graphs show visibly larger quality drops, so the shortcut's reliability on other graph types is not established.

Editorial extensions

If this is right

  • The 3.8-billion-edge sk-2005 graph runs on a single 80 GB A100 GPU under $\nu$MG8-LPA, while $\nu$-LPA runs out of memory.
  • Compared with GVE-LPA, $\nu$MG8-LPA is 2.4x faster and uses 98x less memory; compared with $\nu$-LPA it is 1.1x slower and uses 44x less memory.
  • Modularity loss is 4.7% versus GVE-LPA and 2.9% versus $\nu$-LPA for $\nu$MG8-LPA; the one-slot $\nu$BM-LPA sells far more quality (20-27% lower) for its speed.
  • Algorithmic memory (excluding the input graph) scales as $O(|V|)$ rather than $O(|E|)$, so the per-iteration working set no longer grows with edge count.

Reading between the lines

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

  • The same $O(|V|)$ sketch machinery should transfer to other per-vertex aggregation algorithms that currently allocate degree-proportional hashtables, such as connected-component labeling and graph partitioning by label diffusion; the memory saving would be identical.
  • Because the quality loss concentrates on road and k-mer graphs, a hybrid scheme that uses full exact counting for low-degree vertices (where the sketch's $k+1$ threshold rarely binds) and sketches only for high-degree vertices might recover most of the lost modularity at small memory cost.
  • With the input graph placed in unified memory, the practical ceiling for this algorithm on an A100-class GPU is set by graph storage rather than algorithm scratch space; the paper's own conclusion gestures at this but does not quantify it.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper proposes two GPU-based label propagation algorithms, νMG8-LPA and νBM-LPA, that replace per-vertex/per-thread hash tables with fixed-size weighted Misra-Gries and Boyer-Moore sketches, thereby reducing the algorithm's working memory from O(|E|) to O(|V|) excluding the input graph. The main claimed results are that νMG8-LPA uses 98x and 44x less memory than GVE-LPA and ν-LPA, is 2.4x faster than GVE-LPA and only 1.1x slower than ν-LPA, with modularity drops of 4.7% and 2.9% relative to those two baselines. The evaluation is carried out on 13 SuiteSparse graphs, and the paper also reports results for νBM-LPA, which is faster but has substantially lower community quality.

Significance. If the memory claims hold, the work is significant: reducing the auxiliary memory of GPU LPA from O(|E|) to O(|V|) is a structural improvement that can make billion-edge graphs processable on a single GPU. The design is plausible and the paper gives credit for using mergeable MG summaries, warp-level primitives, and a publicly available implementation. However, the empirical speed and quality claims are currently in-sample estimates because all hyperparameters are tuned on the same 13 graphs used for the reported benchmarks, and the single-scan shortcut that drives the quality trade-off is validated only by one in-sample experiment. The structural O(|V|) memory result is solid by design, but the headline numeric claims need stronger validation.

major comments (3)
  1. [Section 4.4] The decision to skip the second scan is justified only by the assertion that the most weighted candidate label c@ will 'likely align' with the label c# found by a second scan, and by the experiment summarized in Figure 5. The weighted MG sketch does not guarantee that the maximum-weight slot equals the true maximum-weight neighbor label: the decrement operation subtracts from all slot weights whenever a new label arrives with all slots full, so slot weights are systematically distorted, and labels with true weight below K_i/(k+1) may be absent entirely. Figure 5 reports only mean relative runtime and states that modularity is 'nearly identical' without showing per-graph modularity differences; Section 5.2 itself acknowledges that road networks and protein k-mer graphs yield lower-quality communities. Because the abstract's quality-loss numbers depend on this shortcut, the paper should report the per-graph and per-iteration disagreement rate between c@ and the label chosen by an exact scan over all neighbor labels, the per-graph modularity deltas underlying Figure 5, and results on a held-out or otherwise disjoint set of graphs. Without this, the 'minimal quality loss' claim is not established beyond the benchmark set used to tune the algorithm.
  2. [Sections 4.1, 4.2, 4.5] All major hyperparameters are selected using the same 13 graphs on which the final results are reported: the sketch size k is chosen via Figure 2 in Section 4.1; the degree threshold D_H, thread-group count R_H, and kernel launch configurations are tuned by manual gradient descent in Section 4.2; and the Pick-Less period rho is tuned in Section 4.5. The speedups and quality deltas reported in Section 5 are therefore in-sample estimates, not out-of-sample assessments. This is load-bearing for the speed claims (2.4x faster than GVE-LPA, 1.1x slower than nu-LPA), though it does not affect the structural O(|V|) memory claim. The authors should either tune on a disjoint subset of graphs and evaluate on a held-out set, report sensitivity of runtime and modularity to each parameter, or explicitly frame all performance numbers as in-sample and discuss how much the tuning might overstate them.
  3. [Section 5.2 / memory measurement] Memory usage is measured with cudaMemGetInfo(), which reports global device memory, but the MG sketches are stored in shared memory as described in Section 4.1. The reported memory values for nuMG8-LPA and nuBM-LPA in Figure 7(d) are identical to three decimal places for every graph, which suggests the sketch storage is not included in the reported footprint. The paper should state explicitly whether the headline '98x/44x lower memory' claim refers only to global memory or to the total memory footprint, and should report peak shared-memory usage and occupancy. This matters because shared memory per SM is a finite resource that can limit graph size and kernel occupancy, so the memory-efficiency story is incomplete without those numbers.
minor comments (6)
  1. [Abstract and Section 1] The first sentence of the abstract contains a grammatical error: 'dense connections within groups, than between them' should be 'dense connections within groups than between them.'
  2. [Section 3.4] The text says the Boyer-Moore majority vote algorithm was developed in 1981, but reference [13] is the 1991 MJRTY paper; please correct or clarify the citation.
  3. [Section 4.1] There is a typo in 'a larger value of k is expected to improve community quality, as it increased the likelihood'; it should be 'it increases the likelihood.'
  4. [Section 5.2] The quality comparisons are reported as percentages (e.g., '4.7% lower'), but the paper does not state whether these are relative or absolute modularity differences; please define this clearly and consider reporting per-graph absolute modularity deltas.
  5. [Algorithms 1 and 4] The text in Section 4.2 says that only the first thread group updates the changed-vertex count when multiple groups process a vertex, but the pseudocode as written increments the count for every group; please align the pseudocode and the prose.
  6. [Section 4.6] The claim that fixed-size sketches residing in shared memory yield O(|V|) space complexity is stated without derivation; please add a sentence explaining that the number of simultaneously live sketches is bounded by the number of resident thread blocks rather than by |V|.

Circularity Check

0 steps flagged · score 1.0 of 10

No load-bearing circularity: the reported memory, speed, and quality numbers are benchmark measurements, not predictions forced by fitted parameters or self-citations.

full rationale

The paper contains no derivation chain in which a claimed result is equal to an input by construction. The central memory claim (O(|V|) working set with 8-slot MG sketches) follows directly from the fixed-size sketch design described in Section 4.6, and the reported memory reductions are measurements against prior implementations, not outputs of a fitted equation. Hyperparameters such as k=8, D_H=128, R_H=32, and rho=8 are tuned on the same 13 SuiteSparse graphs used for the final measurements (Sections 4.1, 4.2, 4.5), so the speed and quality figures are in-sample and may not generalize; the paper itself admits lower quality on road and k-mer graphs. This is a benchmarking and generalization limitation, not a circular reduction, because no parameter is renamed as a prediction and no final number is computed from the fitted values. Self-citations ([74], [76], [77]) supply prior baselines and the MG-sketch idea, but the current paper re-derives or re-tests the load-bearing choices, e.g., k=8 via Figure 2, the single-scan shortcut via Figure 5, and rho=8 via its own testing in Section 4.5, so these citations are not load-bearing in a circular way. The single-scan shortcut in Section 4.4 is an empirical approximation checked on the same graphs, not a theorem obtained from the sketch definition. Therefore no significant circularity is present.

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

The central claims rest on standard Misra-Gries/Boyer-Moore sketch theory and mergeability of MG summaries, plus a set of hyperparameters tuned on the evaluation graphs (k=8, DH=128, RH=32, block sizes, Pick-Less period). The single-scan shortcut is an empirical assumption tested only in-sample. No new entities are introduced.

free parameters (7)
  • k (MG sketch slots) = 8
    Chosen from experiments on the 13 benchmark graphs balancing runtime and modularity (Figure 2); this value directly controls sketch size and memory usage.
  • DH (high-degree threshold) = 128
    Tuned by manual gradient descent on the benchmark graphs (Section 4.2); determines which kernel processes a vertex.
  • RH (thread groups per high-degree vertex) = 32
    Tuned by manual gradient descent (Section 4.2); controls parallelism and contention in the block-per-vertex kernel.
  • Kernel launch configurations = 32 threads/block (group kernel), 256 threads/block (block kernel)
    Tuned by manual gradient descent (Section 4.2, 5.1.2).
  • PL period rho = 8
    Adjusted from 4 to 8 after testing on the graphs (Section 4.5); influences final modularity.
  • Tolerance tau = 0.05
    Adopted from GVE-LPA [74] and used as stopping criterion; not tuned here but affects runtime and final quality.
  • MAX_ITERATIONS = 20
    Cap on LPA iterations, adopted from prior work; not tuned here.
assumptions (5)
  • standard math Misra-Gries sketch property: after streaming, all labels with weight > K_i/(k+1) are guaranteed to be retained.
    Invoked in Section 4 approach to justify tracking only k labels per vertex; standard result from Misra-Gries [58].
  • standard math MG summaries are mergeable: merging partial sketches yields a sketch of the union.
    Used in Section 4.3 to merge per-thread-group sketches; from Agarwal et al. [2].
  • ad hoc to paper Single-scan equivalence: the highest-weight label in the sketch equals the true highest-weight neighbor label often enough that no second scan is needed.
    Empirical assumption validated only by one experiment on the same 13 graphs (Section 4.4, Figure 5).
  • ad hoc to paper Pick-Less periodic label restriction preserves community quality.
    Heuristic from author's prior ν-LPA [77], with period rho tuned in Section 4.5; no proof that it does not distort final communities.
  • domain assumption Modularity is a valid quality metric for disjoint community detection.
    Used throughout evaluation (Equation 1); standard in the community detection literature but not without known limitations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs." pith.science (2026). https://pith.science/paper/QN7TADEH

@misc{pith2026241119901,
  author       = {Pith},
  title        = {Pith review of: Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QN7TADEH}},
  note         = {Machine review of arXiv:2411.19901}
}
abstract

Community detection involves grouping nodes in a graph with dense connections within groups, than between them. We previously proposed efficient multicore (GVE-LPA) and GPU-based ($\nu$-LPA) implementations of Label Propagation Algorithm (LPA) for community detection. However, these methods incur high memory overhead due to their per-thread/per-vertex hashtables. This makes it challenging to process large graphs on shared memory systems. In this report, we introduce memory-efficient GPU-based LPA implementations, using weighted Boyer-Moore (BM) and Misra-Gries (MG) sketches. Our new implementation, $\nu$MG8-LPA, using an 8-slot MG sketch, reduces memory usage by 98x and 44x compared to GVE-LPA and $\nu$-LPA, respectively. It is also 2.4x faster than GVE-LPA and only 1.1x slower than $\nu$-LPA, with minimal quality loss (4.7%/2.9% drop compared to GVE-LPA/$\nu$-LPA).

Figures

Figures reproduced from arXiv: 2411.19901 by the authors.

Figure 1
Figure 1. Illustration of per-vertex open-addressing hashta [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Relative runtime and Modularity of obtained com [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 4
Figure 4. Relative Runtime of Shared sketch and Partial sketches approaches for populating weighted Misra-Gries (MG) sketches from the neighborhood of each vertex. 4.4 A Single Scan is Sufficient Note that the 𝑘 candidate labels we obtain for a vertex 𝑖 in an MG sketch will include labels with a linking weight greater than 𝐾𝑖 𝑘+1 , where 𝐾𝑖 is the weighted degree of 𝑖. However, not all of these labels will necessarily exceed … view at source ↗
Figures from the paper (2 more)
Figure 6
Figure 6. Figure 6: Illustration of how 𝜈MG-LPA selects the best candi￾date community label for each vertex, with the group-per￾vertex kernel shown in (a), and the block-per-vertex kernel shown in (b). Here, the number of slots in each MG sketch is assumed to be 𝑘 = 4, and in the block-pe…
Figure 7
Figure 7. Figure 7: Runtime in seconds (log-scale), speedup (log-scale), modularity of obtained communities, and memory usage in [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

109 extracted references · 51 canonical work pages

  1. [1]

    Emmanuel Abbe. 2018. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research 18, 177 (2018), 1–86

    2018

  2. [2]

    Pankaj K Agarwal, Graham Cormode, Zengfeng Huang, Jeff M Phillips, Zhewei Wei, and Ke Yi. 2013. Mergeable summaries. ACM Transactions on Database Systems (TODS) 38, 4 (2013), 1–28

    2013

  3. [3]

    Tarique Aziz, Muhammad Waseem, Shengyuan Liu, Zhenzhi Lin, Yuxuan Zhao, and Kaiyuan Pang. 2023. A novel power system sectionalizing strategy based on modified label propagation algorithm. In 2023 6th International Conference on Energy, Electrical and Power Engineering (CEEPE) . IEEE, 807–812

    2023

  4. [4]

    Minho Bae, Minjoong Jeong, and Sangyoon Oh. 2020. Label propagation-based parallel graph partitioning for large-scale graph data. IEEE Access 8 (2020), 72801–72813

    2020

  5. [5]

    Yuhe Bai, Camelia Constantin, and Hubert Naacke. 2024. Leiden-Fusion Par- titioning Method for Effective Distributed Training of Graph Embeddings. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 366–382

    2024

  6. [6]

    Joel J Bechtel, William A Kelley, Teresa A Coons, M Gerry Klein, Daniel D Slagel, and Thomas L Petty. 2005. Lung cancer detection in patients with airflow obstruction identified in a primary care outpatient practice. Chest 127, 4 (2005), 1140–1145

    2005

  7. [7]

    Kamal Berahmand and Asgarali Bouyer. 2018. LP-LPA: A link influence-based label propagation algorithm for discovering community structures in networks. International Journal of Modern Physics B 32, 06 (2018), 1850062

    2018

  8. [8]

    Bhowmick, S

    A. Bhowmick, S. Vadhiyar, and V. PV. 2022. Scalable multi-node multi-GPU Louvain community detection algorithm for heterogeneous architectures. Con- currency and Computation: Practice and Experience 34, 17 (2022), 1–18

    2022

Show all 109 references
  1. [9]

    Bhowmik and S

    A. Bhowmik and S. Vadhiyar. 2019. HyDetect: A Hybrid CPU-GPU Algorithm for Community Detection. In IEEE 26th International Conference on High Perfor- mance Computing, Data, and Analytics (HiPC) . IEEE, Goa, India, 2–11

    2019

  2. [10]

    Ivan Blekanov, Svetlana S Bodrunova, and Askar Akhmetov. 2021. Detection of hidden communities in twitter discussions of varying volumes. Future Internet 13, 11 (2021), 295

    2021

  3. [11]

    Blondel, J

    V. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008, 10 (Oct 2008), P10008

    2008

  4. [12]

    Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. 2011. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th international conference on World Wide Web. 587–596

    2011

  5. [13]

    Robert S Boyer and J Strother Moore. 1991. MJRTY—a fast majority vote algorithm. In Automated reasoning: essays in honor of Woody Bledsoe . Springer, 105–117

    1991

  6. [14]

    Lingli Cao and Cheng Zhang. 2022. Implementation of domain-oriented mi- croservices decomposition based on node-attributed network. In Proceedings of the 2022 11th International Conference on Software and Computer Applications . 136–142

    2022

  7. [15]

    Wendong Chen, Xize Liu, Xuewu Chen, Long Cheng, and Jingxu Chen. 2023. Deciphering flow clusters from large-scale free-floating bike sharing journey data: a two-stage flow clustering method. Transportation (2023), 1–30

    2023

  8. [16]

    Cheong, H

    C. Cheong, H. Huynh, D. Lo, and R. Goh. 2013. Hierarchical Parallel Algorithm for Modularity-Based Community Detection Using GPUs. In Proceedings of the 19th International Conference on Parallel Processing (Aachen, Germany) (Euro-Par’13). Springer-Verlag, Berlin, Heidelberg, 775–787

    2013

  9. [17]

    Han-Yi Chou and Sayan Ghosh. 2022. Batched Graph Community Detection on GPUs. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. 172–184

    2022

  10. [18]

    Aaron Clauset, Mark EJ Newman, and Cristopher Moore. 2004. Finding com- munity structure in very large networks. Physical review E 70, 6 (2004), 066111

    2004

  11. [19]

    Michele Coscia, Fosca Giannotti, and Dino Pedreschi. 2011. A classification for community discovery methods in complex networks. Statistical Analysis and Data Mining: The ASA Data Science Journal 4, 5 (2011), 512–546

    2011

  12. [20]

    Dipanjan Das and Slav Petrov. 2011. Unsupervised part-of-speech tagging with bilingual graph-based projections. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies . 600–609

    2011

  13. [21]

    Jordi Duch and Alex Arenas. 2005. Community detection in complex networks using extremal optimization. Physical review E 72, 2 (2005), 027104

    2005

  14. [22]

    Imen Ben El Kouni, Wafa Karoui, and Lotfi Ben Romdhane. 2021. WLNI-LPA: Detecting Overlapping Communities in Attributed Networks based on Label Propagation Process.. In ICSOFT. 408–416

    2021

  15. [23]

    Golnoosh Farnadi, Zeinab Mahdavifar, Ivan Keller, Jacob Nelson, Ankur Tere- desai, Marie-Francine Moens, and Martine De Cock. 2015. Scalable adaptive label propagation in Grappa. In 2015 IEEE International Conference on Big Data (Big Data). IEEE, 1485–1491

    2015

  16. [24]

    Fazlali, E

    M. Fazlali, E. Moradi, and H. Malazi. 2017. Adaptive parallel Louvain community detection on a multicore platform. Microprocessors and microsystems 54 (Oct 2017), 26–34

    2017

  17. [25]

    Fortunato

    S. Fortunato. 2010. Community detection in graphs. Physics reports 486, 3-5 (2010), 75–174

    2010

  18. [26]

    Gach and J

    O. Gach and J. Hao. 2014. Improving the Louvain algorithm for community de- tection with modularity maximization. In Artificial Evolution: 11th International Conference, Evolution Artificielle, EA , Bordeaux, France, October 21-23, . Revised Selected Papers 11. Springer, Sprin...

    2014

  19. [27]

    Gawande, S

    N. Gawande, S. Ghosh, M. Halappanavar, A. Tumeo, and A. Kalyanaraman. 2022. Towards scaling community detection on distributed-memory heterogeneous systems. Parallel Comput. 111 (2022), 102898

    2022

  20. [28]

    Ghosh, M

    S. Ghosh, M. Halappanavar, A. Tumeo, A. Kalyanaraman, and A.H. Gebremedhin

  21. [29]

    Ghosh, M

    S. Ghosh, M. Halappanavar, A. Tumeo, A. Kalyanaraman, H. Lu, D. Chavarria- Miranda, A. Khan, and A. Gebremedhin. 2018. Distributed louvain algorithm for graph community detection. In IEEE International Parallel and Distributed Processing Symposium (IPDPS). Vancouver, British C...

    2018

  22. [30]

    Lars Gottesbüren, Tobias Heuer, Peter Sanders, and Sebastian Schlag. 2021. Scalable Shared-Memory Hypergraph Partitioning. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX) . SIAM, 16–30

    2021

  23. [31]

    S. Gregory. 2010. Finding overlapping communities in networks by label propa- gation. New Journal of Physics 12 (10 2010), 103018. Issue 10. 11 Subhajit Sahu

    2010

  24. [32]

    Roger Guimerà, DB Stouffer, Marta Sales-Pardo, EA Leicht, MEJ Newman, and Luis AN Amaral. 2010. Origin of compartmentalization in food webs. Ecology 91, 10 (2010), 2941–2951

    2010

  25. [33]

    Halappanavar, H

    M. Halappanavar, H. Lu, A. Kalyanaraman, and A. Tumeo. 2017. Scalable static and dynamic community detection using Grappolo. In IEEE High Performance Extreme Computing Conference (HPEC) . IEEE, Waltham, MA USA, 1–6

    2017

  26. [34]

    Nandinee Haq and Z Jane Wang. 2016. Community detection from genomic datasets across human cancers. In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP). IEEE, 1147–1150

    2016

  27. [35]

    Mark Harris. 2017. Unified Memory for CUDA Beginners. https://developer.nvidia.com/blog/unified-memory-cuda-beginners/. [Online; accessed 2024-11-02]

    2017

  28. [36]

    Mark Harris and Kyrylo Perelygin. 2017. Cooperative Groups: Flexible CUDA Thread Programming. https://developer.nvidia.com/blog/cooperative-groups/. [Online; accessed 2024-11-02]

    2017

  29. [37]

    Vitali Henne. 2015. Label propagation for hypergraph partitioning . Ph. D. Dis- sertation. Karlsruher Institut für Technologie (KIT)

    2015

  30. [38]

    Alexandre Hollocou, Julien Maudet, Thomas Bonald, and Marc Lelarge. 2017. A linear streaming algorithm for community detection in very large networks. arXiv preprint arXiv:1703.02955 (2017)

    2017 arXiv

  31. [39]

    Alexandre Hollocou, Julien Maudet, Thomas Bonald, and Marc Lelarge. 2017. A streaming algorithm for graph clustering. arXiv preprint arXiv:1712.04337 (2017)

    2017 arXiv

  32. [40]

    Yongmin Hu, Jing Wang, Cheng Zhao, Yibo Liu, Cheng Chen, Xiaoliang Cong, and Chao Li. [n. d.]. ParLeiden: Boosting Parallelism of Distributed Leiden Algorithm on Large-scale Graphs. ([n. d.])

  33. [41]

    S. Kang, C. Hastings, J. Eaton, and B. Rees. 2023. cuGraph C++ primitives: vertex/edge-centric building blocks for parallel graph computing. In IEEE Inter- national Parallel and Distributed Processing Symposium Workshops . 226–229

    2023

  34. [42]

    I’ll be back

    Arnav Kapoor, Rishi Raj Jain, Avinash Prabhu, Tanvi Karandikar, and Ponnu- rangam Kumaraguru. 2021. “I’ll be back”: Examining Restored Accounts On Twitter. In IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology. 71–78

    2021

  35. [43]

    Pan-Jun Kim, Dong-Yup Lee, and Hawoong Jeong. 2009. Centralized modularity of N-linked glycosylation pathways in mammalian cells. PloS one 4, 10 (2009), e7317

    2009

  36. [44]

    Kloster and D

    K. Kloster and D. Gleich. 2014. Heat kernel based community detection. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining . ACM, New York, USA, 1386–1395

    2014

  37. [45]

    Kolodziej, M

    S. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. Davis, M. Henderson, Y. Hu, and R. Sandstrom. 2019. The SuiteSparse matrix collection website interface. The Journal of Open Source Software 4, 35 (Mar 2019), 1244

    2019

  38. [46]

    Yusuke Kozawa, Toshiyuki Amagasa, and Hiroyuki Kitagawa. 2017. Gpu- accelerated graph clustering via parallel label propagation. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management . 567–576

    2017

  39. [47]

    Massimo La Morgia, Alessandro Mei, Alberto Maria Mongardini, and Jie Wu

  40. [48]

    Rongrong Li, Wenzhong Guo, Kun Guo, and Qirong Qiu. 2015. Parallel multi- label propagation for overlapping community detection in large-scale networks. In Multi-disciplinary Trends in Artificial Intelligence: 9th International Workshop, MIW AI 2015, Fuzhou, China, November 13...

    2015

  41. [49]

    Panagiotis Liakos, Alexandros Ntoulas, and Alex Delis. 2017. COEUS: commu- nity detection via seed-set expansion on graph streams. In 2017 IEEE Interna- tional Conference on Big Data (Big Data) . IEEE, 676–685

    2017

  42. [50]

    Panagiotis Liakos, Katia Papakonstantinopoulou, Alexandros Ntoulas, and Alex Delis. 2020. Rapid detection of local communities in graph streams. IEEE Transactions on Knowledge and Data Engineering 34, 5 (2020), 2375–2386

    2020

  43. [51]

    Yuan Lin. 2018. Using CUDA warp-level primitives. https://developer.nvidia.com/blog/using-cuda-warp-level-primitives/. [Online; accessed 2024-11-02]

    2018

  44. [52]

    H. Lu, M. Halappanavar, and A. Kalyanaraman. 2015. Parallel heuristics for scalable community detection. Parallel computing 47 (Aug 2015), 19–37

    2015

  45. [53]

    Milo Lurati, Stijn Heldens, Alessio Sclocco, and Ben van Werkhoven. 2024. Bringing Auto-Tuning to HIP: Analysis of Tuning Impact and Difficulty on AMD and Nvidia GPUs. In European Conference on Parallel Processing . Springer, 91–106

    2024

  46. [54]

    Jun Ma, Jenny Wang, Laleh Soltan Ghoraie, Xin Men, Benjamin Haibe-Kains, and Penggao Dai. 2019. A comparative study of cluster detection algorithms in protein–protein interaction for drug target discovery and drug repurposing. Frontiers in pharmacology 10 (2019), 109

    2019

  47. [55]

    Tinghuai Ma, Mingliang Yue, Jingjing Qu, Yuan Tian, Abdullah Al-Dhelaan, and Mznah Al-Rodhaan. 2018. PSPLPA: Probability and similarity based parallel label propagation algorithm on spark. Physica A: Statistical Mechanics and its Applications 503 (2018), 366–378

    2018

  48. [56]

    Erfan Farhangi Maleki, Nasser Ghadiri, Maryam Lotfi Shahreza, and Zeinab Maleki. 2020. DHLP 1&2: Giraph based distributed label propagation algorithms on heterogeneous drug-related networks. Expert Systems with Applications 159 (2020), 113640

    2020

  49. [57]

    Henning Meyerhenke, Peter Sanders, and Christian Schulz. 2017. Parallel graph partitioning for complex networks. IEEE Transactions on Parallel and Distributed Systems 28, 9 (2017), 2625–2638

    2017

  50. [58]

    Jayadev Misra and David Gries. 1982. Finding repeated elements. Science of computer programming 2, 2 (1982), 143–152

    1982

  51. [59]

    Mohammadi, M

    M. Mohammadi, M. Fazlali, and M. Hosseinzadeh. 2020. Accelerating Louvain community detection algorithm on graphic processing unit. The Journal of supercomputing (Nov 2020)

    2020

  52. [60]

    Anuraj Mohan, R Venkatesan, and KV Pramod. 2017. A scalable method for link prediction in large real world networks. J. Parallel and Distrib. Comput. 109 (2017), 89–101

    2017

  53. [61]

    M. Naim, F. Manne, M. Halappanavar, and A. Tumeo. 2017. Community de- tection on the GPU. In IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, Orlando, Florida, USA, 625–634

    2017

  54. [62]

    M. Newman. 2006. Finding community structure in networks using the eigen- vectors of matrices. Physical review E 74, 3 (2006), 036104

    2006

  55. [63]

    Ozaki, H

    N. Ozaki, H. Tezuka, and M. Inaba. 2016. A simple acceleration method for the Louvain algorithm. International Journal of Computer and Electrical Engineering 8, 3 (2016), 207

    2016

  56. [64]

    Leto Peel, Daniel B Larremore, and Aaron Clauset. 2017. The ground truth about metadata and community detection in networks. Science advances 3, 5 (2017), e1602548

    2017

  57. [65]

    Chengbin Peng, Tamara G Kolda, and Ali Pinar. 2014. Accelerating community detection by using k-core subgraphs. arXiv preprint arXiv:1403.2226 (2014)

    2014 arXiv

  58. [66]

    Ovidiu Popa, Einat Hazkani-Covo, Giddy Landan, William Martin, and Tal Dagan. 2011. Directed networks reveal genomic barriers and DNA repair bypasses to lateral gene transfer among prokaryotes. Genome research 21, 4 (2011), 599–609

    2011

  59. [67]

    Hang Qie, Shijie Li, Yong Dou, Jinwei Xu, Yunsheng Xiong, and Zikai Gao. 2022. Isolate sets partition benefits community detection of parallel Louvain method. Scientific Reports 12, 1 (2022), 8248

    2022

  60. [68]

    Raghavan, R

    U. Raghavan, R. Albert, and S. Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 76, 3 (Sep 2007), 036106–1–036106–11

    2007

  61. [69]

    Jörg Reichardt and Stefan Bornholdt. 2006. Statistical mechanics of community detection. Physical review E 74, 1 (2006), 016110

    2006

  62. [70]

    Corban G Rivera, Rachit Vakil, and Joel S Bader. 2010. NeMo: network module identification in Cytoscape. BMC bioinformatics 11 (2010), 1–9

    2010

  63. [71]

    Hamid Roghani, Asgarali Bouyer, and Esmaeil Nourani. 2021. PLDLS: A novel parallel label diffusion and label Selection-based community detection algorithm based on Spark in social networks. Expert Systems with Applications 183 (2021), 115377

    2021

  64. [72]

    Rosvall and C

    M. Rosvall and C. Bergstrom. 2008. Maps of random walks on complex networks reveal community structure. Proceedings of the national academy of sciences 105, 4 (2008), 1118–1123

    2008

  65. [73]

    Rotta and A

    R. Rotta and A. Noack. 2011. Multilevel local search algorithms for modularity clustering. Journal of Experimental Algorithmics (JEA) 16 (2011), 2–1

    2011

  66. [74]

    Subhajit Sahu. 2023. GVE-LPA: Fast Label Propagation Algorithm (LPA) for Com- munity Detection in Shared Memory Setting. arXiv preprint arXiv:2312.08140 (2023)

    2023 arXiv

  67. [75]

    S. Sahu. 2023. Selecting a suitable Parallel Label-propagation based algorithm for Disjoint Community Detection. arXiv preprint arXiv:2301.09125 (2023)

    2023 arXiv

  68. [76]

    Subhajit Sahu. 2024. Memory-Efficient Community Detection on Large Graphs Using Weighted Sketches. arXiv preprint arXiv:2411.02268 (2024)

    2024 arXiv

  69. [77]

    Subhajit Sahu. 2024. 𝜈-LPA: Fast GPU-based Label Propagation Algorithm (LPA) for Community Detection. arXiv preprint arXiv:2411.11468 (2024)

    2024 arXiv

  70. [78]

    Marcel Salathé and James H Jones. 2010. Dynamics and control of diseases in networks with community structure. PLoS computational biology 6, 4 (2010), e1000736

    2010

  71. [79]

    Naw Safrin Sattar and Shaikh Arifuzzaman. 2022. Scalable distributed Louvain algorithm for community detection in large graphs. The Journal of Supercom- puting 78, 7 (2022), 10275–10309

    2022

  72. [80]

    Mohammad Sattari and Kamran Zamanifar. 2018. A spreading activation-based label propagation algorithm for overlapping community detection in dynamic social networks. Data & Knowledge Engineering 113 (2018), 155–170

    2018

  73. [81]

    J. Shi, L. Dhulipala, D. Eisenstat, J. Łącki, and V. Mirrokni. 2021. Scalable community detection via parallel correlation clustering

    2021

  74. [82]

    George M Slota, Cameron Root, Karen Devine, Kamesh Madduri, and Sivasankaran Rajamanickam. 2020. Scalable, multi-constraint, complex- objective graph partitioning. IEEE Transactions on Parallel and Distributed Systems 31, 12 (2020), 2789–2801

    2020

  75. [83]

    Jyothish Soman and Ankur Narang. 2011. Fast community detection algorithm with gpus and multicore architectures. In 2011 IEEE International Parallel & Distributed Processing Symposium. IEEE, 568–579

    2011

  76. [84]

    Staudt, A

    C.L. Staudt, A. Sazonovs, and H. Meyerhenke. 2016. NetworKit: A tool suite for large-scale complex network analysis. Network Science 4, 4 (2016), 508–530. 12 Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs

    2016

  77. [85]

    Christian L Staudt and Henning Meyerhenke. 2015. Engineering parallel al- gorithms for community detection in massive networks. IEEE Transactions on Parallel and Distributed Systems 27, 1 (2015), 171–184

    2015

  78. [86]

    Stergios Stergiou, Dipen Rughwani, and Kostas Tsioutsiouliklis. 2018. Shortcut- ting label propagation for distributed connected components. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining . 540–546

    2018

  79. [87]

    V. Traag. 2015. Faster unfolding of communities: Speeding up the Louvain algorithm. Physical Review E 92, 3 (2015), 032801

    2015

  80. [88]

    Traag and L

    V.A. Traag and L. Šubelj. 2023. Large network community detection by fast label propagation. Scientific Reports 13, 1 (2023), 2701

    2023

  81. [89]

    Traag, L

    V. Traag, L. Waltman, and N. Eck. 2019. From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports 9, 1 (Mar 2019), 5233

    2019

  82. [90]

    Lucreţia Udrescu, Paul Bogdan, Aimée Chiş, Ioan Ovidiu Sîrbu, Alexandru Topîrceanu, Renata-Maria Văruţ, and Mihai Udrescu. 2020. Uncovering new drug properties in target-based drug–drug similarity networks. Pharmaceutics 12, 9 (2020), 879

    2020

  83. [91]

    Joshua Uyheng, Aman Tyagi, and Kathleen M Carley. 2021. Mainstream consen- sus and the expansive fringe: characterizing the polarized information ecosys- tems of online climate change discourse. In Proceedings of the 13th ACM Web Science Conference 2021. 196–204

    2021

  84. [92]

    Alan Valejo, Thiago Faleiros, Maria Cristina Ferreira de Oliveira, and Alneu de Andrade Lopes. 2020. A coarsening method for bipartite networks via weight-constrained label propagation. Knowledge-Based Systems 195 (2020), 105678

    2020

  85. [93]

    Ann Verhetsel, Joris Beckers, and Jeroen Cant. 2022. Regional retail landscapes emerging from spatial network analysis. Regional Studies 56, 11 (2022), 1829– 1844

    2022

  86. [94]

    Waltman and N

    L. Waltman and N. Eck. 2013. A smart local moving algorithm for large-scale modularity-based community detection. The European physical journal B 86, 11 (2013), 1–14

    2013

  87. [95]

    Changzhen Wang, Fahui Wang, and Tracy Onega. 2021. Network optimization approach to delineating health care service areas: Spatially constrained Louvain and Leiden algorithms. Transactions in GIS 25, 2 (2021), 1065–1081

    2021

  88. [96]

    Meng Wang, Yanhao Yang, David Bindel, and Kun He. 2023. Streaming local community detection through approximate conductance. IEEE Transactions on Big Data (2023)

    2023

  89. [97]

    Yan Wang, Rongrong Ji, and Shih-Fu Chang. 2013. Label propagation from imagenet to 3d point clouds. In Proceedings of the IEEE conference on computer vision and pattern recognition . 3135–3142

    2013

  90. [98]

    Wickramaarachchi, M

    C. Wickramaarachchi, M. Frincu, P. Small, and V. Prasanna. 2014. Fast parallel algorithm for unfolding of communities in large graphs. In IEEE High Perfor- mance Extreme Computing Conference (HPEC) . IEEE, IEEE, Waltham, MA USA, 1–6

    2014

  91. [99]

    J. Xie, M. Chen, and B. Szymanski. 2013. LabelrankT: Incremental community detection in dynamic networks via label propagation. In Proceedings of the Workshop on Dynamic Networks Management and Mining . ACM, New York, USA, 25–32

    2013

  92. [100]

    J. Xie, B. Szymanski, and X. Liu. 2011. SLPA: Uncovering overlapping commu- nities in social networks via a speaker-listener interaction dynamic process. In IEEE 11th International Conference on Data Mining Workshops . IEEE, IEEE, Vancouver, Canada, 344–349

    2011

  93. [101]

    Xiaolong Xu, Nan Hu, Tao Li, Marcello Trovati, Francesco Palmieri, Georgios Kontonatsios, and Aniello Castiglione. 2019. Distributed temporal link predic- tion algorithm based on label propagation. Future generation computer systems 93 (2019), 627–636

    2019

  94. [102]

    Chang Ye, Yuchen Li, Bingsheng He, Zhao Li, and Jianling Sun. 2023. Large- Scale Graph Label Propagation on GPUs. IEEE Transactions on Knowledge and Data Engineering (2023)

    2023

  95. [103]

    Bagher Zarei, Mohammad Reza Meybodi, and Behrooz Masoumi. 2020. De- tecting community structure in signed and unsigned social networks by using weighted label propagation. Chaos: An Interdisciplinary Journal of Nonlinear Science 30, 10 (2020)

    2020

  96. [104]

    Weitong Zhang, Ronghua Shang, and Licheng Jiao. 2023. Large-scale community detection based on core node and layer-by-layer label propagation. Information Sciences 632 (2023), 1–18

    2023

  97. [105]

    Xian-Kun Zhang, Jing Ren, Chen Song, Jia Jia, and Qian Zhang. 2017. Label propagation algorithm for community detection based on node importance and label influence. Physics Letters A 381, 33 (2017), 2691–2698

    2017

  98. [106]

    Yu Zheng, Yongxin Zhu, Shijin Song, Peng Xiong, Zihao Cao, and Junjie Hou

  99. [109]

    In 17th IEEE TrustCom / 12th IEEE BigDataSE

    Improved weighted label propagation algorithm in social network com- puting. In 17th IEEE TrustCom / 12th IEEE BigDataSE . IEEE, 1799–1803. 13 Subhajit Sahu A APPENDIX A.1 Our Weighted Misra-Gries (MG) based GPU Implementation of LPA Algorithm 1 outlines the pseudocode for our...

  100. [2018]

    In 2018 IEEE High Performance extreme Computing Conference (HPEC)

    Scalable distributed memory community detection using vite. In 2018 IEEE High Performance extreme Computing Conference (HPEC) . IEEE, 1–7

    2018

  101. [2021]

    arXiv preprint arXiv:2111.13530 (2021)

    Uncovering the dark side of Telegram: Fakes, clones, scams, and conspiracy movements. arXiv preprint arXiv:2111.13530 (2021)

    2021 arXiv

Pith tools

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