Counting communities in weighted Stochastic Block Models via semidefinite programming

We consider the problem of estimating the number of communities in a weighted balanced Stochastic Block Model. We construct hypothesis tests based on semidefinite programming and with a statistic coming from a GOE matrix to distinguish between any two candidate numbers of communities. This is possible due to a universality result for a semidefinite programming-based function that we also prove. The tests are then used to form a sequential test to estimate the number of communities. Furthermore, we also construct estimators of the communities themselves.

Bayesian Modeling and Causal Inference Bayesian Methods and Mixture Models Opinion Dynamics and Social Influence

View graph Source

Paper

Similar papers

Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block ModelsYuchen Liu, Xiaodong Li2024 · International Conference on Artificial Intelligence and Statistics · 0 citations In Library

Estimation of the Number of Communities in the Stochastic Block ModelAndressa Cerqueira, Florencia Leonardi2020 · IEEE Transactions on Information Theory In Library

Determining the Number of Communities in Degree-corrected Stochastic Block ModelsShujie Ma, Liangjun Su, Yichong Zhang2018 · Journal of machine learning research · 55 citations In Library

Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphsElchanan Mossel, Allan Sly, Youngtak Sohn2024 · arXiv (Cornell University) In Library

Community Detection in the Stochastic Block Model by Mixed Integer ProgrammingBreno Serrano, Thibaut Vidal2021 · Pattern Recognition · 13 citations In Library

Achieving Optimal Misclassification Proportion in Stochastic Block ModelChao Gao, Zongming Ma, A. Zhang et al.2015 · Journal of machine learning research · 248 citations In Library

Provable Estimation of the Number of Blocks in Block ModelsBowei Yan, Purnamrita Sarkar, Xiuyuan Cheng2017 · International Conference on Artificial Intelligence and Statistics · 35 citations In Library

Bayesian Modeling of the Stochastic Block Model for Weighted Network Data with Zero-Inflated Negative Binomial DistributionFumiya Iwashige2026 · arXiv (Cornell University) In Library

Community detection for weighted bipartite networksHuan Qing, Jingli Wang2021 · Knowledge-Based Systems · 19 citations In Library

Improved Community Detection using Stochastic Block ModelsMinhyuk Park, Daniel Wang Feng, Siya Digra et al.2024 · arXiv (Cornell University) In Library

Source of record

OpenAlex

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal