91社区

Title:聽Counting communities in weighted SBM via semidefinite programming

础产蝉迟谤补肠迟:听We present the problem of community detection and of estimating the number of communities in a weighted Stochastic Block Model (SBM) in the regime of diverging degrees. To obtain consistent estimators, our approach uses a universality result for semidefinite programming, which we establish, along with asymptotic knowledge of the eigenstructure of a GOE random matrix. In addition, we construct hypothesis tests able to distinguish between any two candidate numbers of communities in the graph. We point out that this application of semidefinite programming for both problems is new even for the well-studied case of the unweighted SBM.