Dynamic graph clustering combining modularity and smoothness

Abstract

Maximizing the quality index modularity has become one of the primary methods for identifying the clustering structure within a graph. Since many contemporary networks are not static but evolve over time, traditional static approaches can be inappropriate for specific tasks. In this work, we pioneer the NP-hard problem of online dynamic modularity maximization. We develop scalable dynamizations of the currently fastest and the most widespread static heuristics and engineer a heuristic dynamization of an optimal static algorithm. Our algorithms efficiently maintain a modularity -based clustering of a graph for which dynamic changes arrive as a stream. For our quickest heuristic we prove a tight bound on its number of operations. In an experimental evaluation on both a real-world dynamic network and on dynamic clustered random graphs, we show that the dynamic maintenance of a clustering of a changing graph yields higher modularity than recomputation, guarantees much smoother clustering dynamics, and requires much lower runtimes. We conclude with giving sound recommendations for the choice of an algorithm.