1
|
Kritschgau J, Kaiser D, Alvarado Rodriguez O, Amburg I, Bolkema J, Grubb T, Lan F, Maleki S, Chodrow P, Kay B. Community detection in hypergraphs via mutual information maximization. Sci Rep 2024; 14:6933. [PMID: 38521798 PMCID: PMC10960844 DOI: 10.1038/s41598-024-55934-5] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/08/2023] [Accepted: 02/29/2024] [Indexed: 03/25/2024] Open
Abstract
The hypergraph community detection problem seeks to identify groups of related vertices in hypergraph data. We propose an information-theoretic hypergraph community detection algorithm which compresses the observed data in terms of community labels and community-edge intersections. This algorithm can also be viewed as maximum-likelihood inference in a degree-corrected microcanonical stochastic blockmodel. We perform the compression/inference step via simulated annealing. Unlike several recent algorithms based on canonical models, our microcanonical algorithm does not require inference of statistical parameters such as vertex degrees or pairwise group connection rates. Through synthetic experiments, we find that our algorithm succeeds down to recently-conjectured thresholds for sparse random hypergraphs. We also find competitive performance in cluster recovery tasks on several hypergraph data sets.
Collapse
Affiliation(s)
- Jürgen Kritschgau
- Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, 15213, USA
| | - Daniel Kaiser
- Department of Informatics, Indiana University, Bloomington, IN, 47408, USA
| | | | - Ilya Amburg
- Pacific Northwest National Laboratory, Richland, WA, 99354, USA
| | - Jessalyn Bolkema
- Department of Mathematics, California State University, Dominguez Hills, Carson, CA, 90747, USA
| | - Thomas Grubb
- University of California San Diego, San Diego, CA, 92093, USA
| | - Fangfei Lan
- Scientific Computing and Imaging Institute, University of Utah, Salt Lake City, UT, 84112, USA
| | - Sepideh Maleki
- Department of Computer Science, University of Texas at Austin, Austin, TX, 78712, USA
| | - Phil Chodrow
- Department of Computer Science, Middlebury College, Middlebury, VT, 05753, USA
| | - Bill Kay
- Pacific Northwest National Laboratory, Richland, WA, 99354, USA.
| |
Collapse
|