Configuration Models of Random Hypergraphs and their Applications

Abstract

Networks of dyadic relationships between entities have emerged as a dominant paradigm for modeling complex systems. Many empirical "networks" -- such as collaboration networks; co-occurence networks; and communication networks -- are intrinsically polyadic, with multiple entities interacting simultaneously. Historically, such polyadic data has been represented dyadically via a standard projection operation. While convenient, this projection often has unintended and uncontrolled impact on downstream analysis, especially null hypothesis-testing. In this work, we develop a class of random null models for polyadic data in the framework of hypergraphs, therefore circumventing the need for projection. The null models we define are uniform on the space of hypergraphs sharing common degree and edge dimension sequences, and thus provide direct generalizations of the classical configuration model of network science. We also derive Metropolis-Hastings algorithms in order to sample from these spaces. We then apply the model to study two classical network topics -- clustering and assortativity -- as well as one contemporary, polyadic topic -- simplicial closure. In each application, we emphasize the importance of randomizing over hypergraph space rather than projected graph space, showing that this choice can dramatically alter directional study conclusions and statistical findings. For example, we find that many of social networks we study are less clustered than would be expected at random, a finding in tension with much conventional wisdom within network science. Our findings underscore the importance of carefully choosing appropriate null spaces for polyadic relational data, and demonstrate the utility of random hypergraphs in many study contexts.