Access Restriction

Author Grke, Robert ♦ Maillard, Pascal ♦ Schumm, Andrea ♦ Staudt, Christian ♦ Wagner, Dorothea
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Dynamic graph clustering ♦ Experimental evaluation ♦ Modularity ♦ Temporal smoothness
Abstract Maximizing the quality index $\textit{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 $\textit{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 $\textit{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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-04-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 18
Page Count 29
Starting Page 1.1
Ending Page 1.29

Open content in new tab

   Open content in new tab
Source: ACM Digital Library