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 modularity at low memory cost.
A Streaming Algorithm for Graph Clustering
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
cs.LG 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
CluStRE: Streaming Graph Clustering with Multi-Stage Refinement
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 modularity at low memory cost.