TY - JOUR
T1 - Random walks on hypergraphs
AU - Carletti, Timoteo
AU - Battiston, Federico
AU - Cencetti, Giulia
AU - Fanelli, Duccio
N1 - Funding Information:
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 Équipements de Calcul Intensif . F.B. acknowledges partial support from the ERC Synergy Grant No. 810115 (DYNASNET).
Publisher Copyright:
©2020 American Physical Society.
PY - 2020/2/18
Y1 - 2020/2/18
N2 - 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.
AB - 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.
KW - random walk
KW - hypergraphs
KW - classification
KW - ranking
KW - high order models
UR - http://www.scopus.com/inward/record.url?scp=85080099774&partnerID=8YFLogxK
U2 - 10.1103/PhysRevE.101.022308
DO - 10.1103/PhysRevE.101.022308
M3 - Article
SN - 2470-0045
VL - 101
JO - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics
JF - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics
IS - 2
M1 - 022308
ER -