Random Walk on hypergraphs

by Timoteo Carletti (Université de Namur)




In the last twenty years network science has proven its strength in modelling many real-world interacting systems as generic agents, the nodes, connected by pairwise edges. Yet, 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 multi-body interactions. We hereby propose and study a new class of random walks defined on such higher-order structures, and grounded on a microscopic physical model where multi-body proximity is associated to highly probable exchanges among agents belonging to the same hyperedge. We provide an analytical characterization of the process whose behavior is ruled out 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 a full control of the high-order structures, and real-world networks where higher-order interactions are at play. As a 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 a 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. We then conclude by showing the impact of the high order interactions on the community structure.