A Streaming Algorithm for Graph Clustering
Preprint
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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Detecting the overlapping and hierarchical community structure in complex networksNew Journal of Physics, 2009
- Patterns and dynamics of users' behavior and interaction: Network analysis of an online communityJournal of the American Society for Information Science and Technology, 2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences, 2008
- Spectral partitioning works: Planar graphs and finite element meshesLinear Algebra and its Applications, 2007
- On graph problems in a semi-streaming modelTheoretical Computer Science, 2005
- Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming modelsDistributed Computing, 2005
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Fast algorithm for detecting community structure in networksPhysical Review E, 2004