Random walks on hypergraphs

Timoteo Carletti, Federico Battiston, Giulia Cencetti, Duccio Fanelli

Research output: Contribution to journalArticlepeer-review

47 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number022308
Number of pages19
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume101
Issue number2
DOIs
Publication statusPublished - 18 Feb 2020

Keywords

  • random walk
  • hypergraphs
  • classification
  • ranking
  • high order models

Fingerprint

Dive into the research topics of 'Random walks on hypergraphs'. Together they form a unique fingerprint.
  • Dynamical systems on hypergraphs

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

    Research output: Contribution in Book/Catalog/Report/Conference proceedingChapter (peer-reviewed)peer-review

    Open Access
    File
    6 Downloads (Pure)
  • Flow-Based Community Detection in Hypergraphs

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

    Research output: Contribution in Book/Catalog/Report/Conference proceedingChapter (peer-reviewed)peer-review

    File
    5 Downloads (Pure)

Cite this