Generative hypergraph clustering: From blockmodels to modularity

Philip S. Chodrow

doi:10.1126/sciadv.abh1303

Generative hypergraph clustering: From blockmodels to modularity

2021-07-09

79

OA

AI

DOI：10.1126/sciadv.abh1303

原文链接

查看原文

摘要

En 中文

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.

Keyword:

COMMUNITY STRUCTURE

MODELS

ALGORITHM

NETWORKS

Generative hypergraph clustering: From blockmodels to modularity

摘要

AI总结

期刊

机构