Generative hypergraph clustering: From blockmodels to modularity

• Published in: Science advances 2021-07, Vol.7 (28)
• Main Authors: Chodrow, Philip S, Veldt, Nate, Benson, Austin R
• Format: Article
• Language: English
• Subjects: Computer Science; Network Science; SciAdv r-articles
• ISSN: 2375-2548; 2375-2548
• DOI: 10.1126/sciadv.abh1303

Hypergraphs are a natural modeling paradigm for networked systems with multiway interactions. A standard task in network analysis is the identification of closely related or densely interconnected nodes. We propose a probabilistic generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. Approximate maximum likelihood inference in this model leads to a clustering objective that generalizes the popular modularity objective for graphs. From this, we derive an inference algorithm that generalizes the Louvain graph community detection method, and a faster, specialized variant in which edges are expected to lie fully within clusters. Using synthetic and empirical data, we demonstrate that the specialized method is highly scalable and can detect clusters where graph-based methods fail. We also use our model to find interpretable higher-order structure in school contact networks, U.S. congressional bill cosponsorship and committees, product categories in copurchasing behavior, and hotel locations from web browsing sessions.