{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T15:11:34Z","timestamp":1793113894144,"version":"4.5.0"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T00:00:00Z","timestamp":1570060800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T00:00:00Z","timestamp":1570060800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["286211"],"award-info":[{"award-number":["286211"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["313927"],"award-info":[{"award-number":["313927"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["317085"],"award-info":[{"award-number":["317085"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["654024"],"award-info":[{"award-number":["654024"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2020,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>In this paper, we study the problem of discovering a timeline of events in a temporal network. We model events as dense subgraphs that occur within intervals of network activity. We formulate the event discovery task as an optimization problem, where we search for a partition of the network timeline into <jats:italic>k<\/jats:italic> non-overlapping intervals, such that the intervals span subgraphs with maximum total density. The output is a sequence of dense subgraphs along with corresponding time intervals, capturing the most interesting events during the network lifetime. A na\u00efve solution to our optimization problem has polynomial but prohibitively high running time. We adapt existing recent work on dynamic densest subgraph discovery and approximate dynamic programming to design a fast approximation algorithm. Next, to ensure richer structure, we adjust the problem formulation to encourage coverage of a larger set of nodes. This problem is <jats:bold>NP<\/jats:bold>-hard; however, we show that on static graphs a simple greedy algorithm leads to approximate solution due to submodularity. We extend this greedy approach for temporal networks, but we lose the approximation guarantee in the process. Finally, we demonstrate empirically that our algorithms recover solutions with good quality.<\/jats:p>","DOI":"10.1007\/s10115-019-01403-9","type":"journal-article","created":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T06:03:31Z","timestamp":1570082611000},"page":"1611-1639","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Finding events in temporal networks: segmentation meets densest subgraph discovery"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1714-5567","authenticated-orcid":false,"given":"Polina","family":"Rozenshtein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aristides","family":"Gionis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mauro","family":"Sozio","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikolaj","family":"Tatti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,10,3]]},"reference":[{"key":"1403_CR1","unstructured":"Alvarez-Hamelin J\u00a0I, Dall\u2019Asta L, Barrat A, Vespignani A (2006) Large scale networks fingerprinting and visualization using the k-core decomposition. In: NIPS"},{"key":"1403_CR2","doi-asserted-by":"crossref","unstructured":"Andersen R, Chellapilla K (2009) Finding dense subgraphs with size bounds. In: WAW, pp 25\u201337","DOI":"10.1007\/978-3-540-95995-3_3"},{"issue":"6","key":"1403_CR3","first-page":"574","volume":"5","author":"A Angel","year":"2012","unstructured":"Angel A, Sarkas N, Koudas N, Srivastava D (2012) Dense subgraph maintenance under streaming edge weight updates for real-time story identification. PLVDB 5(6):574\u2013585","journal-title":"PLVDB"},{"issue":"2","key":"1403_CR4","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jagm.1999.1062","volume":"34","author":"Y Asahiro","year":"2000","unstructured":"Asahiro Y, Iwama K, Tamaki H, Tokuyama T (2000) Greedily finding a dense subgraph. J Algorithms 34(2):203\u2013221","journal-title":"J Algorithms"},{"issue":"4","key":"1403_CR5","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/1631162.1631164","volume":"3","author":"S Asur","year":"2009","unstructured":"Asur S, Parthasarathy S, Ucar D (2009) An event-based framework for characterizing the evolutionary behavior of interaction graphs. TKDD 3(4):16","journal-title":"TKDD"},{"key":"1403_CR6","doi-asserted-by":"crossref","unstructured":"Backstrom L, Huttenlocher D, Kleinberg J, Lan X (2006) Group formation in large social networks: membership, growth, and evolution. In: KDD, pp 44\u201354","DOI":"10.1145\/1150402.1150412"},{"key":"1403_CR7","doi-asserted-by":"crossref","unstructured":"Balalau OD, Bonchi F, Chan T, Gullo F, Sozio M (2015) Finding subgraphs with maximum total density and limited overlap. In: WSDM, pp 379\u2013388","DOI":"10.1145\/2684822.2685298"},{"key":"1403_CR8","unstructured":"Balalau O\u00a0D, Castillo C, Sozio M (2018) Evidense: a graph-based method for finding unique high-impact events with succinct keyword-based descriptions. In: Proceedings of the twelfth international conference on web and social media, ICWSM, pp 560\u2013563"},{"key":"1403_CR9","unstructured":"Bellman R (2013) Dynamic programming, Courier Corporation"},{"key":"1403_CR10","doi-asserted-by":"crossref","unstructured":"Bellman R, Kotkin B (1962) On the approximation of curves by line segments using dynamic programming. II, Technical report, RAND CORP SANTA MONICA CALIF","DOI":"10.1145\/366573.366611"},{"key":"1403_CR11","doi-asserted-by":"crossref","unstructured":"Berlingerio M, Bonchi F, Bringmann B, Gionis A (2009) Mining graph evolution rules. In: ECML PKDD, pp\u00a0115\u2013130","DOI":"10.1007\/978-3-642-04180-8_25"},{"issue":"3","key":"1403_CR12","first-page":"294","volume":"27","author":"M Berlingerio","year":"2013","unstructured":"Berlingerio M, Pinelli F, Calabrese F (2013) Abacus: frequent pattern mining-based community discovery in multidimensional networks. DMKD 27(3):294\u2013320","journal-title":"DMKD"},{"key":"1403_CR13","doi-asserted-by":"crossref","unstructured":"Beutel A, Xu W, Guruswami V, Palow C, Faloutsos C (2013) Copycatch: stopping group attacks by spotting lockstep behavior in social networks. In: WWW, pp\u00a0119\u2013130","DOI":"10.1145\/2488388.2488400"},{"key":"1403_CR14","doi-asserted-by":"crossref","unstructured":"Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C (2015) Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: STOC, pp\u00a0173\u2013182","DOI":"10.1145\/2746539.2746592"},{"key":"1403_CR15","doi-asserted-by":"crossref","unstructured":"Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. In: APPROX, pp 84\u201395","DOI":"10.1007\/3-540-44436-X_10"},{"issue":"7","key":"1403_CR16","first-page":"1216","volume":"24","author":"J Chen","year":"2012","unstructured":"Chen J, Saad Y (2012) Dense subgraph extraction with application to community detection. TKDE 24(7):1216\u20131230","journal-title":"TKDE"},{"key":"1403_CR17","doi-asserted-by":"crossref","unstructured":"Danisch M, Chan T\u00a0H, Sozio M (2017) Large scale density-friendly graph decomposition via convex programming. In: Proceedings of the 26th international conference on World Wide Web, WWW 2017","DOI":"10.1145\/3038912.3052619"},{"key":"1403_CR18","doi-asserted-by":"crossref","unstructured":"DiTursi D, Ghosh G, Bogdanov P (2017) Local community detection in dynamic networks. \narXiv:1709.04033","DOI":"10.1109\/ICDM.2017.103"},{"key":"1403_CR19","doi-asserted-by":"crossref","unstructured":"Epasto A, Lattanzi S, Sozio M (2015) Efficient densest subgraph computation in evolving graphs. In: WWW, pp\u00a0300\u2013310","DOI":"10.1145\/2736277.2741638"},{"key":"1403_CR20","unstructured":"Esfandiari H, Hajiaghayi M, Woodruff D (2015) Applications of uniform sampling: Densest subgraph and beyond. \narXiv:1506.04505"},{"issue":"2","key":"1403_CR21","first-page":"261","volume":"51","author":"T Feder","year":"1995","unstructured":"Feder T, Motwani R (1995) Clique partitions, graph compression and speeding-up algorithms. JCSS 51(2):261\u2013272","journal-title":"JCSS"},{"issue":"14","key":"1403_CR22","doi-asserted-by":"publisher","first-page":"e150","DOI":"10.1093\/bioinformatics\/btl243","volume":"22","author":"E Fratkin","year":"2006","unstructured":"Fratkin E, Naughton BT, Brutlag DL, Batzoglou S (2006) Motifcut: regulatory motifs finding with maximum density subgraphs. Bioinformatics 22(14):e150\u2013e157","journal-title":"Bioinformatics"},{"issue":"5\u20136","key":"1403_CR23","first-page":"1586","volume":"28","author":"E Galbrun","year":"2014","unstructured":"Galbrun E, Gionis A, Tatti N (2014) Overlapping community detection in labeled graphs. DMKD 28(5\u20136):1586\u20131610","journal-title":"DMKD"},{"issue":"5","key":"1403_CR24","first-page":"1134","volume":"30","author":"E Galbrun","year":"2016","unstructured":"Galbrun E, Gionis A, Tatti N (2016) Top-$$k$$ overlapping densest subgraphs. DMKD 30(5):1134\u20131165","journal-title":"DMKD"},{"key":"1403_CR25","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo G, Grigoriadis MD, Tarjan RE (1989) A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18:30\u201355","journal-title":"SIAM J. Comput."},{"key":"1403_CR26","unstructured":"Gibson D, Kumar R, Tomkins A (2005) Discovering large dense subgraphs in massive graphs. In: PVLDB, pp\u00a0721\u2013732"},{"key":"1403_CR27","unstructured":"Goldberg A\u00a0V (1984) Finding a maximum density subgraph, University of California Berkeley"},{"key":"1403_CR28","doi-asserted-by":"crossref","unstructured":"Greene D, Doyle D, Cunningham P (2010) Tracking the evolution of communities in dynamic social networks. In: ASONAM","DOI":"10.1109\/ASONAM.2010.17"},{"key":"1403_CR29","doi-asserted-by":"crossref","unstructured":"Guha S, Koudas N, Shim K (2001) Data-streams and histograms. In: STOC, pp\u00a0471\u2013475","DOI":"10.1145\/380752.380841"},{"key":"1403_CR30","doi-asserted-by":"crossref","unstructured":"Hern\u00e1ndez C, Navarro G (2012) Compressed representation of web and social networks via dense subgraphs. In: SIGIR, pp\u00a0264\u2013276","DOI":"10.1007\/978-3-642-34109-0_28"},{"key":"1403_CR31","doi-asserted-by":"crossref","unstructured":"Jethava V, Beerenwinkel N (2015) Finding dense subgraphs in relational graphs. In: ECML PKDD, pp\u00a0641\u2013654","DOI":"10.1007\/978-3-319-23525-7_39"},{"key":"1403_CR32","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1080\/15427951.2009.10390646","volume":"6","author":"C Karande","year":"2009","unstructured":"Karande C, Chellapilla K, Andersen R (2009) Speeding up algorithms on compressed web graphs. Internet Math 6:373\u2013398","journal-title":"Internet Math"},{"key":"1403_CR33","doi-asserted-by":"crossref","unstructured":"Khuller S, Saha B (2009) On finding dense subgraphs. In: ICALP","DOI":"10.1007\/978-3-642-02927-1_50"},{"issue":"10","key":"1403_CR34","first-page":"2453","volume":"26","author":"R-H Li","year":"2014","unstructured":"Li R-H, Yu JX, Mao R (2014) Efficient core maintenance in large dynamic graphs. TKDE 26(10):2453\u20132465","journal-title":"TKDE"},{"key":"1403_CR35","unstructured":"Lin H, Bilmes J (2011) A class of submodular functions for document summarization. In: ACL, pp 510\u2013520"},{"key":"1403_CR36","unstructured":"Lin Y-R, Chi Y, Zhu S, Sundaram H, Tseng B\u00a0L (2008) Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In: WWW, pp\u00a0685\u2013694"},{"key":"1403_CR37","doi-asserted-by":"crossref","unstructured":"Makino K, Uno T (2004) New algorithms for enumerating all maximal cliques. In: SWAT, pp\u00a0260\u2013272","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"1403_CR38","doi-asserted-by":"crossref","unstructured":"McGregor A, Tench D, Vorotnikova S, Vu HT (2015) Densest subgraph in dynamic graph streams. In: MFCS. Springer, Berlin","DOI":"10.1007\/978-3-662-48054-0_39"},{"key":"1403_CR39","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M, Pachocki J, Peng R, Tsourakakis C, Xu SC (2015) Scalable large near-clique detection in large-scale networks via sampling. In: KDD, pp\u00a0815\u2013824","DOI":"10.1145\/2783258.2783385"},{"issue":"5980","key":"1403_CR40","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1126\/science.1184819","volume":"328","author":"PJ Mucha","year":"2010","unstructured":"Mucha PJ, Richardson T, Macon K, Porter MA, Onnela J-P (2010) Community structure in time-dependent, multiscale, and multiplex networks. Science 328(5980):876\u2013878","journal-title":"Science"},{"key":"1403_CR41","unstructured":"Myers SA, Leskovec J (2014) The bursty dynamics of the twitter information network. In: WWW, pp\u00a0913\u2013924"},{"issue":"1","key":"1403_CR42","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G Nemhauser","year":"1978","unstructured":"Nemhauser G, Wolsey L, Fisher M (1978) An analysis of approximations for maximizing submodular set functions. Math Progr 14(1):265\u2013294","journal-title":"Math Progr"},{"key":"1403_CR43","doi-asserted-by":"crossref","unstructured":"Orlin JB (2013) Max flows in o (nm) time, or better. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing","DOI":"10.1145\/2488608.2488705"},{"issue":"3","key":"1403_CR44","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/3046791","volume":"11","author":"P Rozenshtein","year":"2017","unstructured":"Rozenshtein P, Tatti N, Gionis A (2017) Finding dynamic dense subgraphs. TKDD 11(3):27","journal-title":"TKDD"},{"key":"1403_CR45","doi-asserted-by":"crossref","unstructured":"Saha B, Hoch A, Khuller S, Raschid L, Zhang X-N (2010) Dense subgraphs with restrictions and applications to gene annotation graphs. In: RECOMB","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"1403_CR46","doi-asserted-by":"crossref","unstructured":"Semertzidis K, Pitoura E, Terzi E, Tsaparas P (2018) Finding lasting dense subgraphs. Data Mining and Knowledge Discovery","DOI":"10.1007\/s10618-018-0602-x"},{"key":"1403_CR47","unstructured":"Tatti N (2018) Strongly polynomial efficient approximation scheme for segmentation. \narXiv:1805.11170"},{"issue":"3","key":"1403_CR48","first-page":"031056","volume":"7","author":"D Taylor","year":"2017","unstructured":"Taylor D, Caceres RS, Mucha PJ (2017) Super-resolution community detection for layer-aggregated multilayer networks. Phys Rev X 7(3):031056","journal-title":"Phys Rev X"},{"key":"1403_CR49","doi-asserted-by":"crossref","unstructured":"Tsourakakis C, Bonchi F, Gionis A, Gullo F, Tsiarli M (2013) Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: KDD, pp\u00a0104\u2013112","DOI":"10.1145\/2487575.2487645"},{"key":"1403_CR50","unstructured":"Tsourakakis CE (2014) A novel approach to finding near-cliques: the triangle-densest subgraph problem. \narXiv:1405.1477"},{"key":"1403_CR51","doi-asserted-by":"crossref","unstructured":"Viswanath B, Mislove A, Cha M, Gummadi K (2009) On the evolution of user interaction in facebook, In: WOSN, pp\u00a037\u201342","DOI":"10.1145\/1592665.1592675"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-019-01403-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-019-01403-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-019-01403-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,1]],"date-time":"2020-10-01T23:43:57Z","timestamp":1601595837000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-019-01403-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,3]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["1403"],"URL":"https:\/\/doi.org\/10.1007\/s10115-019-01403-9","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,3]]},"assertion":[{"value":"5 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}