Pith. sign in

REVIEW 2 cited by

A Streaming Algorithm for Graph Clustering

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1712.04337 v1 pith:XUEYA2V5 submitted 2017-12-09 cs.LG cs.SI

Alexandre Hollocou , Julien Maudet , Thomas Bonald , Marc Lelarge This is my paper · ORCID
classification cs.LGcs.SI
keywords algorithmgraphstreamingclusteringedgeedgesgraphsmemory
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We introduce a novel algorithm to perform graph clustering in the edge streaming setting. In this model, the graph is presented as a sequence of edges that can be processed strictly once. Our streaming algorithm has an extremely low memory footprint as it stores only three integers per node and does not keep any edge in memory. We provide a theoretical justification of the design of the algorithm based on the modularity function, which is a usual metric to evaluate the quality of a graph partition. We perform experiments on massive real-life graphs ranging from one million to more than one billion edges and we show that this new algorithm runs more than ten times faster than existing algorithms and leads to similar or better detection scores on the largest graphs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. CluStRE: Streaming Graph Clustering with Multi-Stage Refinement

    cs.LG 2025-02 conditional novelty 6.0 of 10

    CluStRE is a streaming graph clustering algorithm that combines one-pass node assignment, on-the-fly quotient graph construction, memetic refinement, and re-streaming local search to approach Louvain-quality modularit...

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

    cs.DC 2024-11 conditional novelty 4.0 of 10

    Replacing per-vertex hash tables with 8-slot Misra-Gries sketches makes GPU label propagation use O(|V|) memory instead of O(|E|), cutting memory up to 98x with roughly 5% modularity loss.

Pith tools