Random walks on hypergraphs

Timoteo Carletti, Federico Battiston, Giulia Cencetti, Duccio Fanelli

Résultats de recherche: Contribution à un journal/une revueArticleRevue par des pairs

97 Téléchargements (Pure)

Résumé

In the past 20 years network science has proven its strength in modeling many real-world interacting systems as generic agents, the nodes, connected by pairwise edges. Nevertheless, in many relevant cases, interactions are not pairwise but involve larger sets of nodes at a time. These systems are thus better described in the framework of hypergraphs, whose hyperedges effectively account for multibody interactions. Here we propose and study a class of random walks defined on such higher-order structures and grounded on a microscopic physical model where multibody proximity is associated with highly probable exchanges among agents belonging to the same hyperedge. We provide an analytical characterization of the process, deriving a general solution for the stationary distribution of the walkers. The dynamics is ultimately driven by a generalized random-walk Laplace operator that reduces to the standard random-walk Laplacian when all the hyperedges have size 2 and are thus meant to describe pairwise couplings. We illustrate our results on synthetic models for which we have full control of the high-order structures and on real-world networks where higher-order interactions are at play. As the first application of the method, we compare the behavior of random walkers on hypergraphs to that of traditional random walkers on the corresponding projected networks, drawing interesting conclusions on node rankings in collaboration networks. As the second application, we show how information derived from the random walk on hypergraphs can be successfully used for classification tasks involving objects with several features, each one represented by a hyperedge. Taken together, our work contributes to unraveling the effect of higher-order interactions on diffusive processes in higher-order networks, shedding light on mechanisms at the heart of biased information spreading in complex networked systems.
langue originaleAnglais
Numéro d'article022308
Nombre de pages19
journalPhysical review. E
Volume101
Numéro de publication2
Les DOIs
Etat de la publicationPublié - 18 févr. 2020

Financement

We thank an anonymous referee for pointing out an issue with a previous version of Eq. . T.C. would like to thank F. Gargiulo for her help in the data collection process. This research used resources of the Plateforme Technologique de Calcul Intensif (PTCI) located at the University of Namur, Belgium, which is supported by the FNRS-FRFC, the Walloon Region, and the University of Namur (Conventions No. 2.5020.11, No. GEQ U.G006.15, No. 1610468, and No. RW/GEQ2016). The PTCI is member of the Consortium des \u00C9quipements de Calcul Intensif . F.B. acknowledges partial support from the ERC Synergy Grant No. 810115 (DYNASNET).

Bailleurs de fondsNuméro du bailleur de fonds
FNRS-FRFC
European Resuscitation Council
Université de Namur1610468, 2.5020.11, RW/GEQ2016, GEQ U.G006.15
Horizon 2020 Framework Programme810115
UK Research and Innovation51045

    Empreinte digitale

    Examiner les sujets de recherche de « Random walks on hypergraphs ». Ensemble, ils forment une empreinte digitale unique.
    • Dynamical systems on hypergraphs

      Carletti, T. & Fanelli, D., 27 avr. 2022, Higher-Order Systems. Springer, p. 163-180 18 p. (Understanding Complex Systems).

      Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceChapitre (revu par des pairs)Revue par des pairs

      Accès ouvert
      File
      60 Téléchargements (Pure)
    • Flow-Based Community Detection in Hypergraphs

      Eriksson, A., Carletti, T., Lambiotte, R., Rojas, A. & Rosvall, M., 27 avr. 2022, Understanding Complex Systems. Springer, p. 141-161 21 p. (Understanding Complex Systems).

      Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceChapitre (revu par des pairs)Revue par des pairs

      File
      53 Téléchargements (Pure)
    • Conference Complex Systems 2020

      Carletti, T. (Participant)

      7 déc. 202011 déc. 2020

      Activité: Participation ou organisation d'un événementParticipation à une conférence, un congrès

    • BeNet20

      Carletti, T. (Conférencier)

      12 nov. 2020

      Activité: Participation ou organisation d'un événementParticipation à une conférence, un congrès

    • BeNet20

      Carletti, T. (Participant)

      12 nov. 2020

      Activité: Participation ou organisation d'un événementParticipation à une conférence, un congrès

    Contient cette citation