{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T17:52:11Z","timestamp":1740160331823,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"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":["Soc. Netw. Anal. Min."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Interactions among entities are usually modeled using graphs. In many real scenarios, these relations may change over time, and different kinds exist among entities that need to be integrated. We introduce a new network model called temporal dual network, to deal with interactions which change over time and to integrate information coming from two different networks. In this new model, we consider a fundamental problem in graph mining, that is, finding the densest subgraphs. To deal with this problem, we propose an approach that, given two temporal graphs, (1) produces a dual temporal graph via alignment and (2) asks for identifying the densest subgraphs in this resulting graph. For this latter problem, we present a polynomial-time dynamic programming algorithm and a faster heuristic based on constraining the dynamic programming to consider only bounded temporal graphs and a local search procedure. We show that our method can output solutions not far from the optimal ones, even for temporal graphs having 10000 vertices and 10000 timestamps. Finally, we present a case study on a real dual temporal network.<\/jats:p>","DOI":"10.1007\/s13278-023-01136-2","type":"journal-article","created":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T05:01:37Z","timestamp":1696568497000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Dense subgraphs in temporal social networks"],"prefix":"10.1007","volume":"13","author":[{"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pietro Hiram","family":"Guzzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad Mehdi","family":"Hosseinzadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marianna","family":"Milano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,6]]},"reference":[{"key":"1136_CR1","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.jcss.2019.08.002","volume":"107","author":"EC Akrida","year":"2020","unstructured":"Akrida EC, Mertzios GB, Spirakis PG, Zamaraev V (2020) Temporal vertex cover with a sliding time window. J Comput Syst Sci 107:108\u2013123","journal-title":"J Comput Syst Sci"},{"key":"1136_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-01284-6_3","volume-title":"Adaptive networks","author":"D Braha","year":"2009","unstructured":"Braha D, Bar-Yam Y (2009) Time-dependent complex networks: Dynamic centrality, dynamic motifs, and cycles of social interactions. Adaptive networks. Springer, Cham, pp 39\u201350"},{"key":"1136_CR3","doi-asserted-by":"crossref","unstructured":"Castelli M, Dondi R, Hosseinzadeh MM (2020) Genetic algorithms for finding episodes in temporal networks. In: Cristani M, Toro C, Zanni-Merk C, Howlett RJ, Jain LC (eds.) Knowledge-based and intelligent information & Engineering systems: proceedings of the 24th international conference KES-2020, Virtual Event, 16-18 September 2020. Procedia Computer Science, vol. 176. Elsevier, pp. 215\u2013224","DOI":"10.1016\/j.procs.2020.08.023"},{"key":"1136_CR4","doi-asserted-by":"crossref","unstructured":"Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. In: Approximation algorithms for combinatorial optimization, third international workshop, APPROX 2000, Proceedings. pp 84\u201395","DOI":"10.1007\/3-540-44436-X_10"},{"issue":"7","key":"1136_CR5","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1109\/TKDE.2010.271","volume":"24","author":"J Chen","year":"2010","unstructured":"Chen J, Saad Y (2010) Dense subgraph extraction with application to community detection. IEEE Trans Knowl Data Eng 24(7):1216\u20131230","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"1136_CR6","doi-asserted-by":"crossref","unstructured":"Chen T, Bonchi F, Garcia-Soriano D, Miyauchi A, Tsourakakis CE (2022) Dense and well-connected subgraph detection in dual networks. In: Proceedings of the 2022 SIAM international conference on data mining (SDM). SIAM, pp 361\u2013369","DOI":"10.1137\/1.9781611977172.41"},{"issue":"1","key":"1136_CR7","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s13721-022-00383-1","volume":"11","author":"P Cinaglia","year":"2022","unstructured":"Cinaglia P, Cannataro M (2022) Network alignment and motif discovery in dynamic networks. Netw Model Anal Health Inform Bioinform 11(1):38","journal-title":"Netw Model Anal Health Inform Bioinform"},{"key":"1136_CR8","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/978-3-031-21131-7_41","volume-title":"Complex networks and their applications XI","author":"R Dondi","year":"2023","unstructured":"Dondi R, Guzzi PH, Hosseinzadeh MM (2023) Integrating temporal graphs via dual networks: dense graph discovery. In: Cherifi H, Mantegna RN, Rocha LM, Cherifi C, Micciche S (eds) Complex networks and their applications XI. Springer International Publishing, Cham, pp 523\u2013535"},{"issue":"3","key":"1136_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s42979-021-00593-w","volume":"2","author":"R Dondi","year":"2021","unstructured":"Dondi R, Hosseinzadeh MM (2021) Dense sub-networks discovery in temporal networks. SN Comput Sci 2(3):1\u201311","journal-title":"SN Comput Sci"},{"issue":"1","key":"1136_CR10","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/s41109-021-00381-8","volume":"6","author":"R Dondi","year":"2021","unstructured":"Dondi R, Hosseinzadeh MM, Guzzi PH (2021) A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks. Appl Netw Sci 6(1):40","journal-title":"Appl Netw Sci"},{"issue":"1","key":"1136_CR11","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 (2021) Top-k overlapping densest subgraphs: approximation algorithms and computational complexity. J Comb Optim 41(1):80\u2013104","journal-title":"J Comb Optim"},{"issue":"5","key":"1136_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 (2016) Top-k overlapping densest subgraphs. Data Min Knowl Discov 30(5):1134\u20131165","journal-title":"Data Min Knowl Discov"},{"issue":"5","key":"1136_CR13","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1038\/s41435-020-00112-6","volume":"21","author":"JC Galicia","year":"2020","unstructured":"Galicia JC, Guzzi PH, Giorgi FM, Khan AA (2020) Predicting the response of the dental pulp to sars-cov2 infection: a transcriptome-wide effect cross-analysis. Genes Immun 21(5):360\u2013363","journal-title":"Genes Immun"},{"key":"1136_CR14","volume-title":"Finding a maximum density subgraph","author":"AV Goldberg","year":"1984","unstructured":"Goldberg AV (1984) Finding a maximum density subgraph. Tech. rep, Berkeley"},{"issue":"9","key":"1136_CR15","doi-asserted-by":"publisher","first-page":"2544","DOI":"10.1093\/bioinformatics\/btac133","volume":"38","author":"S Gu","year":"2022","unstructured":"Gu S, Jiang M, Guzzi PH, Milenkovi\u0107 T (2022) Modeling multi-scale data via a network of networks. Bioinformatics 38(9):2544\u20132553","journal-title":"Bioinformatics"},{"issue":"3","key":"1136_CR16","first-page":"472","volume":"19","author":"PH Guzzi","year":"2018","unstructured":"Guzzi PH, Milenkovi\u0107 T (2018) Survey of local and global biological network alignment: the need to reconcile the two sides of the same coin. Brief Bioinform 19(3):472\u2013481","journal-title":"Brief Bioinform"},{"key":"1136_CR17","doi-asserted-by":"publisher","first-page":"162279","DOI":"10.1109\/ACCESS.2020.3020924","volume":"8","author":"PH Guzzi","year":"2020","unstructured":"Guzzi PH, Salerno E, Tradigo G, Veltri P (2020) Extracting dense and connected communities in dual networks: an alignment based algorithm. IEEE Access 8:162279\u2013162289","journal-title":"IEEE Access"},{"issue":"15","key":"1136_CR18","first-page":"1","volume":"22","author":"PH Guzzi","year":"2021","unstructured":"Guzzi PH, Tradigo G, Veltri P (2021) Using dual-network-analyser for communities detecting in dual networks. BMC Bioinform 22(15):1\u201316","journal-title":"BMC Bioinform"},{"issue":"3","key":"1136_CR19","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme P, Saram\u00e4ki J (2012) Temporal networks. Phys Rep 519(3):97\u2013125","journal-title":"Phys Rep"},{"key":"1136_CR20","first-page":"711","volume-title":"International conference on current trends in theory and practice of informatics","author":"MM Hosseinzadeh","year":"2020","unstructured":"Hosseinzadeh MM (2020) Dense subgraphs in biological networks. International conference on current trends in theory and practice of informatics. Springer, Cham, pp 711\u2013719"},{"issue":"1","key":"1136_CR21","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/s13721-022-00406-x","volume":"12","author":"MM Hosseinzadeh","year":"2023","unstructured":"Hosseinzadeh MM, Cannataro M, Guzzi PH, Dondi R (2023) Temporal networks in biology and medicine: a survey on models, algorithms, and tools. Netw Model Anal Health Inform Bioinform 12(1):10","journal-title":"Netw Model Anal Health Inform Bioinform"},{"issue":"12","key":"1136_CR22","doi-asserted-by":"publisher","first-page":"3461","DOI":"10.1007\/s00453-017-0400-7","volume":"80","author":"Y Kawase","year":"2018","unstructured":"Kawase Y, Miyauchi A (2018) The densest subgraph problem with a convex\/concave size function. Algorithmica 80(12):3461\u20133480","journal-title":"Algorithmica"},{"issue":"4","key":"1136_CR23","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 (2002) Connectivity and inference problems for temporal networks. J Comput Syst Sci 64(4):820\u2013842","journal-title":"J Comput Syst Sci"},{"issue":"6","key":"1136_CR24","doi-asserted-by":"publisher","first-page":"1840","DOI":"10.1007\/s10618-017-0515-0","volume":"31","author":"O Kostakis","year":"2017","unstructured":"Kostakis O, Tatti N, Gionis A (2017) Discovering recurring activity in temporal networks. Data Min Knowl Discov 31(6):1840\u20131871","journal-title":"Data Min Knowl Discov"},{"issue":"1","key":"1136_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-020-60737-5","volume":"10","author":"M Milano","year":"2020","unstructured":"Milano M, Milenkovi\u0107 T, Cannataro M, Guzzi PH (2020) L-hetnetaligner: a novel algorithm for local alignment of heterogeneous biological networks. Sci Rep 10(1):1\u201320","journal-title":"Sci Rep"},{"key":"1136_CR26","doi-asserted-by":"crossref","unstructured":"Rozenshtein P, Gionis A (2019) Mining temporal networks. In: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. ACM, pp 3225\u20133226","DOI":"10.1145\/3292500.3332295"},{"issue":"9","key":"1136_CR27","doi-asserted-by":"publisher","first-page":"721","DOI":"10.14778\/2732939.2732945","volume":"7","author":"H Wu","year":"2014","unstructured":"Wu H, Cheng J, Huang S, Ke Y, Lu Y, Xu Y (2014) Path problems in temporal graphs. Proc VLDB Endow 7(9):721\u2013732","journal-title":"Proc VLDB Endow"},{"key":"1136_CR28","doi-asserted-by":"crossref","unstructured":"Wu Y, Zhu X, Li L, Fan W, Jin R, Zhang X (2016) Mining dual networks - models, algorithms, and applications. TKDD","DOI":"10.1145\/2785970"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-023-01136-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13278-023-01136-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-023-01136-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T21:11:07Z","timestamp":1702588267000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13278-023-01136-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,6]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["1136"],"URL":"https:\/\/doi.org\/10.1007\/s13278-023-01136-2","relation":{},"ISSN":["1869-5469"],"issn-type":[{"type":"electronic","value":"1869-5469"}],"subject":[],"published":{"date-parts":[[2023,10,6]]},"assertion":[{"value":"9 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2023","order":4,"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 they have no financial interests","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"128"}}