{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T23:52:57Z","timestamp":1776297177722,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T00:00:00Z","timestamp":1697760000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T00:00:00Z","timestamp":1697760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004004","name":"Universit\u00e0 degli Studi di Trento","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004004","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Network motifs are recurrent, small-scale patterns of interactions observed frequently in a system. They shed light on the interplay between the topology and the dynamics of complex networks across various domains. In this work, we focus on the problem of counting occurrences of small sub-hypergraph patterns in very large hypergraphs, where higher-order interactions connect arbitrary numbers of system units. We show how directly exploiting higher-order structures speeds up the counting process compared to traditional data mining techniques for exact motif discovery. Moreover, with hyperedge sampling, performance is further improved at the cost of small errors in the estimation of motif frequency. We evaluate our method on several real-world datasets describing face-to-face interactions, co-authorship and human communication. We show that our approximated algorithm allows us to extract higher-order motifs faster and on a larger scale, beyond the computational limits of an exact approach.<\/jats:p>","DOI":"10.1007\/s00607-023-01230-5","type":"journal-article","created":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T20:33:45Z","timestamp":1697834025000},"page":"475-494","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Exact and sampling methods for mining higher-order motifs in large hypergraphs"],"prefix":"10.1007","volume":"106","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7084-8339","authenticated-orcid":false,"given":"Quintino Francesco","family":"Lotito","sequence":"first","affiliation":[]},{"given":"Federico","family":"Musciotto","sequence":"additional","affiliation":[]},{"given":"Federico","family":"Battiston","sequence":"additional","affiliation":[]},{"given":"Alberto","family":"Montresor","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,20]]},"reference":[{"issue":"5594","key":"1230_CR1","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824\u2013827","journal-title":"Science"},{"issue":"4","key":"1230_CR2","doi-asserted-by":"publisher","first-page":"2516","DOI":"10.1137\/20M1361602","volume":"20","author":"AC Schwarze","year":"2021","unstructured":"Schwarze AC, Porter MA (2021) Motifs for processes on networks. SIAM J Appl Dyn Syst 20(4):2516\u20132557","journal-title":"SIAM J Appl Dyn Syst"},{"issue":"5663","key":"1230_CR3","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1126\/science.1089167","volume":"303","author":"R Milo","year":"2004","unstructured":"Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U (2004) Superfamilies of evolved and designed networks. Science 303(5663):1538\u20131542","journal-title":"Science"},{"issue":"6","key":"1230_CR4","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1038\/nrg2102","volume":"8","author":"U Alon","year":"2007","unstructured":"Alon U (2007) Network motifs: theory and experimental approaches. Nat Rev Genet 8(6):450","journal-title":"Nat Rev Genet"},{"issue":"1","key":"1230_CR5","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1038\/ng881","volume":"31","author":"SS Shen-Orr","year":"2002","unstructured":"Shen-Orr SS, Milo R, Mangan S, Alon U (2002) Network motifs in the transcriptional regulation network of Escherichia coli. Nat Genet 31(1):64","journal-title":"Nat Genet"},{"issue":"1","key":"1230_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-5-10","volume":"5","author":"R Dobrin","year":"2004","unstructured":"Dobrin R, Beg QK, Barab\u00e1si A-L, Oltvai ZN (2004) Aggregation of topological motifs in the Escherichia coli transcriptional regulatory network. BMC Bioinformatics 5(1):1\u20138","journal-title":"BMC Bioinformatics"},{"issue":"11","key":"1230_CR7","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1371\/journal.pbio.0020369","volume":"2","author":"O Sporns","year":"2004","unstructured":"Sporns O, K\u00f6tter R (2004) Motifs in brain networks. PLoS Biol 2(11):369","journal-title":"PLoS Biol"},{"issue":"1","key":"1230_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/srep03368","volume":"3","author":"L Chen","year":"2013","unstructured":"Chen L, Qu X, Cao M, Zhou Y, Li W, Liang B, Li W, He W, Feng C, Jia X et al (2013) Identification of breast cancer patients based on human signaling network motifs. Sci Rep 3(1):1\u20137","journal-title":"Sci Rep"},{"key":"1230_CR9","doi-asserted-by":"crossref","unstructured":"Hong-lin, X., Han-bing, Y., Cui-fang, G., Ping, Z.: Social network analysis based on network motifs. J Appl Math (2014)","DOI":"10.1155\/2014\/874708"},{"issue":"1","key":"1230_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/srep30286","volume":"6","author":"F Saracco","year":"2016","unstructured":"Saracco F, Di Clemente R, Gabrielli A, Squartini T (2016) Detecting early signs of the 2007\u20132008 crisis in the world trade. Sci Rep 6(1):1\u201311","journal-title":"Sci Rep"},{"issue":"1524","key":"1230_CR11","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1098\/rstb.2008.0226","volume":"364","author":"J Bascompte","year":"2009","unstructured":"Bascompte J, Stouffer DB (2009) The assembly and disassembly of ecological networks. Philos Trans R Soc B: Biol Sci 364(1524):1781\u20131787","journal-title":"Philos Trans R Soc B: Biol Sci"},{"issue":"2","key":"1230_CR12","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1111\/oik.05670","volume":"128","author":"BI Simmons","year":"2019","unstructured":"Simmons BI, Cirtwill AR, Baker NJ, Wauchope HS, Dicks LV, Stouffer DB, Sutherland WJ (2019) Motifs in bipartite ecological networks: uncovering indirect interactions. Oikos 128(2):154\u2013170","journal-title":"Oikos"},{"key":"1230_CR13","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.065103","volume":"71","author":"J-P Onnela","year":"2005","unstructured":"Onnela J-P, Saram\u00e4ki J, Kert\u00e9sz J, Kaski K (2005) Intensity and coherence of motifs in weighted complex networks. Phys Rev E 71:065103","journal-title":"Phys Rev E"},{"issue":"11","key":"1230_CR14","doi-asserted-by":"publisher","first-page":"11005","DOI":"10.1088\/1742-5468\/2011\/11\/P11005","volume":"2011","author":"L Kovanen","year":"2011","unstructured":"Kovanen L, Karsai M, Kaski K, Kert\u00e9sz J, Saram\u00e4ki J (2011) Temporal motifs in time-dependent networks. J Stat Mech: Theory Exp 2011(11):11005","journal-title":"J Stat Mech: Theory Exp"},{"key":"1230_CR15","doi-asserted-by":"crossref","unstructured":"Paranjape A, Benson AR, Leskovec J (2017) Motifs in temporal networks. In: Proceedings of the tenth ACM international conference on web search and data mining, pp 601\u2013610 (2017). ACM","DOI":"10.1145\/3018661.3018731"},{"issue":"4","key":"1230_CR16","doi-asserted-by":"publisher","DOI":"10.1063\/1.4979282","volume":"27","author":"F Battiston","year":"2017","unstructured":"Battiston F, Nicosia V, Chavez M, Latora V (2017) Multilayer motif analysis of brain networks. Chaos Interdiscip J Nonlinear Sci 27(4):047404","journal-title":"Chaos Interdiscip J Nonlinear Sci"},{"issue":"3","key":"1230_CR17","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1109\/TNSE.2017.2753963","volume":"5","author":"M Kivel\u00e4","year":"2018","unstructured":"Kivel\u00e4 M, Porter MA (2018) Isomorphisms in multilayer networks. IEEE Trans Netw Sci Eng 5(3):198\u2013211","journal-title":"IEEE Trans Netw Sci Eng"},{"key":"1230_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2020.05.004","volume":"874","author":"F Battiston","year":"2020","unstructured":"Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young J-G, Petri G (2020) Networks beyond pairwise interactions: structure and dynamics. Phys Rep 874:1\u201392","journal-title":"Phys Rep"},{"issue":"10","key":"1230_CR19","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1038\/s41567-021-01371-4","volume":"17","author":"F Battiston","year":"2021","unstructured":"Battiston F, Amico E, Barrat A, Bianconi G, Ferraz de Arruda G, Franceschiello B, Iacopini I, K\u00e9fi S, Latora V, Moreno Y, Murray MM, Peixoto TP, Vaccarino F, Petri G (2021) The physics of higher-order interactions in complex systems. Nat Phys 17(10):1093\u20131098","journal-title":"Nat Phys"},{"issue":"1","key":"1230_CR20","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1140\/epjds\/s13688-017-0114-8","volume":"6","author":"A Patania","year":"2017","unstructured":"Patania A, Petri G, Vaccarino F (2017) The shape of collaborations. EPJ Data Sci 6(1):18","journal-title":"EPJ Data Sci"},{"key":"1230_CR21","doi-asserted-by":"publisher","first-page":"7028","DOI":"10.1038\/s41598-021-86469-8","volume":"11","author":"G Cencetti","year":"2021","unstructured":"Cencetti G, Battiston F, Lepri B, Karsai M (2021) Temporal properties of higher-order interactions in social networks. Sci Rep 11:7028","journal-title":"Sci Rep"},{"key":"1230_CR22","unstructured":"Berge, C.: Graphs and hypergraphs (1973)"},{"issue":"12","key":"1230_CR23","doi-asserted-by":"publisher","first-page":"2256","DOI":"10.14778\/3407790.3407823","volume":"13","author":"G Lee","year":"2020","unstructured":"Lee G, Ko J, Shin K (2020) Hypergraph motifs: concepts, algorithms, and discoveries. Proc VLDB Endow 13(12):2256\u20132269","journal-title":"Proc VLDB Endow"},{"issue":"1","key":"1230_CR24","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1038\/s42005-022-00858-7","volume":"5","author":"QF Lotito","year":"2022","unstructured":"Lotito QF, Musciotto F, Montresor A, Battiston F (2022) Higher-order motif analysis in hypergraphs. Commun Phys 5(1):79","journal-title":"Commun Phys"},{"issue":"4","key":"1230_CR25","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1109\/TCBB.2006.51","volume":"3","author":"S Wernicke","year":"2006","unstructured":"Wernicke S (2006) Efficient detection of network motifs. IEEE\/ACM Trans Comput Biol Bioinf 3(4):347\u2013359","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"4","key":"1230_CR26","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1049\/iet-syb.2020.0004","volume":"14","author":"S Patra","year":"2020","unstructured":"Patra S, Mohapatra A (2020) Review of tools and algorithms for network motif discovery in biological networks. IET Syst Biol 14(4):171\u2013189","journal-title":"IET Syst Biol"},{"key":"1230_CR27","doi-asserted-by":"crossref","unstructured":"Liu, P., Benson, A.R., Charikar, M.: Sampling methods for counting temporal motifs. In: Proceedings of the twelfth ACM international conference on web search and data mining. WSDM \u201919, pp 294\u2013302. Association for Computing Machinery, New York, NY, USA (2019)","DOI":"10.1145\/3289600.3290988"},{"issue":"4","key":"1230_CR28","doi-asserted-by":"publisher","first-page":"cnaa031","DOI":"10.1093\/comnet\/cnaa031","volume":"8","author":"A Jazayeri","year":"2020","unstructured":"Jazayeri A, Yang CC (2020) Motif discovery algorithms in static and temporal networks: a survey. J Complex Netw 8(4):cnaa031","journal-title":"J Complex Netw"},{"key":"1230_CR29","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-540-73847-3_26","volume-title":"Inductive logic programming","author":"T Horv\u00e1th","year":"2007","unstructured":"Horv\u00e1th T, Bringmann B, De Raedt L (2007) Frequent hypergraph mining. In: Muggleton S, Otero R, Tamaddoni-Nezhad A (eds) Inductive logic programming. Springer, Berlin, pp 244\u2013259"},{"key":"1230_CR30","doi-asserted-by":"crossref","unstructured":"Preti G, De\u00a0Francisci\u00a0Morales G, Bonchi F (2022) Fresco: mining frequent patterns in simplicial complexes. In: Proceedings of the ACM web conference 2022. WWW \u201922, pp. 1444\u20131454. Association for Computing Machinery, New York, NY, USA (2022)","DOI":"10.1145\/3485447.3512191"},{"key":"1230_CR31","doi-asserted-by":"crossref","unstructured":"Lee, G., Shin, K.: Thyme+: temporal hypergraph motifs and fast algorithms for exact counting. In: 2021 IEEE international conference on data mining (ICDM), pp 310\u2013319 (2021). IEEE","DOI":"10.1109\/ICDM51629.2021.00042"},{"key":"1230_CR32","unstructured":"Lotito, Q.F.: Higher-order motif discovery sampling algorithm (2022). https:\/\/github.com\/FraLotito\/sampling-motifs"},{"issue":"3","key":"1230_CR33","first-page":"019","volume":"11","author":"QF Lotito","year":"2023","unstructured":"Lotito QF, Contisciani M, De Bacco C, Di Gaetano L, Gallo L, Montresor A, Musciotto F, Ruggeri N, Battiston F (2023) Hypergraphx: a library for higher-order network analysis. J Complex Netw 11(3):019","journal-title":"J Complex Netw"},{"issue":"48","key":"1230_CR34","doi-asserted-by":"publisher","first-page":"11221","DOI":"10.1073\/pnas.1800683115","volume":"115","author":"AR Benson","year":"2018","unstructured":"Benson AR, Abebe R, Schaub MT, Jadbabaie A, Kleinberg J (2018) Simplicial closure and higher-order link prediction. Proc Natl Acad Sci USA 115(48):11221\u201311230","journal-title":"Proc Natl Acad Sci USA"},{"key":"1230_CR35","doi-asserted-by":"crossref","unstructured":"Chodrow, P.S.: Configuration models of random hypergraphs. J Complex Netw 8(3) (2020)","DOI":"10.1093\/comnet\/cnaa018"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-023-01230-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00607-023-01230-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-023-01230-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T07:10:19Z","timestamp":1706598619000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00607-023-01230-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,20]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["1230"],"URL":"https:\/\/doi.org\/10.1007\/s00607-023-01230-5","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,20]]},"assertion":[{"value":"25 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2023","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"}}]}}