{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T03:36:18Z","timestamp":1769225778345,"version":"3.49.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T00:00:00Z","timestamp":1768694400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T00:00:00Z","timestamp":1769040000000},"content-version":"vor","delay-in-days":4,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"name":"DS4H","award":["ANR-17-EURE-0004"],"award-info":[{"award-number":["ANR-17-EURE-0004"]}]},{"name":"3IA","award":["ANR-19-P3IA-0002"],"award-info":[{"award-number":["ANR-19-P3IA-0002"]}]},{"name":"Nokia Bell Labs \u201cDistributed Learning and Control for Network Analysis\u201d"},{"name":"Bpifrance in collaboration with Airbus D&S"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"DOI":"10.1007\/s41109-025-00756-1","type":"journal-article","created":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T23:05:34Z","timestamp":1768777534000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalization of single-linkage with higher-order interactions"],"prefix":"10.1007","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-3570-746X","authenticated-orcid":false,"given":"Louis","family":"Hauseux","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8124-8272","authenticated-orcid":false,"given":"Konstantin","family":"Avrachenkov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7444-0856","authenticated-orcid":false,"given":"Josiane","family":"Zerubia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,18]]},"reference":[{"issue":"177","key":"756_CR1","first-page":"1","volume":"18","author":"E Abbe","year":"2018","unstructured":"Abbe E (2018) Community detection and stochastic block models: recent developments. J Mach Learn Res 18(177):1\u201386","journal-title":"J Mach Learn Res"},{"issue":"2","key":"756_CR2","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0020-7373(72)80029-4","volume":"4","author":"R Atkin","year":"1972","unstructured":"Atkin R (1972) From cohomology in physics to $$q$$-connectivity in social science. Int J Man Mach Stud 4(2):139\u2013167. https:\/\/doi.org\/10.1016\/S0020-7373(72)80029-4","journal-title":"Int J Man Mach Stud"},{"key":"756_CR3","doi-asserted-by":"crossref","unstructured":"Behley J, Garbade M, Milioto A, et\u00a0al (2019) SemanticKITTI: a dataset for semantic scene understanding of LiDAR sequences. In: proceedings of the IEEE\/CVF international conference on computer vision (ICCV)","DOI":"10.1109\/ICCV.2019.00939"},{"key":"756_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25388-6","volume-title":"Lectures on the nearest neighbor method","author":"G Biau","year":"2015","unstructured":"Biau G, Devroye L (2015) Lectures on the nearest neighbor method, vol 246. Springer, New York. https:\/\/doi.org\/10.1007\/978-3-319-25388-6"},{"key":"756_CR5","series-title":"Cambridge Texts in Applied Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25388-6","volume-title":"Geometric and Topological Inference","author":"JD Boissonnat","year":"2018","unstructured":"Boissonnat JD, Chazal F, Yvinec M (2018) Geometric and Topological Inference. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge. https:\/\/doi.org\/10.1007\/978-3-319-25388-6"},{"key":"756_CR6","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-642-37456-2_14","volume-title":"Advances in knowledge discovery and data mining","author":"RJGB Campello","year":"2013","unstructured":"Campello RJGB, Moulavi D, Sander J (2013) Density-based clustering based on hierarchical density estimates. In: Sam A (ed) Advances in knowledge discovery and data mining. Springer, New York, pp 160\u2013172. https:\/\/doi.org\/10.1007\/978-3-642-37456-2_14"},{"issue":"2","key":"756_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/widm.1343","volume":"10","author":"RJGB Campello","year":"2020","unstructured":"Campello RJGB, Kr\u00f6ger P, Sander J et al (2020) Density-based clustering. WIREs Data Mining Knowl Disc 10(2):231. https:\/\/doi.org\/10.1002\/widm.1343","journal-title":"WIREs Data Mining Knowl Disc"},{"key":"756_CR8","volume-title":"Advances in neural information processing systems","author":"K Chaudhuri","year":"2010","unstructured":"Chaudhuri K, Dasgupta S (2010) Rates of convergence for the cluster tree. In: Lafferty J, Williams C, Shawe-Taylor J et al (eds) Advances in neural information processing systems, vol 23. Curran Associates Inc, Red Hook"},{"issue":"6","key":"756_CR9","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B Chazelle","year":"2000","unstructured":"Chazelle B (2000) A minimum spanning tree algorithm with inverse-Ackermann type complexity. J ACM 47(6):1028\u20131047. https:\/\/doi.org\/10.1145\/355541.355562","journal-title":"J ACM"},{"issue":"3\u20134","key":"756_CR10","doi-asserted-by":"publisher","first-page":"282","DOI":"10.4064\/cm-2-3-4-282-285","volume":"2","author":"K Florek","year":"1951","unstructured":"Florek K, \u0141ukaszewicz J, Perkal J et al (1951) Sur la liaison et la division des points d\u2019un ensemble fini. Colloq Math 2(3\u20134):282\u2013285. https:\/\/doi.org\/10.4064\/cm-2-3-4-282-285","journal-title":"Colloq Math"},{"key":"756_CR11","unstructured":"Forina M, Armanino C, Lanteri S, et\u00a0al (1983) Classification of olive oils from their fatty acid composition. In: Food research and data analysis: proceedings from the IUFoST symposium, September 20-23, 1982, Oslo, London: Applied Science Publishers"},{"key":"756_CR12","doi-asserted-by":"publisher","first-page":"4743","DOI":"10.1007\/s10489-018-1238-7","volume":"48","author":"P Fr\u00e4nti","year":"2018","unstructured":"Fr\u00e4nti P, Sieranoja S (2018) K-means properties on six clustering benchmark datasets. Appl Intell 48:4743\u20134759. https:\/\/doi.org\/10.1007\/s10489-018-1238-7","journal-title":"Appl Intell"},{"key":"756_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.softx.2022.101270","volume":"20","author":"M Gagolewski","year":"2022","unstructured":"Gagolewski M (2022) A framework for benchmarking clustering algorithms. SoftwareX 20:101270. https:\/\/doi.org\/10.1016\/j.softx.2022.101270 (https:\/\/clustering-benchmarks.gagolewski.com)","journal-title":"SoftwareX"},{"issue":"1","key":"756_CR14","doi-asserted-by":"publisher","first-page":"54","DOI":"10.2307\/2346439","volume":"18","author":"JC Gower","year":"1969","unstructured":"Gower JC, Ross GJS (1969) Minimum spanning trees and single linkage cluster analysis. J Roy Stat Soc Ser C (Appl Stat) 18(1):54\u201364. https:\/\/doi.org\/10.2307\/2346439","journal-title":"J Roy Stat Soc Ser C (Appl Stat)"},{"key":"756_CR15","volume-title":"Clustering algorithms","author":"JA Hartigan","year":"1975","unstructured":"Hartigan JA (1975) Clustering algorithms. Wiley, Amsterdam"},{"key":"756_CR16","unstructured":"Hauseux L (2025) HypergraphPercol_K2: reference implementation for K=2 higher-order single-linkage. https:\/\/github.com\/Ayana-Inria\/HypergraphPercol_K2, gitHub repository"},{"key":"756_CR17","doi-asserted-by":"publisher","unstructured":"Hauseux L, Avrachenkov K, Zerubia J (2024a) Benefits of hypergraphs for density-based clustering. In: 32nd European signal processing conference (EUSIPCO), Lyon, France, https:\/\/doi.org\/10.23919\/EUSIPCO63174.2024.10715271","DOI":"10.23919\/EUSIPCO63174.2024.10715271"},{"key":"756_CR18","doi-asserted-by":"crossref","unstructured":"Hauseux L, Avrachenkov K, Zerubia J (2024b) Hypergraphs, percolation, and hierarchical clustering. In: Springer (ed) The 13th international conference on complex networks and their applications, Istanbul, Turkey, Studies in Computational Intelligence","DOI":"10.1007\/978-3-031-82431-9_2"},{"issue":"1","key":"756_CR19","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/s41468-025-00202-2","volume":"9","author":"C Hirsch","year":"2025","unstructured":"Hirsch C, Valesin D (2025) Face and cycle percolation. J Appl Comput Topol 9(1):6","journal-title":"J Appl Comput Topol"},{"issue":"2","key":"756_CR20","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"PW Holland","year":"1983","unstructured":"Holland PW, Leinhardt S (1983) Stochastic blockmodels: first steps. Social Netw 5(2):109\u2013137. https:\/\/doi.org\/10.1016\/0378-8733(83)90021-7","journal-title":"Social Netw"},{"key":"756_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","volume":"2","author":"L Hubert","year":"1985","unstructured":"Hubert L, Arabie P (1985) Compar partitions. J Classif 2:193\u2013218. https:\/\/doi.org\/10.1007\/BF01908075","journal-title":"J Classif"},{"issue":"2","key":"756_CR22","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1525\/gfc.2020.20.2.55","volume":"20","author":"C Ipsen","year":"2020","unstructured":"Ipsen C (2020) Xylella fastidiosa and the olive oil crisis in Puglia. Gastronomica 20(2):55\u201366. https:\/\/doi.org\/10.1525\/gfc.2020.20.2.55","journal-title":"Gastronomica"},{"issue":"2","key":"756_CR23","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"DR Karger","year":"1995","unstructured":"Karger DR, Klein PN, Tarjan RE (1995) A randomized linear-time algorithm to find minimum spanning trees. J ACM 42(2):321\u2013328. https:\/\/doi.org\/10.1145\/201019.201022","journal-title":"J ACM"},{"key":"756_CR24","doi-asserted-by":"publisher","unstructured":"McInnes L, Healy J (2017) Accelerated hierarchical density based clustering. In: IEEE international conference on data mining workshops (ICDMW), pp 33\u201342, https:\/\/doi.org\/10.1109\/ICDMW.2017.12","DOI":"10.1109\/ICDMW.2017.12"},{"key":"756_CR25","series-title":"Cambridge Tracts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511895357","volume-title":"Continuum Percolation","author":"R Meester","year":"1996","unstructured":"Meester R, Roy R (1996) Continuum Percolation. Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge. https:\/\/doi.org\/10.1017\/CBO9780511895357"},{"issue":"3","key":"756_CR26","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1111\/rssa.12796","volume":"185","author":"G Menardi","year":"2022","unstructured":"Menardi G, De Stefano D (2022) Density-based clustering of social networks. J R Stat Soc Ser A Stat Soc 185(3):1004\u20131029. https:\/\/doi.org\/10.1111\/rssa.12796","journal-title":"J R Stat Soc Ser A Stat Soc"},{"key":"756_CR27","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-319-21903-5_8","volume-title":"Hierarchical clustering","author":"F Nielsen","year":"2016","unstructured":"Nielsen F (2016) Hierarchical clustering. Springer, New York, pp 195\u2013211. https:\/\/doi.org\/10.1007\/978-3-319-21903-5_8"},{"key":"756_CR28","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1016\/S0076-6879(88)64084-5","volume-title":"Ribosomes, Methods in Enzymology","author":"GJ Olsen","year":"1988","unstructured":"Olsen GJ (1988) Phylogenetic analysis using ribosomal RNA. Ribosomes, Methods in Enzymology, vol 164. Academic Press, Cambridge, pp 793\u2013812. https:\/\/doi.org\/10.1016\/S0076-6879(88)64084-5"},{"key":"756_CR29","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-540-69395-6_9","volume-title":"$$k$$-clique percolation and clustering","author":"G Palla","year":"2008","unstructured":"Palla G, \u00c1bel D, Farkas IJ et al (2008) $$k$$-clique percolation and clustering. Springer, Berlin, pp 369\u2013408. https:\/\/doi.org\/10.1007\/978-3-540-69395-6_9"},{"issue":"2\u20134","key":"756_CR30","first-page":"57","volume":"11","author":"HP Patil","year":"1986","unstructured":"Patil HP (1986) On the structure of $$k$$-trees. J Combin Inform Syst Sci 11(2\u20134):57\u201364","journal-title":"J Combin Inform Syst Sci"},{"key":"756_CR31","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Random geometric graphs","author":"M Penrose","year":"2003","unstructured":"Penrose M (2003) Random geometric graphs, vol 5. Oxford University Press, Oxford. https:\/\/doi.org\/10.1093\/acprof:oso\/9780198506263.001.0001"},{"issue":"1","key":"756_CR32","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/505241.505243","volume":"49","author":"S Pettie","year":"2002","unstructured":"Pettie S, Ramachandran V (2002) An optimal minimum spanning tree algorithm. J ACM 49(1):16\u201334. https:\/\/doi.org\/10.1145\/505241.505243","journal-title":"J ACM"},{"issue":"6","key":"756_CR33","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36(6):1389\u20131401. https:\/\/doi.org\/10.1002\/j.1538-7305.1957.tb01515.x","journal-title":"Bell Syst Tech J"},{"key":"756_CR34","doi-asserted-by":"publisher","unstructured":"Rolle A, Scoccola L (2023) Stable and consistent density-based clustering. https:\/\/doi.org\/10.48550\/arXiv.2005.09048","DOI":"10.48550\/arXiv.2005.09048"},{"key":"756_CR35","doi-asserted-by":"publisher","unstructured":"Sarfraz MS, Sharma V, Stiefelhagen R (2019) Efficient parameter-free clustering using first neighbor relations. In: Proceedings of the IEEE\/CVF conference on computer vision and pattern recognition (CVPR), pp 8934\u20138943, https:\/\/doi.org\/10.1109\/CVPR.2019.00914","DOI":"10.1109\/CVPR.2019.00914"},{"key":"756_CR36","doi-asserted-by":"publisher","unstructured":"Sautier C, Puy G, Boulch A, et\u00a0al (2025) Clustering is back: reaching state-of-the-art LiDAR instance segmentation without training. https:\/\/doi.org\/10.48550\/arXiv.2107.06440","DOI":"10.48550\/arXiv.2107.06440"},{"issue":"1","key":"756_CR37","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1080\/02664763.2020.1799958","volume":"49","author":"D Scaldelai","year":"2022","unstructured":"Scaldelai D, Matioli LC, Santos SR et al (2022) MulticlusterKDE: a new algorithm for clustering based on multivariate kernel density estimation. J Appl Stat 49(1):98\u2013121. https:\/\/doi.org\/10.1080\/02664763.2020.1799958","journal-title":"J Appl Stat"},{"key":"756_CR38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.102.052108","volume":"102","author":"H Schawe","year":"2020","unstructured":"Schawe H, Hartmann AK (2020) Large deviations of connected components in the stochastic block model. Phys Rev E 102:052108. https:\/\/doi.org\/10.1103\/PhysRevE.102.052108","journal-title":"Phys Rev E"},{"key":"756_CR39","doi-asserted-by":"publisher","unstructured":"Shangin RE, Pardalos PM (2014) Heuristics for minimum spanning $$k$$-tree problem. Procedia Computer Science 31:1074\u20131083. https:\/\/doi.org\/10.1016\/j.procs.2014.05.362, 2nd international conference on information technology and quantitative management, ITQM 2014","DOI":"10.1016\/j.procs.2014.05.362"},{"key":"756_CR40","doi-asserted-by":"crossref","unstructured":"Srinivasavaradhan SR, Gopi S, Pfister HD, et\u00a0al (2021) Trellis bma: coded trace reconstruction on ids channels for dna storage. Dataset: https:\/\/github.com\/microsoft\/clustered-nanopore-reads-dataset, arXiv:2107.06440","DOI":"10.1109\/ISIT45174.2021.9517821"},{"issue":"2","key":"756_CR41","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1198\/jcgs.2009.07049","volume":"19","author":"W Stuetzle","year":"2010","unstructured":"Stuetzle W, Nugent R (2010) A generalized single linkage method for estimating the cluster tree of a density. J Comput Graph Stat 19(2):397\u2013418. https:\/\/doi.org\/10.1198\/jcgs.2009.07049","journal-title":"J Comput Graph Stat"},{"key":"756_CR42","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BFb0038202","volume-title":"New results and new trends in computer science","author":"E Welzl","year":"1991","unstructured":"Welzl E (1991) Smallest enclosing disks (balls and ellipsoids). In: Maurer H (ed) New results and new trends in computer science. Springer, Heidelberg, pp 359\u2013370. https:\/\/doi.org\/10.1007\/BFb0038202"},{"issue":"2","key":"756_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.18637\/jss.v040.i02","volume":"40","author":"H Wickham","year":"2011","unstructured":"Wickham H, Cook D, Hofmann H et al (2011) tourr: an R package for exploring multivariate data with projections. J Stat Softw 40(2):1\u201318. https:\/\/doi.org\/10.18637\/jss.v040.i02","journal-title":"J Stat Softw"},{"key":"756_CR44","unstructured":"Wishart D (1969) Mode analysis: a generalization of nearest neighbour which reduces chaining effects (with discussion). Numerical taxonomy pp 282\u2013311"},{"issue":"6","key":"756_CR45","doi-asserted-by":"publisher","first-page":"4897","DOI":"10.1109\/TPAMI.2025.3545573","volume":"47","author":"J Yao","year":"2025","unstructured":"Yao J, Pan J, Zeng Y (2025) Gauging-$$\\delta $$: a non-parametric hierarchical clustering algorithm. IEEE Trans Pattern Anal Mach Intell 47(6):4897\u20134907. https:\/\/doi.org\/10.1109\/TPAMI.2025.3545573","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"756_CR46","doi-asserted-by":"publisher","unstructured":"Zhu E, Markovtsev V, Astafiev A et al (2024) datasketch: MinHash, LSH, LSH Forest, Weighted MinHash, HyperLogLog, HyperLogLog++. LSH ensemble and HNSW. https:\/\/doi.org\/10.5281\/zenodo.11462182 (https:\/\/github.com\/ekzhu\/datasketch)","DOI":"10.5281\/zenodo.11462182"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-025-00756-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-025-00756-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-025-00756-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T23:04:27Z","timestamp":1769209467000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41109-025-00756-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,18]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["756"],"URL":"https:\/\/doi.org\/10.1007\/s41109-025-00756-1","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,18]]},"assertion":[{"value":"15 July 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 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":"Competing interests"}}],"article-number":"9"}}