Title: Simplicial Closure and higher-order link prediction,
Abstract: Networks provide a powerful formalism for modeling complex systems by using a
model of pairwise interactions. But much of the structure within these systems
involves interactions that take place among more than two nodes at once; for
example, communication within a group rather than person-to person,
collaboration among a team rather than a pair of coauthors, or biological
interaction between a set of molecules rather than just two. Such higher-order
interactions are ubiquitous, but their empirical study has received limited
attention, and little is known about possible organizational principles of such
structures. Here we study the temporal evolution of 19 datasets with explicit
accounting for higher-order interactions. We show that there is a rich variety
of structure in our datasets but datasets from the same system types have
consistent patterns of higher-order structure. Furthermore, we find that tie
strength and edge density are competing positive indicators of higher-order
organization, and these trends are consistent across interactions involving
differing numbers of nodes. To systematically further the study of theories for
such higher-order structures, we propose higher-order link prediction as a
benchmark problem to assess models and algorithms that predict higher-order
structure. We find a fundamental differences from traditional pairwise link
prediction, with a greater role for local rather than long-range information in
predicting the appearance of new interactions.