A deluge of new data on real-world networks suggests that interactions among system units are not limited to pairs, but often involve a higher number of nodes. To properly encode higher-order interactions, richer mathematical frameworks such as hypergraphs are needed, where hyperedges describe interactions among an arbitrary number of nodes. Here we systematically investigate higher-order motifs, defined as small connected subgraphs in which vertices may be linked by interactions of any order, and propose an efficient algorithm to extract complete higher-order motif profiles from empirical data. We identify different families of hypergraphs, characterized by distinct higher-order connectivity patterns at the local scale. We also propose a set of measures to study the nested structure of hyperedges and provide evidences of structural reinforcement, a mechanism that associates higher strengths of higher-order interactions for the nodes that interact more at the pairwise level. Our work highlights the informative power of higher-order motifs, providing a principled way to extract higher-order fingerprints in hypergraphs at the network microscale.

Higher-order motif analysis in hypergraphs / Lotito, Q. F.; Musciotto, F.; Montresor, A.; Battiston, F.. - In: COMMUNICATIONS PHYSICS. - ISSN 2399-3650. - ELETTRONICO. - 5:1(2022), pp. 791-798. [10.1038/s42005-022-00858-7]

Higher-order motif analysis in hypergraphs

Lotito Q. F.;Montresor A.;
2022-01-01

Abstract

A deluge of new data on real-world networks suggests that interactions among system units are not limited to pairs, but often involve a higher number of nodes. To properly encode higher-order interactions, richer mathematical frameworks such as hypergraphs are needed, where hyperedges describe interactions among an arbitrary number of nodes. Here we systematically investigate higher-order motifs, defined as small connected subgraphs in which vertices may be linked by interactions of any order, and propose an efficient algorithm to extract complete higher-order motif profiles from empirical data. We identify different families of hypergraphs, characterized by distinct higher-order connectivity patterns at the local scale. We also propose a set of measures to study the nested structure of hyperedges and provide evidences of structural reinforcement, a mechanism that associates higher strengths of higher-order interactions for the nodes that interact more at the pairwise level. Our work highlights the informative power of higher-order motifs, providing a principled way to extract higher-order fingerprints in hypergraphs at the network microscale.
2022
1
Lotito, Q. F.; Musciotto, F.; Montresor, A.; Battiston, F.
Higher-order motif analysis in hypergraphs / Lotito, Q. F.; Musciotto, F.; Montresor, A.; Battiston, F.. - In: COMMUNICATIONS PHYSICS. - ISSN 2399-3650. - ELETTRONICO. - 5:1(2022), pp. 791-798. [10.1038/s42005-022-00858-7]
File in questo prodotto:
File Dimensione Formato  
s42005-022-00858-7.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Creative commons
Dimensione 771.09 kB
Formato Adobe PDF
771.09 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/340472
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 67
  • ???jsp.display-item.citation.isi??? 58
  • OpenAlex ND
social impact