{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T21:04:24Z","timestamp":1776287064831,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100015968","name":"Universit\u00e0 degli studi di Bergamo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100015968","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Temporal networks have been successfully applied to analyse dynamics of networks. In this paper we focus on an approach recently introduced to identify dense subgraphs in a temporal network and we present a heuristic, based on the local search technique, for the problem. The experimental results we present on synthetic and real-world datasets show that our heuristic provides mostly better solutions (denser solutions) and that the heuristic is fast (comparable with the fastest method in literature, which is outperformed in terms of quality of the solutions). We present also experimental results of two variants of our method based on two different subroutines to compute a dense subgraph of a given graph.<\/jats:p>","DOI":"10.1007\/s42979-021-00593-w","type":"journal-article","created":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T15:02:47Z","timestamp":1616252567000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Dense Sub-networks Discovery in Temporal Networks"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6124-2965","authenticated-orcid":false,"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3275-6286","authenticated-orcid":false,"given":"Mohammad Mehdi","family":"Hosseinzadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,20]]},"reference":[{"issue":"2","key":"593_CR1","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s00778-013-0340-z","volume":"23","author":"A Angel","year":"2014","unstructured":"Angel A, Koudas N, Sarkas N, Srivastava D, Svendsen M, Tirthapura S. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. VLDB J. 2014;23(2):175\u201399.","journal-title":"VLDB J"},{"key":"593_CR2","doi-asserted-by":"publisher","unstructured":"Asahiro Y, Iwama K, Tamaki H, Tokuyama T. Greedily finding a dense subgraph. In: Algorithm Theory - SWAT \u201996, 5th Scandinavian Workshop on Algorithm Theory, Reykjav\u00edk, Iceland, July 3-5, 1996, Proceedings; 1996. p. 136\u201348. https:\/\/doi.org\/10.1007\/3-540-61422-2_127.","DOI":"10.1007\/3-540-61422-2_127"},{"key":"593_CR3","doi-asserted-by":"crossref","unstructured":"Backurs A, Roditty L, Segal G, Williams VV, Wein N. Towards tight approximation bounds for graph diameter and eccentricities. In: Diakonikolas I, Kempe D, Henzinger M, editors. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25\u201329, 2018. ACM; 2018. p. 267\u201380.","DOI":"10.1145\/3188745.3188950"},{"key":"593_CR4","doi-asserted-by":"publisher","unstructured":"Balalau OD, Bonchi F, Chan TH, Gullo F, Sozio M. Finding subgraphs with maximum total density and limited overlap. In: Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, WSDM. 2015. p. 379\u201388. https:\/\/doi.org\/10.1145\/2684822.2685298.","DOI":"10.1145\/2684822.2685298"},{"key":"593_CR5","doi-asserted-by":"crossref","unstructured":"Charikar M. Greedy approximation algorithms for finding dense components in a graph. In: Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Proceedings. 2000. p. 84\u201395.","DOI":"10.1007\/3-540-44436-X_10"},{"issue":"5","key":"593_CR6","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1002\/sam.10133","volume":"4","author":"M Coscia","year":"2011","unstructured":"Coscia M, Giannotti F, Pedreschi D. A classification for community discovery methods in complex networks. Stat Anal Data Min ASA Data Sci J. 2011;4(5):512\u201346.","journal-title":"Stat Anal Data Min ASA Data Sci J"},{"issue":"1","key":"593_CR7","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/s10878-020-00664-3","volume":"41","author":"R Dondi","year":"2021","unstructured":"Dondi R, Hosseinzadeh MM, Mauri G, Zoppis I. Top-k overlapping densest subgraphs: approximation algorithms and computational complexity. J Comb Optim. 2021;41(1):80\u2013104. https:\/\/doi.org\/10.1007\/s10878-020-00664-3.","journal-title":"J Comb Optim"},{"key":"593_CR8","doi-asserted-by":"crossref","unstructured":"Duhan N, Sharma A, Bhatia KK. Page ranking algorithms: a survey. In: 2009 IEEE International Advance Computing Conference. IEEE; 2009. p. 1530\u20131537.","DOI":"10.1109\/IADCC.2009.4809246"},{"key":"593_CR9","doi-asserted-by":"crossref","unstructured":"Epasto A, Lattanzi S, Sozio M. Efficient densest subgraph computation in evolving graphs. In: Proceedings of the 24th International Conference on World Wide Web, International World Wide Web Conferences Steering Committee. 2015. p. 300\u2013310.","DOI":"10.1145\/2736277.2741638"},{"key":"593_CR10","unstructured":"Ferraz\u00a0Costa A, Yamaguchi Y, Juci Machado\u00a0Traina A, Traina\u00a0Jr C, Faloutsos C. Rsc: Mining and modeling temporal activity in social media. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM; 2015. p. 269\u2013278."},{"issue":"3\u20135","key":"593_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato S. Community detection in graphs. Phys Rep. 2010;486(3\u20135):75\u2013174.","journal-title":"Phys Rep"},{"issue":"5","key":"593_CR12","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1007\/s10618-016-0464-z","volume":"30","author":"E Galbrun","year":"2016","unstructured":"Galbrun E, Gionis A, Tatti N. Top-k overlapping densest subgraphs. Data Min Knowl Discov. 2016;30(5):1134\u201365. https:\/\/doi.org\/10.1007\/s10618-016-0464-z.","journal-title":"Data Min Knowl Discov"},{"issue":"2","key":"593_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/1117454.1117456","volume":"7","author":"L Getoor","year":"2005","unstructured":"Getoor L, Diehl CP. Link mining: a survey. ACM SIGKDD Explor Newsl. 2005;7(2):3\u201312.","journal-title":"ACM SIGKDD Explor Newsl"},{"key":"593_CR14","unstructured":"Goldberg AV. Finding a maximum density subgraph. Tech. rep., Berkeley, CA, USA. 1984."},{"issue":"9","key":"593_CR15","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1140\/epjb\/e2015-60657-4","volume":"88","author":"P Holme","year":"2015","unstructured":"Holme P. Modern temporal network theory: a colloquium. Eur Phys J B. 2015;88(9):234.","journal-title":"Eur Phys J B"},{"key":"593_CR16","doi-asserted-by":"crossref","unstructured":"Hosseinzadeh MM. A new heuristic to find overlapping dense subgraphs in biological networks. Proceeding of Current Trends in Theory and Practice of Computer Science p to appear. 2020.","DOI":"10.1007\/978-3-030-38919-2_60"},{"issue":"4","key":"593_CR17","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe D, Kleinberg J, Kumar A. Connectivity and inference problems for temporal networks. J Comput Syst Sci. 2002;64(4):820\u201342.","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"593_CR18","doi-asserted-by":"publisher","first-page":"e86197","DOI":"10.1371\/journal.pone.0086197","volume":"9","author":"D Kondor","year":"2014","unstructured":"Kondor D, P\u00f3sfai M, Csabai I, Vattay G. Do the rich get richer? an empirical analysis of the bitcoin transaction network. PLoS One. 2014;9(2):e86197.","journal-title":"PLoS One"},{"key":"593_CR19","doi-asserted-by":"publisher","first-page":"P11005","DOI":"10.1088\/1742-5468\/2011\/11\/P11005","volume":"11","author":"L Kovanen","year":"2011","unstructured":"Kovanen L, Karsai M, Kaski K, Kert\u00e9sz J. Saram\u00e4ki J (2011) Temporal motifs in time-dependent networks. J Stat Mech Theory Exp. 2011;11:P11005.","journal-title":"J Stat Mech Theory Exp"},{"issue":"8","key":"593_CR20","doi-asserted-by":"publisher","first-page":"083038","DOI":"10.1088\/1367-2630\/16\/8\/083038","volume":"16","author":"MX Li","year":"2014","unstructured":"Li MX, Palchykov V, Jiang ZQ, Kaski K, Kert\u00e9sz J, Miccich\u00e8 S, Tumminello M, Zhou WX, Mantegna RN. Statistically validated mobile communication networks: the evolution of motifs in european and chinese data. New J Phys. 2014;16(8):083038.","journal-title":"New J Phys"},{"key":"593_CR21","doi-asserted-by":"publisher","unstructured":"McGregor A, Tench D, Vorotnikova S, Vu HT. Densest subgraph in dynamic graph streams. In: Italiano GF, Pighizzini G, Sannella D, editors. Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, Springer, Lecture Notes in Computer Science, vol. 9235. 2015. p. 472\u201382. https:\/\/doi.org\/10.1007\/978-3-662-48054-0_39.","DOI":"10.1007\/978-3-662-48054-0_39"},{"key":"593_CR22","doi-asserted-by":"publisher","unstructured":"Nasir MAU, Gionis A, Morales GDF, Girdzijauskas S. Fully dynamic algorithm for top-k densest subgraphs. In: Lim E, Winslett M, Sanderson M, Fu AW, Sun J, Culpepper JS, Lo E, Ho JC, Donato D, Agrawal R, Zheng Y, Castillo C, Sun A, Tseng VS, Li C, editors. Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, Singapore, November 06 - 10, 2017. ACM; 2017. p. 1817\u201326. https:\/\/doi.org\/10.1145\/3132847.3132966.","DOI":"10.1145\/3132847.3132966"},{"issue":"2","key":"593_CR23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/3172867","volume":"51","author":"G Rossetti","year":"2018","unstructured":"Rossetti G, Cazabet R. Community discovery in dynamic networks: a survey. ACM Comput Surv (CSUR). 2018;51(2):35.","journal-title":"ACM Comput Surv (CSUR)"},{"key":"593_CR24","doi-asserted-by":"crossref","unstructured":"Rozenshtein P, Gionis A. Mining temporal networks. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM; 2019. p. 3225\u20133226.","DOI":"10.1145\/3292500.3332295"},{"key":"593_CR25","doi-asserted-by":"crossref","unstructured":"Rozenshtein P, Bonchi F, Gionis A, Sozio M, Tatti N. Finding events in temporal networks: Segmentation meets densest subgraph discovery. Knowledge and Information Systems. 2019.","DOI":"10.1109\/ICDM.2018.00055"},{"key":"593_CR26","doi-asserted-by":"publisher","first-page":"79","DOI":"10.3389\/fphy.2015.00079","volume":"3","author":"C Sanli","year":"2015","unstructured":"Sanli C, Lambiotte R. Temporal pattern of online communication spike trains in spreading a scientific rumor: how often, who interacts with whom? Front Phys. 2015;3:79.","journal-title":"Front Phys"},{"key":"593_CR27","doi-asserted-by":"crossref","unstructured":"Wackersreuther B, Wackersreuther P, Oswald A, B\u00f6hm C, Borgwardt KM. Frequent subgraph discovery in dynamic networks. In: Proceedings of the Eighth Workshop on Mining and Learning with Graphs. ACM; 2010. p. 155\u2013162.","DOI":"10.1145\/1830252.1830272"},{"key":"593_CR28","doi-asserted-by":"crossref","unstructured":"Zhao B, Wang W, Xue G, Yuan N, Tian Q. An empirical analysis on temporal pattern of credit card trade. In: International Conference in Swarm Intelligence. Springer; 2015. p. 63\u201370.","DOI":"10.1007\/978-3-319-20472-7_7"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00593-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-021-00593-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00593-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T17:26:21Z","timestamp":1620926781000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-021-00593-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,20]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["593"],"URL":"https:\/\/doi.org\/10.1007\/s42979-021-00593-w","relation":{},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,20]]},"assertion":[{"value":"5 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest\/Competing interests"}},{"value":"Code is available on request.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"We give our consent to participate.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"We give our consent for the publication.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"158"}}