Smallworldness in hypergraphs

Abstract

Most real-world networks are endowed with the small-world property, by means of which the maximal distance between any two of their nodes scales logarithmically rather than linearly with their size. The evidence sparkled a wealth of studies trying to reveal possible mechanisms through which the pairwise interactions amongst the units of a network are structured in a way to determine such observed regularity. Here we show that smallworldness occurs also when interactions are of higher order. Namely, by considering Q -uniform hypergraphs and a process through which connections can be randomly rewired with given probability p , we find that such systems may exhibit prominent clustering properties in connection with small average path lengths for a wide range of p values, in analogy to the case of dyadic interactions. The nature of small-world transition remains the same at different orders Q ( ${=}2, 3, 4, 5,$ and 6) of the interactions, however, the increase in the hyperedge order reduces the range of rewiring probability for which smallworldness emerge.

Keywords

• hypergraphs
• graph theory
• small-world