{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T11:08:44Z","timestamp":1770548924187,"version":"3.49.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,6,5]],"date-time":"2021-06-05T00:00:00Z","timestamp":1622851200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,5]],"date-time":"2021-06-05T00:00:00Z","timestamp":1622851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003407","name":"MIUR","doi-asserted-by":"crossref","award":["PON-VQA"],"award-info":[{"award-number":["PON-VQA"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The use of networks for modelling and analysing relations among data is currently growing. Recently, the use of a single networks for capturing all the aspects of some complex scenarios has shown some limitations. Consequently, it has been proposed to use Dual Networks (DN), a pair of related networks, to analyse complex systems. The two graphs in a DN have the same set of vertices and different edge sets. Common subgraphs among these networks may convey some insights about the modelled scenarios. For instance, the detection of the Top-k Densest Connected subgraphs, i.e. a set k subgraphs having the largest density in the conceptual network which are also connected in the physical network, may reveal set of highly related nodes. After proposing a formalisation of the approach, we propose a heuristic to find a solution, since the problem is computationally hard. A set of experiments on synthetic and real networks is also presented to support our approach.<\/jats:p>","DOI":"10.1007\/s41109-021-00381-8","type":"journal-article","created":{"date-parts":[[2021,6,5]],"date-time":"2021-06-05T20:02:43Z","timestamp":1622923363000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks"],"prefix":"10.1007","volume":"6","author":[{"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad Mehdi","family":"Hosseinzadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5542-2997","authenticated-orcid":false,"given":"Pietro H.","family":"Guzzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,5]]},"reference":[{"key":"381_CR1","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1186\/1471-2105-10-275","volume":"10","author":"L Abatangelo","year":"2009","unstructured":"Abatangelo L, Maglietta R, Distaso A, D\u2019Addabbo A, Creanza TM, Mukherjee S, Ancona N (2009) Comparative study of gene set enrichment methods. BMC Bioinform 10:275. https:\/\/doi.org\/10.1186\/1471-2105-10-275","journal-title":"BMC Bioinform"},{"issue":"2","key":"381_CR2","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"},{"key":"381_CR3","doi-asserted-by":"publisher","unstructured":"Balalau OD, Bonchi F, Chan T-H, Gullo F, Sozio M (2015) Finding subgraphs with maximum total density and limited overlap. In: Cheng, X., Li, H., Gabrilovich, E., Tang, J. (eds.) Proceedings of the eighth ACM international conference on web search and data mining, WSDM 2015, Shanghai, China, February 2\u20136, 2015. ACM, pp 379\u2013388. https:\/\/doi.org\/10.1145\/2684822.2685298","DOI":"10.1145\/2684822.2685298"},{"issue":"1","key":"381_CR4","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1038\/nphys2188","volume":"8","author":"A-L Barab\u00e1si","year":"2011","unstructured":"Barab\u00e1si A-L (2011) The network takeover. Nat Phys 8(1):14\u201316. https:\/\/doi.org\/10.1038\/nphys2188","journal-title":"Nat Phys"},{"issue":"1","key":"381_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1824795.1824796","volume":"43","author":"M Cannataro","year":"2010","unstructured":"Cannataro M, Guzzi PH, Veltri P (2010) Protein-to-protein interactions. ACM Comput Surv 43(1):1\u201336. https:\/\/doi.org\/10.1145\/1824795.1824796","journal-title":"ACM Comput Surv"},{"issue":"3","key":"381_CR6","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/j.future.2009.08.001","volume":"26","author":"M Cannataro","year":"2010","unstructured":"Cannataro M, Guzzi PH, Veltri P (2010) Impreco: distributed prediction of protein complexes. Future Gener Comput Syst 26(3):434\u2013440","journal-title":"Future Gener Comput Syst"},{"key":"381_CR7","doi-asserted-by":"crossref","unstructured":"Chan TM (2012) All-pairs shortest paths for unweighted undirected graphs in o(mn) time. ACM Trans Algorithms 8(4)","DOI":"10.1145\/2344422.2344424"},{"key":"381_CR8","doi-asserted-by":"crossref","unstructured":"Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. In: International workshop on approximation algorithms for combinatorial optimization. Springer, pp 84\u201395","DOI":"10.1007\/3-540-44436-X_10"},{"key":"381_CR9","doi-asserted-by":"publisher","unstructured":"Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. In: Jansen K, Khuller S (eds) Approximation algorithms for combinatorial optimization, third international workshop, APPROX 2000, Proceedings. Lecture notes in computer science, vol 1913. Springer, pp 84\u201395. https:\/\/doi.org\/10.1007\/3-540-44436-X","DOI":"10.1007\/3-540-44436-X"},{"issue":"1","key":"381_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1477-5956-11-20","volume":"11","author":"Y-R Cho","year":"2013","unstructured":"Cho Y-R, Mina M, Lu Y, Kwon N, Guzzi PH (2013) M-finder: uncovering functionally associated proteins from interactome data integrated with go annotations. Proteome Sci 11(1):1\u201312","journal-title":"Proteome Sci"},{"key":"381_CR11","doi-asserted-by":"crossref","unstructured":"Cho E, Myers SA, Leskovec J (2011) Friendship and mobility: user movement in location-based social networks. In: Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1082\u20131090","DOI":"10.1145\/2020408.2020579"},{"issue":"6","key":"381_CR12","doi-asserted-by":"publisher","first-page":"38107","DOI":"10.1371\/journal.pone.0038107","volume":"7","author":"G Ciriello","year":"2012","unstructured":"Ciriello G, Mina M, Guzzi PH, Cannataro M, Guerra C (2012) AlignNemo: a local network alignment method to integrate homology and topology. PLOS ONE 7(6):38107. https:\/\/doi.org\/10.1371\/journal.pone.0038107","journal-title":"PLOS ONE"},{"issue":"16","key":"381_CR13","doi-asserted-by":"publisher","first-page":"2351","DOI":"10.1093\/bioinformatics\/btu307","volume":"30","author":"C Clark","year":"2014","unstructured":"Clark C, Kalita J (2014) A comparison of algorithms for the pairwise alignment of biological networks. Bioinformatics (Oxford, England) 30(16):2351\u20132359","journal-title":"Bioinformatics (Oxford, England)"},{"issue":"2","key":"381_CR14","doi-asserted-by":"publisher","first-page":"271","DOI":"10.7155\/jgaa.00491","volume":"23","author":"R Dondi","year":"2019","unstructured":"Dondi R, Mauri G, Sikora F, Zoppis I (2019) Covering a graph with clubs. J Graph Algorithms Appl 23(2):271\u2013292. https:\/\/doi.org\/10.7155\/jgaa.00491","journal-title":"J Graph Algorithms Appl"},{"key":"381_CR15","doi-asserted-by":"crossref","unstructured":"Dondi R, Guzzi PH, Hosseinzadeh MM (2020) Top-k connected overlapping densest subgraphs in dual networks. In: International conference on complex networks and their applications. Springer, pp 585\u2013596","DOI":"10.1007\/978-3-030-65351-4_47"},{"key":"381_CR16","unstructured":"Dondi R, Hosseinzadeh MM, Mauri G, Zoppis I (2019) Top-k overlapping densest subgraphs: approximation and complexity. In: Proceedings of the 20th Italian conference on theoretical computer science, ICTCS 2019, Como, Italy, September 9\u201311, 2019, pp 110\u2013121"},{"issue":"1","key":"381_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13637-015-0022-9","volume":"2015","author":"F Faisal","year":"2015","unstructured":"Faisal F, Meng L, Crawford J, Milenkovic T (2015) The post-genomic era of biological network alignment. EURASIP J Bioinform Syst Biol 2015(1):1\u201319","journal-title":"EURASIP J Bioinform Syst Biol"},{"issue":"5","key":"381_CR18","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. https:\/\/doi.org\/10.1007\/s10618-016-0464-z","journal-title":"Data Min Knowl Discov"},{"key":"381_CR19","unstructured":"Goldberg A (1984) Finding a maximum density subgraph. Technical report. University of California, Berkeley"},{"key":"381_CR20","doi-asserted-by":"crossref","unstructured":"Guzzi PH, Milenkovi\u0107 T (2017) Survey of local and global biological network alignment: the need to reconcile the two sides of the same coin. Brief Bioinform 132","DOI":"10.1093\/bib\/bbw132"},{"issue":"1","key":"381_CR21","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1186\/1471-2105-11-315","volume":"11","author":"PH Guzzi","year":"2010","unstructured":"Guzzi PH, Cannataro M (2010) \u03bc-cs: an extension of the tm4 platform to manage affymetrix binary data. BMC Bioinform 11(1):315","journal-title":"BMC Bioinform"},{"issue":"5","key":"381_CR22","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1093\/bib\/bbr066","volume":"13","author":"P Guzzi","year":"2012","unstructured":"Guzzi P, Mina M, Guerra C, Cannataro M (2012) Semantic similarity analysis of protein data: assessment with biological features and issues. Brief Bioinform 13(5):569\u2013585. https:\/\/doi.org\/10.1093\/bib\/bbr066","journal-title":"Brief Bioinform"},{"key":"381_CR23","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"},{"key":"381_CR24","unstructured":"Hagberg A, Swart P, S\u00a0Chult D (2008) Exploring network structure, dynamics, and function using network. In: Technical report, Los Alamos National Lab. (LANL), Los Alamos"},{"issue":"Database issue","key":"381_CR25","first-page":"258","volume":"32","author":"MA Harris","year":"2004","unstructured":"Harris MA, Clark J, Ireland A, Lomax J, Ashburner M et al (2004) The gene ontology (go) database and informatics resource. Nucl Acids Res 32(Database issue):258\u2013261","journal-title":"Nucl Acids Res"},{"key":"381_CR26","unstructured":"Hastad J (1996) Clique is hard to approximate within n\/sup 1-\/spl epsiv. In: Proceedings of 37th conference on foundations of computer science. IEEE, pp 627\u2013636"},{"key":"381_CR27","doi-asserted-by":"crossref","unstructured":"Hosseinzadeh MM (2020) Dense subgraphs in biological networks. In: International conference on current trends in theory and practice of informatics. Springer, pp 711\u2013719","DOI":"10.1007\/978-3-030-38919-2_60"},{"key":"381_CR28","doi-asserted-by":"crossref","unstructured":"Karp RM (2009) Reducibility among combinatorial problems. In: 50 years of integer programming 1958\u20132008. Springer, Berlin, pp 219\u2013241","DOI":"10.1007\/978-3-540-68279-0_8"},{"issue":"12","key":"381_CR29","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. https:\/\/doi.org\/10.1007\/s00453-017-0400-7","journal-title":"Algorithmica"},{"issue":"1","key":"381_CR30","doi-asserted-by":"publisher","first-page":"21","DOI":"10.3390\/a9010021","volume":"9","author":"C Komusiewicz","year":"2016","unstructured":"Komusiewicz C (2016) Multivariate algorithmics for finding cohesive subnetworks. Algorithms 9(1):21","journal-title":"Algorithms"},{"issue":"1","key":"381_CR31","first-page":"2","volume":"13","author":"X Liu","year":"2018","unstructured":"Liu X, Shen C, Guan X, Zhou Y (2018) Digger: detect similar groups in heterogeneous social networks. ACM Trans Knowl Discov from Data (TKDD) 13(1):2","journal-title":"ACM Trans Knowl Discov from Data (TKDD)"},{"issue":"6","key":"381_CR32","doi-asserted-by":"publisher","first-page":"1958","DOI":"10.1109\/TCBB.2018.2830323","volume":"16","author":"M Milano","year":"2018","unstructured":"Milano M, Guzzi PH, Cannataro M (2018) Glalign: a novel algorithm for local network alignment. IEEE\/ACM Trans Comput Biol Bioinform 16(6):1958\u20131969","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"1","key":"381_CR33","doi-asserted-by":"publisher","first-page":"3901","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):3901. https:\/\/doi.org\/10.1038\/s41598-020-60737-5","journal-title":"Sci Rep"},{"issue":"3","key":"381_CR34","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1109\/TCBB.2014.2318707","volume":"11","author":"M Mina","year":"2014","unstructured":"Mina M, Guzzi PH (2014) Improving the robustness of local network alignment: design and extensive assessment of a Markov clustering-based approach. IEEE\/ACM Trans Comput Biol Bioinform (TCBB) 11(3):561\u2013572","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform (TCBB)"},{"issue":"11","key":"381_CR35","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1038\/nrg2452","volume":"9","author":"PC Phillips","year":"2008","unstructured":"Phillips PC (2008) Epistasis\u2014the essential role of gene interactions in the structure and evolution of genetic systems. Nat Rev Genet 9(11):855\u2013867","journal-title":"Nat Rev Genet"},{"key":"381_CR36","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1613\/jair.514","volume":"11","author":"P Resnik","year":"1999","unstructured":"Resnik P (1999) Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language. J Artif Intell Res 11:95\u2013130","journal-title":"J Artif Intell Res"},{"key":"381_CR37","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1016\/j.future.2016.10.019","volume":"86","author":"A Sapountzi","year":"2018","unstructured":"Sapountzi A, Psannis KE (2018) Social networking data analysis tools and challenges. Future Gener Comput Syst 86:893\u2013913","journal-title":"Future Gener Comput Syst"},{"issue":"22","key":"381_CR38","doi-asserted-by":"publisher","first-page":"4345","DOI":"10.1093\/hmg\/ddq356","volume":"19","author":"YV Sun","year":"2010","unstructured":"Sun YV, Kardia SL (2010) Identification of epistatic effects using a protein-protein interaction database. Human Mol Genet 19(22):4345\u20134352","journal-title":"Human Mol Genet"},{"key":"381_CR39","doi-asserted-by":"crossref","unstructured":"Szklarczyk D, Morris JH, Cook H, Kuhn M, Wyder S, Simonovic M, Santos A, Doncheva NT, Roth A, Bork P et al (2016) The string database in 2017: quality-controlled protein-protein association networks, made broadly accessible. Nucl Acids Res 937","DOI":"10.1093\/nar\/gkw937"},{"key":"381_CR40","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"},{"key":"381_CR41","doi-asserted-by":"crossref","unstructured":"Yang J, Leskovec J (2012) Community-affiliation graph model for overlapping network community detection. In: 2012 IEEE 12th international conference on data mining. IEEE, pp 1170\u20131175","DOI":"10.1109\/ICDM.2012.139"},{"key":"381_CR42","doi-asserted-by":"publisher","unstructured":"Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. In: Kleinberg JM (ed) Proceedings of the 38th annual ACM symposium on theory of computing, Seattle, WA, USA, May 21\u201323, 2006. ACM, pp 681\u2013690 (2006). https:\/\/doi.org\/10.1145\/1132516.1132612","DOI":"10.1145\/1132516.1132612"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00381-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-021-00381-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00381-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,5]],"date-time":"2021-06-05T20:09:52Z","timestamp":1622923792000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00381-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,5]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["381"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00381-8","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,5]]},"assertion":[{"value":"26 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 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":"Competing interests"}},{"value":"We give our consent for the publication.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"40"}}