{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:18:38Z","timestamp":1783577918304,"version":"3.55.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T00:00:00Z","timestamp":1778284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T00:00:00Z","timestamp":1778284800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Italian Ministry of University and Reseach","award":["PRIN Project n. 2022TS4Y3N- EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data."],"award-info":[{"award-number":["PRIN Project n. 2022TS4Y3N- EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data."]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2026,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Inferring tie strengths (\n                    <jats:italic>strong<\/jats:italic>\n                    vs.\u00a0\n                    <jats:italic>weak<\/jats:italic>\n                    ) is a core task in network analysis, often guided by the Strong Triadic Closure (STC) principle. In multilayer networks, such as social platforms or biological systems, applying STC independently to each layer can lead to inconsistent tie labels, undermining interpretations that rely on coherent relationship semantics across layers. We propose new formulations, multilayer STC and its extension STC+, which are axiomatically grounded and enforce cross-layer consistency. These problems are NP-hard; we present efficient 2- and 6-approximation algorithms alongside exact solutions. Experiments on real-world networks demonstrate that our methods produce consistent tie strength labelings with a transparent structural justification, significantly improving over the baselines.\n                  <\/jats:p>","DOI":"10.1007\/s10618-026-01216-9","type":"journal-article","created":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T07:35:55Z","timestamp":1778312155000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Consistent tie-strength labeling for multilayer strong triadic closure"],"prefix":"10.1007","volume":"40","author":[{"given":"Lutz","family":"Oettershagen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Athanasios L.","family":"Konstantinidis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fariba","family":"Ranjbar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,9]]},"reference":[{"issue":"3","key":"1216_CR1","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/S10618-020-00673-0","volume":"34","author":"F Adriaens","year":"2020","unstructured":"Adriaens F, Bie TD, Gionis A et al (2020) Relaxing the strong triadic closure problem for edge strength inference. Data Min Knowl Discov 34(3):611\u2013651. https:\/\/doi.org\/10.1007\/S10618-020-00673-0","journal-title":"Data Min Knowl Discov"},{"key":"1216_CR2","doi-asserted-by":"publisher","unstructured":"Arachchi CW, Kumpulainen I, Tatti N (2024) Dense subgraph discovery meets strong triadic closure. In: Baeza-Yates R, Bonchi F (eds) Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, pp 3334\u20133344, https:\/\/doi.org\/10.1145\/3637528.3671697","DOI":"10.1145\/3637528.3671697"},{"issue":"2","key":"1216_CR3","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda R, Even S (1981) A linear-time approximation algorithm for the weighted vertex cover problem. J Algorithms 2(2):198\u2013203. https:\/\/doi.org\/10.1016\/0196-6774(81)90020-1","journal-title":"J Algorithms"},{"issue":"1","key":"1216_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2014.07.001","volume":"544","author":"S Boccaletti","year":"2014","unstructured":"Boccaletti S, Bianconi G, Criado R et al (2014) The structure and dynamics of multilayer networks. Phys Rep 544(1):1\u2013122. https:\/\/doi.org\/10.1016\/j.physrep.2014.07.001","journal-title":"Phys Rep"},{"issue":"1","key":"1216_CR5","doi-asserted-by":"publisher","first-page":"1344","DOI":"10.1038\/srep01344","volume":"3","author":"A Cardillo","year":"2013","unstructured":"Cardillo A, G\u00f3mez-Gardenes J, Zanin M et al (2013) Emergence of network features from multiplexity. Sci Rep 3(1):1344. https:\/\/doi.org\/10.1038\/srep01344","journal-title":"Sci Rep"},{"key":"1216_CR6","doi-asserted-by":"publisher","unstructured":"Cheng X, Yang C, Zhao Y, et\u00a0al (2025) BTS: A comprehensive benchmark for tie strength prediction. In: Antonie L, Pei J, Yu X, et\u00a0al (eds) Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, pp 5345\u20135354, https:\/\/doi.org\/10.1145\/3711896.3737441","DOI":"10.1145\/3711896.3737441"},{"issue":"1","key":"1216_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2021.12.028","volume":"303","author":"TG Crainic","year":"2022","unstructured":"Crainic TG, Gendron B, Kazemzadeh MRA (2022) A taxonomy of multilayer network design and a survey of transportation and telecommunication applications. Eur J Oper Res 303(1):1\u201313. https:\/\/doi.org\/10.1016\/j.ejor.2021.12.028","journal-title":"Eur J Oper Res"},{"issue":"9","key":"1216_CR8","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1038\/s41567-023-02132-1","volume":"19","author":"M De Domenico","year":"2023","unstructured":"De Domenico M (2023) More is different in real-world multilayer networks. Nat Phys 19(9):1247\u20131262. https:\/\/doi.org\/10.1038\/s41567-023-02132-1","journal-title":"Nat Phys"},{"issue":"4","key":"1216_CR9","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.3.041022","volume":"3","author":"M De Domenico","year":"2013","unstructured":"De Domenico M, Sol\u00e9-Ribalta A, Cozzo E et al (2013) Mathematical formulation of multilayer networks. Phys Rev X 3(4):041022. https:\/\/doi.org\/10.1103\/PhysRevX.3.041022","journal-title":"Phys Rev X"},{"issue":"1","key":"1216_CR10","doi-asserted-by":"publisher","first-page":"6864","DOI":"10.1038\/ncomms7864","volume":"6","author":"M De Domenico","year":"2015","unstructured":"De Domenico M, Nicosia V, Arenas A et al (2015) Structural reducibility of multilayer networks. Nat Commun 6(1):6864. https:\/\/doi.org\/10.1038\/ncomms7864","journal-title":"Nat Commun"},{"issue":"2","key":"1216_CR11","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1093\/comnet\/cnu038","volume":"3","author":"M De Domenico","year":"2015","unstructured":"De Domenico M, Porter MA, Arenas A (2015) Muxviz: a tool for multilayer analysis and visualization of networks. Journal of Complex Networks 3(2):159\u2013176. https:\/\/doi.org\/10.1093\/comnet\/cnu038","journal-title":"Journal of Complex Networks"},{"key":"1216_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139941907","author":"ME Dickison","year":"2016","unstructured":"Dickison ME, Magnani M, Rossi L (2016) Multilayer Social Networks. Cambridge University Press Cambridge. https:\/\/doi.org\/10.1017\/CBO9781139941907","journal-title":"Cambridge University Press Cambridge"},{"key":"1216_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942","author":"DA Easley","year":"2010","unstructured":"Easley DA, Kleinberg JM (2010) Networks, Crowds, and Markets - Reasoning About a Highly Connected World. Cambridge University Press Cambridge. https:\/\/doi.org\/10.1017\/CBO9780511761942","journal-title":"Cambridge University Press Cambridge"},{"key":"1216_CR14","doi-asserted-by":"publisher","unstructured":"Gilbert E, Karahalios K (2009) Predicting tie strength with social media. In: Jr. DRO, Arthur RB, Hinckley K, et\u00a0al (eds) Proceedings of the 27th International Conference on Human Factors in Computing Systems, CHI 2009, Boston, MA, USA, April 4-9, 2009. ACM, New York, NY, USA, pp 211\u2013220, https:\/\/doi.org\/10.1145\/1518701.1518736","DOI":"10.1145\/1518701.1518736"},{"issue":"12","key":"1216_CR15","doi-asserted-by":"publisher","first-page":"3520","DOI":"10.1016\/j.cor.2005.03.030","volume":"33","author":"FC Gomes","year":"2006","unstructured":"Gomes FC, Meneses CN, Pardalos PM et al (2006) Experimental analysis of approximation algorithms for the vertex cover and set covering problems. Computers & Operations Research 33(12):3520\u20133534. https:\/\/doi.org\/10.1016\/j.cor.2005.03.030","journal-title":"Computers & Operations Research"},{"issue":"6","key":"1216_CR16","doi-asserted-by":"publisher","first-page":"1360","DOI":"10.1086\/225469","volume":"78","author":"MS Granovetter","year":"1973","unstructured":"Granovetter MS (1973) The strength of weak ties. Am J Sociol 78(6):1360\u20131380. https:\/\/doi.org\/10.1086\/225469","journal-title":"Am J Sociol"},{"key":"1216_CR17","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-019-00617-1","volume":"82","author":"N Gr\u00fcttemeier","year":"2020","unstructured":"Gr\u00fcttemeier N, Komusiewicz C (2020) On the relation of strong triadic closure and cluster deletion. Algorithmica 82:853\u2013880. https:\/\/doi.org\/10.1007\/s00453-019-00617-1","journal-title":"Algorithmica"},{"issue":"1","key":"1216_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/s41044-020-00046-0","volume":"5","author":"Z Hammoud","year":"2020","unstructured":"Hammoud Z, Kramer F (2020) Multilayer networks: aspects, implementations, and application in biomedicine. Big Data Analytics 5(1):2. https:\/\/doi.org\/10.1186\/s41044-020-00046-0","journal-title":"Big Data Analytics"},{"issue":"1","key":"1216_CR19","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0052168","volume":"8","author":"JJ Jones","year":"2013","unstructured":"Jones JJ, Settle JE, Bond RM et al (2013) Inferring tie strength from online directed behavior. PLoS ONE 8(1):e52168. https:\/\/doi.org\/10.1371\/journal.pone.0052168","journal-title":"PLoS ONE"},{"key":"1216_CR20","doi-asserted-by":"publisher","unstructured":"Kahanda I, Neville J (2009) Using transactional information to predict link strength in online social networks. In: Adar E, Hurst M, Finin T, et\u00a0al (eds) Proceedings of the Third International Conference on Weblogs and Social Media, ICWSM. The AAAI Press, Washington, DC, USA, pp 74\u201381, https:\/\/doi.org\/10.1609\/icwsm.v3i1.13957","DOI":"10.1609\/icwsm.v3i1.13957"},{"issue":"3","key":"1216_CR21","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1093\/comnet\/cnu016","volume":"2","author":"M Kivel\u00e4","year":"2014","unstructured":"Kivel\u00e4 M, Arenas A, Barthelemy M et al (2014) Multilayer networks Journal of complex networks 2(3):203\u2013271. https:\/\/doi.org\/10.1093\/comnet\/cnu016","journal-title":"Multilayer networks Journal of complex networks"},{"key":"1216_CR22","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.dam.2020.05.035","volume":"285","author":"AL Konstantinidis","year":"2020","unstructured":"Konstantinidis AL, Papadopoulos C (2020) Maximizing the strong triadic closure in split graphs and proper interval graphs. Discret Appl Math 285:79\u201395. https:\/\/doi.org\/10.1016\/j.dam.2020.05.035","journal-title":"Discret Appl Math"},{"key":"1216_CR23","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.tcs.2018.05.012","volume":"740","author":"AL Konstantinidis","year":"2018","unstructured":"Konstantinidis AL, Nikolopoulos SD, Papadopoulos C (2018) Strong triadic closure in cographs and graphs of low maximum degree. Theor Comput Sci 740:76\u201384. https:\/\/doi.org\/10.1016\/j.tcs.2018.05.012","journal-title":"Theor Comput Sci"},{"key":"1216_CR24","doi-asserted-by":"publisher","unstructured":"Ley M (2002) The DBLP computer science bibliography: Evolution, research issues, perspectives. In: Laender AHF, Oliveira AL (eds) String Processing and Information Retrieval, 9th International Symposium, SPIRE. Springer, Berlin, Heidelberg, pp 1\u201310, https:\/\/doi.org\/10.1007\/3-540-45735-6_1","DOI":"10.1007\/3-540-45735-6_1"},{"issue":"1","key":"1216_CR25","doi-asserted-by":"publisher","first-page":"18001","DOI":"10.1209\/0295-5075\/89\/18001","volume":"89","author":"L L\u00fc","year":"2010","unstructured":"L\u00fc L, Zhou T (2010) Link prediction in weighted networks: The role of weak ties. Europhys Lett 89(1):18001. https:\/\/doi.org\/10.1209\/0295-5075\/89\/18001","journal-title":"Europhys Lett"},{"key":"1216_CR26","doi-asserted-by":"publisher","unstructured":"Magnani M, Micenkova B, Rossi L (2013) Combinatorial analysis of multiple networks. arXiv preprint arXiv:1303.4986https:\/\/doi.org\/10.48550\/arXiv.1303.4986","DOI":"10.48550\/arXiv.1303.4986"},{"issue":"1","key":"1216_CR27","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/s10618-021-00812-1","volume":"36","author":"A Matakos","year":"2022","unstructured":"Matakos A, Gionis A (2022) Strengthening ties towards a highly-connected world. Data Min Knowl Discov 36(1):448\u2013476. https:\/\/doi.org\/10.1007\/s10618-021-00812-1","journal-title":"Data Min Knowl Discov"},{"key":"1216_CR28","doi-asserted-by":"publisher","unstructured":"Oettershagen L, Konstantinidis AL, Italiano GF (2022) Inferring tie strength in temporal networks. In: Amini M, Canu S, Fischer A, et\u00a0al (eds) European Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD. Springer International Publishing, Cham, pp 69\u201385, https:\/\/doi.org\/10.1007\/978-3-031-26390-3_5","DOI":"10.1007\/978-3-031-26390-3_5"},{"issue":"2","key":"1216_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10618-025-01093-8","volume":"39","author":"L Oettershagen","year":"2025","unstructured":"Oettershagen L, Konstantinidis AL, Italiano GF (2025) Inferring tie strength in temporal networks. Data Min Knowl Discov 39(2):1\u201331. https:\/\/doi.org\/10.1007\/s10618-025-01093-8","journal-title":"Data Min Knowl Discov"},{"key":"1216_CR30","first-page":"223","volume-title":"21st Italian Symposium on Advanced Database Systems, SEBD","author":"L Pappalardo","year":"2013","unstructured":"Pappalardo L, Rossetti G, Pedreschi D (2013) Measuring tie strength in multidimensional networks. In: Buccafurri F, Sacc\u00e0 D (eds) 21st Italian Symposium on Advanced Database Systems, SEBD. Curran Associates, Red Hook, NY, USA, pp 223\u2013230"},{"issue":"1","key":"1216_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2877200","volume":"41","author":"H Pham","year":"2016","unstructured":"Pham H, Shahabi C, Liu Y (2016) Inferring social strength from spatiotemporal data. ACM Trans Database Syst 41(1):1\u201347. https:\/\/doi.org\/10.1145\/2877200","journal-title":"ACM Trans Database Syst"},{"key":"1216_CR32","doi-asserted-by":"publisher","unstructured":"Rozenshtein P, Tatti N, Gionis A (2017) Inferring the strength of social ties: A community-driven approach. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, pp 1017\u20131025, https:\/\/doi.org\/10.1145\/3097983.3098199","DOI":"10.1145\/3097983.3098199"},{"key":"1216_CR33","doi-asserted-by":"publisher","unstructured":"Sintos S, Tsaparas P (2014) Using strong triadic closure to characterize ties in social networks. In: Macskassy SA, Perlich C, Leskovec J, et\u00a0al (eds) The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, pp 1466\u20131475, https:\/\/doi.org\/10.1145\/2623330.2623664","DOI":"10.1145\/2623330.2623664"},{"issue":"1","key":"1216_CR34","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.intmar.2020.10.001","volume":"54","author":"S Stolz","year":"2021","unstructured":"Stolz S, Schlereth C (2021) Predicting tie strength with ego network structures. J Interact Mark 54(1):40\u201352. https:\/\/doi.org\/10.1016\/j.intmar.2020.10.001","journal-title":"J Interact Mark"},{"key":"1216_CR35","doi-asserted-by":"publisher","unstructured":"Toutanova K, Chen D, Pantel P, et\u00a0al (2015) Representing text for joint embedding of text and knowledge bases. In: M\u00e0rquez L, Callison-Burch C, Su J (eds) Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Lisbon, Portugal, pp 1499\u20131509, https:\/\/doi.org\/10.18653\/v1\/D15-1174","DOI":"10.18653\/v1\/D15-1174"},{"issue":"9","key":"1216_CR36","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0073970","volume":"8","author":"P Vanhems","year":"2013","unstructured":"Vanhems P, Barrat A, Cattuto C et al (2013) Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PLoS ONE 8(9):e73970. https:\/\/doi.org\/10.1371\/journal.pone.0073970","journal-title":"PLoS ONE"},{"key":"1216_CR37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer Berlin Heidelberg. https:\/\/doi.org\/10.1007\/978-3-662-04565-7","journal-title":"Springer Berlin Heidelberg"},{"key":"1216_CR38","unstructured":"Veldt N (2022) Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds. In: Chaudhuri K, Jegelka S, Song L, et\u00a0al (eds) Proceedings of the 39th International Conference on Machine Learning, pp 22060\u201322083"},{"key":"1216_CR39","doi-asserted-by":"publisher","unstructured":"Xiang R, Neville J, Rogati M (2010) Modeling relationship strength in online social networks. In: Proceedings of the 19th International Conference on World Wide Web, pp 981\u2013990, https:\/\/doi.org\/10.1145\/1772690.1772790","DOI":"10.1145\/1772690.1772790"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-026-01216-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-026-01216-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-026-01216-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T05:53:21Z","timestamp":1783576401000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-026-01216-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,9]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["1216"],"URL":"https:\/\/doi.org\/10.1007\/s10618-026-01216-9","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,9]]},"assertion":[{"value":"29 October 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2026","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 no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"46"}}