{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:30:24Z","timestamp":1777613424456,"version":"3.51.4"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T00:00:00Z","timestamp":1489104000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["118653 (ALGODAN)"],"award-info":[{"award-number":["118653 (ALGODAN)"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>\n            Online social networks are often defined by considering interactions of entities at an\n            <jats:italic>aggregate<\/jats:italic>\n            level. For example, a\n            <jats:italic>call graph<\/jats:italic>\n            is formed among individuals who have called each other at least once; or at least\n            <jats:italic>k<\/jats:italic>\n            times. Similarly, in social-media platforms, we consider\n            <jats:italic>implicit social networks<\/jats:italic>\n            among users who have interacted in some way, e.g., have made a conversation, have commented to the content of each other, and so on. Such definitions have been used widely in the literature and they have offered significant insights regarding the structure of social networks. However, it is obvious that they suffer from a severe limitation: They neglect the precise time that interactions among the network entities occur.\n          <\/jats:p>\n          <jats:p>\n            In this article, we consider\n            <jats:italic>interaction networks<\/jats:italic>\n            , where the data description contains not only information about the underlying topology of the social network, but also the exact time instances that network entities interact. In an interaction network, an edge is associated with a timestamp, and multiple edges may occur for the same pair of entities. Consequently, interaction networks offer a more fine-grained representation, which can be leveraged to reveal otherwise hidden dynamic phenomena.\n          <\/jats:p>\n          <jats:p>\n            In the setting of interaction networks, we study the problem of discovering\n            <jats:italic>dynamic dense subgraphs<\/jats:italic>\n            whose edges occur in\n            <jats:italic>short time intervals<\/jats:italic>\n            . We view such subgraphs as fingerprints of dynamic activity occurring within network communities. Such communities represent groups of individuals who interact with each other in specific time instances, for example, a group of employees who work on a project and whose interaction intensifies before certain project milestones. We prove that the problem we define is\n            <jats:italic>NP<\/jats:italic>\n            -hard, and we provide efficient algorithms by adapting techniques for finding dense subgraphs. We also show how to speed-up the proposed methods by exploiting\n            <jats:italic>concavity<\/jats:italic>\n            properties of our objective function and by the means of\n            <jats:italic>fractional programming<\/jats:italic>\n            . We perform extensive evaluation of the proposed methods on synthetic and real datasets, which demonstrates the validity of our approach and shows that our algorithms can be used to obtain high-quality results.\n          <\/jats:p>","DOI":"10.1145\/3046791","type":"journal-article","created":{"date-parts":[[2017,3,13]],"date-time":"2017-03-13T12:25:15Z","timestamp":1489407915000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Finding Dynamic Dense Subgraphs"],"prefix":"10.1145","volume":"11","author":[{"given":"Polina","family":"Rozenshtein","sequence":"first","affiliation":[{"name":"Helsinki Institute for Information Technology, Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaj","family":"Tatti","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology, Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aristides","family":"Gionis","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology, Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840359"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of Army Science Conference.","author":"Akoglu Leman","year":"2010"},{"key":"e_1_2_1_3_1","unstructured":"Leman Akoglu Hanghang Tong and Danai Koutra. 2014. Graph-based anomaly detection and description: A survey. Data Mining and Knowledge Discovery 28 4 (2014).  Leman Akoglu Hanghang Tong and Danai Koutra. 2014. Graph-based anomaly detection and description: A survey. Data Mining and Knowledge Discovery 28 4 (2014)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Sitaram Asur Srinivasan Parthasarathy and Duygu Ucar. 2009. An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Transactions on Knowledge Discovery from Data 3 4 (2009) 16:1--16:36.  Sitaram Asur Srinivasan Parthasarathy and Duygu Ucar. 2009. An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Transactions on Knowledge Discovery from Data 3 4 (2009) 16:1--16:36.","DOI":"10.1145\/1631162.1631164"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-4-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3121576.3121605"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-013-0331-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488400"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.101"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541880.1541882"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.13.7.492"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347121"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of VLDB. 181--192","author":"Cheong Fung Gabriel Pui","year":"2005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90135-3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10044-008-0141-y"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339628"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2010.17"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835862"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2012.03.001"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1049"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of KDD.","author":"Ide Tsuyoshi","year":"2004"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150428"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024940629314"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.60"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150476"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401948"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772755"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367590"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Peter J Mucha Thomas Richardson Kevin Macon Mason A. Porter and Jukka-Pekka Onnela. 2010. Community structure in time-dependent multiscale and multiplex networks. Science 328 5980 (2010) 876--878.  Peter J Mucha Thomas Richardson Kevin Macon Mason A. Porter and Jukka-Pekka Onnela. 2010. Community structure in time-dependent multiscale and multiplex networks. Science 328 5980 (2010) 876--878.","DOI":"10.1126\/science.1184819"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568043"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature05670"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13174-010-0003-x"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00124"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Carey E. Priebe John M. Conroy David J. Marchette and Youngser Park. 2005. Scan statistics on enron graphs. Computational 8 Mathematical Organization Theory 11 3 (2005) 229--247.  Carey E. Priebe John M. Conroy David J. Marchette and Youngser Park. 2005. Scan statistics on enron graphs. Computational 8 Mathematical Organization Theory 11 3 (2005) 229--247.","DOI":"10.1007\/s10588-005-5378-z"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms5630"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623674"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the International Conference of Intelligent Systems for Molecular Biology (ISMB)","volume":"8","author":"Sharan Roded","year":"2000"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612184"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281266"},{"key":"e_1_2_1_52_1","unstructured":"Stijn van Dongen. 2000. Graph Clustering by Flow Simulation. Ph.D. Dissertation. University of Utrecht.  Stijn van Dongen. 2000. Graph Clustering by Flow Simulation. Ph.D. Dissertation. University of Utrecht."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007586"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90032-6"},{"key":"e_1_2_1_56_1","unstructured":"Rui Zhou Chengfei Liu Jeffrey Xu Yu Weifa Liang and Yanchun Zhang. 2014. Efficient truss maintenance in evolving networks. arXiv Preprint arXiv:1402.2807 (2014).  Rui Zhou Chengfei Liu Jeffrey Xu Yu Weifa Liang and Yanchun Zhang. 2014. Efficient truss maintenance in evolving networks. arXiv Preprint arXiv:1402.2807 (2014)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956789"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3046791","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3046791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:24Z","timestamp":1750218624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3046791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,10]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3046791"],"URL":"https:\/\/doi.org\/10.1145\/3046791","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,10]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}