Community detection in degree-corrected block models (Q1800797)

Understanding the community structure is crucial for the complex networks' internal organization research via finding underlying structures in the unlabeled network data. The main contribution of this paper are two theorems giving the minimax upper and lower bounds of the introduced maximum likelihood estimator. These theorems characterize the asymptotic behavior of the risk bounds. Proved general fundamental limits allow the community sizes to differ and the number of communities \(k\) to grow to infinity with the number of nodes \(n\). A polynomial-time algorithm is proposed to adaptively perform consistent and asymptotically optimal community detection since it does not involve convex programming. The efficiency of the constructed theory is confirmed by experimental results.