Normalized Likelihood Criteria for Model Selection in the Stochastic Block Model
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910121267822592 |
|---|---|
| author | Cerqueira, Andressa Baptistão, Felipe |
| author_facet | Cerqueira, Andressa Baptistão, Felipe |
| contents | Estimating the number of communities is a fundamental problem in network analysis under the stochastic block model (SBM). In this paper, we study penalized estimators for this task based on normalized likelihood criteria. We show that a penalized estimator derived from the Normalized Maximum Likelihood (NML) is strongly consistent with a logarithmic penalty term, although its computation is intractable. To overcome this limitation, we consider the Normalized Maximum Complete Likelihood (NMCL) and the Decomposed Normalized Maximum Likelihood (DNML). The DNML admits an explicit formulation with cubic computational complexity in the number of nodes. We prove that the NMCL- and DNML- based estimators are strongly consistent for sparse networks in which the average node degree diverges with the network size. Empirical results show that the DNML estimator performs competitively with existing methods, particularly in unbalanced networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_10205 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Normalized Likelihood Criteria for Model Selection in the Stochastic Block Model Cerqueira, Andressa Baptistão, Felipe Statistics Theory Estimating the number of communities is a fundamental problem in network analysis under the stochastic block model (SBM). In this paper, we study penalized estimators for this task based on normalized likelihood criteria. We show that a penalized estimator derived from the Normalized Maximum Likelihood (NML) is strongly consistent with a logarithmic penalty term, although its computation is intractable. To overcome this limitation, we consider the Normalized Maximum Complete Likelihood (NMCL) and the Decomposed Normalized Maximum Likelihood (DNML). The DNML admits an explicit formulation with cubic computational complexity in the number of nodes. We prove that the NMCL- and DNML- based estimators are strongly consistent for sparse networks in which the average node degree diverges with the network size. Empirical results show that the DNML estimator performs competitively with existing methods, particularly in unbalanced networks. |
| title | Normalized Likelihood Criteria for Model Selection in the Stochastic Block Model |
| topic | Statistics Theory |
| url | https://arxiv.org/abs/2604.10205 |