A Streaming Algorithm for Graph Clustering

2017-12-09 · Alexandre Hollocou, Julien Maudet, Thomas Bonald, Marc Lelarge

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.

📄 PDF Abstract BibTeX arXiv:1712.04337

Code (1)

ahollocou/graph-streaming 공식 구현

Tasks

ClusteringGraph Clustering

CluStRE: Streaming Graph Clustering with Multi-Stage Refinement

2025-02-08 · Adil Chhabra, Shai Dorian Peretz, Christian Schulz

We present CluStRE, a novel streaming graph clustering algorithm that balances computational efficiency with high-quality clustering using multi-stage refinement. Unlike traditional in-memory clustering approaches, CluSt…

Clustering Computational Efficiency Graph Clustering

Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost

2023-09-21 · NeurIPS 2023 11

Correlation clustering is a fundamental optimization problem at the intersection of machine learning and theoretical computer science. Motivated by applications to big data processing, recent years have witnessed a flur…

Incremental Community Detection in Distributed Dynamic Graph

2021-10-12 · Tariq Abughofa, Ahmed A. Harby, Haruna Isah, Farhana Zulkernine

Community detection is an important research topic in graph analytics that has a wide range of applications. A variety of static community detection algorithms and quality metrics were developed in the past few years. Ho…

Clustering Community Detection

Learning-Augmented Streaming Algorithms for Correlation Clustering

2025-10-12 · Yinhao Dong, Shan Jiang, Shi Li, Pan Peng arxiv

We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partition the vertices into disjoint clusters,…

Online Clustering by Penalized Weighted GMM

2019-02-07 · Shlomo Bugdary, Shay Maymon

With the dawn of the Big Data era, data sets are growing rapidly. Data is streaming from everywhere - from cameras, mobile phones, cars, and other electronic devices. Clustering streaming data is a very challenging probl…

Clustering Online Clustering