| Autor: |
Pascal Maillard, Robert Görke, Christian L. Staudt, Dorothea Wagner, Andrea Schumm |
| Rok vydání: |
2013 |
| Předmět: |
|
| Zdroj: |
ACM Journal of Experimental Algorithmics. 18 |
| ISSN: |
1084-6654 |
| DOI: |
10.1145/2444016.2444021 |
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
