{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T11:39:22Z","timestamp":1762429162826,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T00:00:00Z","timestamp":1366329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>\n            Maximizing the quality index\n            <jats:italic>modularity<\/jats:italic>\n            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\n            <jats:italic>modularity<\/jats:italic>\n            -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\n            <jats:italic>modularity<\/jats:italic>\n            than recomputation, guarantees much smoother clustering dynamics, and requires much lower runtimes. We conclude with giving sound recommendations for the choice of an algorithm.\n          <\/jats:p>","DOI":"10.1145\/2444016.2444021","type":"journal-article","created":{"date-parts":[[2013,5,7]],"date-time":"2013-05-07T20:51:42Z","timestamp":1367959902000},"source":"Crossref","is-referenced-by-count":15,"title":["Dynamic graph clustering combining modularity and smoothness"],"prefix":"10.1145","volume":"18","author":[{"given":"Robert","family":"G\u00f6rke","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Germany"}]},{"given":"Pascal","family":"Maillard","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Pierre et Marie Curie, Paris, France"}]},{"given":"Andrea","family":"Schumm","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Germany"}]},{"given":"Christian","family":"Staudt","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Germany"}]}],"member":"320","published-online":{"date-parts":[[2013,4,19]]},"reference":[{"volume-title":"Proceedings of the 5th SIAM International Conference on Data Mining (SDM'05)","author":"Aggarwal C. C.","key":"e_1_2_1_1_1","unstructured":"Aggarwal , C. C. and Yu , P. S . 2005. Online analysis of community evolution in data streams . In Proceedings of the 5th SIAM International Conference on Data Mining (SDM'05) . SIAM. Aggarwal, C. C. and Yu, P. S. 2005. Online analysis of community evolution in data streams. In Proceedings of the 5th SIAM International Conference on Data Mining (SDM'05). SIAM."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190689"},{"key":"e_1_2_1_4_1","volume-title":"Eds","author":"Brandes U.","year":"2005","unstructured":"Brandes , U. and Erlebach , T. , Eds . 2005 . Network Analysis : Methodological Foundations. Springer . Brandes, U. and Erlebach, T., Eds. 2005. Network Analysis: Methodological Foundations. Springer."},{"volume-title":"Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03)","author":"Brandes U.","key":"e_1_2_1_5_1","unstructured":"Brandes , U. , Gaertler , M. , and Wagner , D . 2003. Experiments on graph clustering algorithms . In Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03) . Springer, 568--579. Brandes, U., Gaertler, M., and Wagner, D. 2003. Experiments on graph clustering algorithms. In Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03). Springer, 568--579."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150467"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68880-8_14"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02158-9_14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.81.046106"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00203"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_30"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_37"},{"key":"e_1_2_1_16_1","unstructured":"G\u00f6rke R. Maillard P. Staudt C. and Wagner D. 2010b. Modularity-driven clustering of dynamic graphs. Tech. rep. TR 2010-5 ITI Wagner Department of Informatics Karlsruhe Institute of Technology Informatik Uni Karlsruhe http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000016558.  G\u00f6rke R. Maillard P. Staudt C. and Wagner D. 2010b. Modularity-driven clustering of dynamic graphs. Tech. rep. TR 2010-5 ITI Wagner Department of Informatics Karlsruhe Institute of Technology Informatik Uni Karlsruhe http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000016558."},{"key":"e_1_2_1_17_1","unstructured":"G\u00f6rke R. and Staudt C. 2009. A generator of dynamic clustered random graphs. Tech. rep. TR 2009-7 ITI Wagner Faculty of Informatics Universit\u00e4t Karlsruhe Informatik Uni Karlsruhe http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000012167.  G\u00f6rke R. and Staudt C. 2009. A generator of dynamic clustered random graphs. Tech. rep. TR 2009-7 ITI Wagner Faculty of Informatics Universit\u00e4t Karlsruhe Informatik Uni Karlsruhe http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000012167."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03288"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0307750100"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014077"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.056131"},{"key":"e_1_2_1_23_1","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman M. E. J.","year":"2004","unstructured":"Newman , M. E. J. and Girvan , M. 2004 . Finding and evaluating community structure in networks . Phys. Rev. E 69 , 026113, 1--16. Newman, M. E. J. and Girvan, M. 2004. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 1--16.","journal-title":"Phys. Rev. E"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_24"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature05670"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00124"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"volume-title":"Proceedings of the IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. IEEE, 667--672","author":"Schaeffer S. E.","key":"e_1_2_1_28_1","unstructured":"Schaeffer , S. E. , Marinoni , S. , S\u00e4rel\u00e4 , M. , and Nikander , P . 2006. Dynamic local clustering for hierarchical ad hoc networks . In Proceedings of the IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. IEEE, 667--672 . Schaeffer, S. E., Marinoni, S., S\u00e4rel\u00e4, M., and Nikander, P. 2006. Dynamic local clustering for hierarchical ad hoc networks. In Proceedings of the IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. IEEE, 667--672."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281266"},{"volume-title":"Proceedings of the 6th International Workshop on Pattern Recognition in Information Systems (PRIS'06)","author":"Vazirgiannis M.","key":"e_1_2_1_31_1","unstructured":"Vazirgiannis , M. , N\u00f8rv\u00e5g , K. , and Doulkeridis , C . 2006. Peer-to-peer clustering for semantic overlay network generation . In Proceedings of the 6th International Workshop on Pattern Recognition in Information Systems (PRIS'06) . Vazirgiannis, M., N\u00f8rv\u00e5g, K., and Doulkeridis, C. 2006. Peer-to-peer clustering for semantic overlay network generation. In Proceedings of the 6th International Workshop on Pattern Recognition in Information Systems (PRIS'06)."},{"volume-title":"Proceedings of the 5th SIAM International Conference on Data Mining (SDM'05)","author":"White S.","key":"e_1_2_1_32_1","unstructured":"White , S. and Smyth , P . 2005. A spectral clustering approach to finding communities in graphs . In Proceedings of the 5th SIAM International Conference on Data Mining (SDM'05) . SIAM, 274--285. White, S. and Smyth, P. 2005. A spectral clustering approach to finding communities in graphs. In Proceedings of the 5th SIAM International Conference on Data Mining (SDM'05). SIAM, 274--285."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2444021","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2444016.2444021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:57Z","timestamp":1750236537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2444021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,19]]},"references-count":30,"alternative-id":["10.1145\/2444016.2444021"],"URL":"https:\/\/doi.org\/10.1145\/2444016.2444021","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2013,4,19]]}}}