{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T20:05:32Z","timestamp":1769371532766,"version":"3.49.0"},"reference-count":90,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,2,28]]},"abstract":"<jats:p>\n            When analyzing temporal networks, a fundamental task is the identification of dense structures (i.e., groups of vertices that exhibit a large number of links), together with their temporal span (i.e., the period of time for which the high density holds). In this article, we tackle this task by introducing a notion of temporal core decomposition where each core is associated with two quantities, its coreness, which quantifies how densely it is connected, and its span, which is a temporal interval: we call such cores\n            <jats:italic>span-cores<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            For a temporal network defined on a discrete temporal domain\n            <jats:italic>T<\/jats:italic>\n            , the total number of time intervals included in\n            <jats:italic>T<\/jats:italic>\n            is quadratic in |\n            <jats:italic>T<\/jats:italic>\n            |, so that the total number of span-cores is potentially quadratic in |\n            <jats:italic>T<\/jats:italic>\n            | as well. Our first main contribution is an algorithm that, by exploiting containment properties among span-cores, computes all the span-cores efficiently. Then, we focus on the problem of finding only the\n            <jats:italic>maximal span-cores<\/jats:italic>\n            , i.e., span-cores that are not dominated by any other span-core by both their coreness property and their span. We devise a very efficient algorithm that exploits theoretical findings on the maximality condition to directly extract the maximal ones without computing all span-cores.\n          <\/jats:p>\n          <jats:p>\n            Finally, as a third contribution, we introduce the problem of\n            <jats:italic>temporal community search<\/jats:italic>\n            , where a set of query vertices is given as input, and the goal is to find a set of densely-connected subgraphs containing the query vertices and covering the whole underlying temporal domain\n            <jats:italic>T<\/jats:italic>\n            . We derive a connection between this problem and the problem of finding (maximal) span-cores. Based on this connection, we show how temporal community search can be solved in polynomial-time via dynamic programming, and how the maximal span-cores can be profitably exploited to significantly speed-up the basic algorithm.\n          <\/jats:p>\n          <jats:p>We provide an extensive experimentation on several real-world temporal networks of widely different origins and characteristics. Our results confirm the efficiency and scalability of the proposed methods. Moreover, we showcase the practical relevance of our techniques in a number of applications on temporal networks, describing face-to-face contacts between individuals in schools. Our experiments highlight the relevance of the notion of (maximal) span-core in analyzing social dynamics, detecting\/correcting anomalies in the data, and graph-embedding-based network classification.<\/jats:p>","DOI":"10.1145\/3418226","type":"journal-article","created":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T19:04:16Z","timestamp":1607367856000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Span-core Decomposition for Temporal Networks"],"prefix":"10.1145","volume":"15","author":[{"given":"Edoardo","family":"Galimberti","sequence":"first","affiliation":[{"name":"ISI Foundation and University of Turin, Turin, Italy"}]},{"given":"Martino","family":"Ciaperoni","sequence":"additional","affiliation":[{"name":"Aalto University, Aalto, Finland"}]},{"given":"Alain","family":"Barrat","sequence":"additional","affiliation":[{"name":"Aix Marseille Univ, Universit\u00e9 de Toulon, CNRS, CPT and ISI Foundation, Turin, Italy"}]},{"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[{"name":"ISI Foundation and Eurecat, Barcelona, Spain"}]},{"given":"Ciro","family":"Cattuto","sequence":"additional","affiliation":[{"name":"University of Turin and ISI Foundation, Turin, Italy"}]},{"given":"Francesco","family":"Gullo","sequence":"additional","affiliation":[{"name":"UniCredit, Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2020,12,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.5"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 18th International Conference on Advances in Neural Information Processing Systems (NeurIPS\u201906)","author":"Alvarez-Hamelin J. Ignacio","year":"2006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 15th International Conference on World Wide Web (WWW\u201906)","author":"Andersen Reid"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_2_1_6_1","volume-title":"Hogue","author":"Bader Gary D.","year":"2003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0422-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46648-7_9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11634-010-0079-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/366573.366611"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3382225.3382234"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04180-8_25"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00016"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.101"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2016.0032"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.3233\/WEB-190412"},{"key":"e_1_2_1_17_1","volume-title":"Chromatic correlation clustering. ACM Transactions on Knowledge Discovery from Data 9, 4","author":"Bonchi Francesco","year":"2015"},{"key":"e_1_2_1_18_1","volume-title":"Encyclopedia of Social Network Analysis and Mining","author":"Bonchi Francesco","edition":"2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2010.91"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_2_1_22_1","volume-title":"On finding dense common subgraphs. CoRR abs\/1802.06361","author":"Charikar Moses","year":"2018"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612179"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935867"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33492-4_11"},{"key":"e_1_2_1_27_1","volume-title":"Multilayer Social Networks","author":"Dickison Mark E."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.88.062819"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313660"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11192-012-0796-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014068"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271767"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132993"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/14\/8\/083030"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512946"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0086028"},{"key":"e_1_2_1_43_1","volume-title":"Mitigation of infectious disease at school: Targeted class closure vs school closure.BMC Infectious Diseases 14, 1","author":"Gemmetto Valerio","year":"2014"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0539-0"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2018.03.022"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 4th International Workshop on Algorithms and Models for the Web-Graph (WAW\u201906)","author":"Healy John","year":"2006"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2016.7752255"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.211"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.41"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23525-7_39"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1746"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining (KDD\u201914)","author":"Isabel"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1032"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2011\/11\/P11005"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871468"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00077"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the World Wide Web Conference (WWW\u201919)","author":"Liu Boge","year":"2019"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290988"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.95"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00587-4"},{"key":"e_1_2_1_65_1","volume-title":"Specificity and stability in topology of protein networks. Science 296, 5569","author":"Maslov Sergei","year":"2002"},{"key":"e_1_2_1_66_1","volume-title":"Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys. PLOS ONE 10, 9 (09","author":"Mastrandrea Rossana","year":"2015"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_68_1","volume-title":"Singh","author":"Mongiovi Misael","year":"2013"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00055"},{"key":"e_1_2_1_73_1","volume-title":"Finding dynamic dense subgraphs. ACM Transactions on Knowledge Discovery from Data 11, 3","author":"Rozenshtein Polina","year":"2017"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749449"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132991"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2015.128"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-018-0602-x"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2013.08.003"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0023176"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-017-0528-8"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150448"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.030"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363809"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1002\/pmic.200400962"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313719"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115406"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-009-0299-0"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.07.006"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418226","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:36Z","timestamp":1750195896000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418226"}},"subtitle":["Algorithms and Applications"],"short-title":[],"issued":{"date-parts":[[2020,12,7]]},"references-count":90,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,28]]}},"alternative-id":["10.1145\/3418226"],"URL":"https:\/\/doi.org\/10.1145\/3418226","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,7]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}