  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.
