Estimating The Number Of Communitie In Stochastic Block Models By Spectral Methods

Community detection is the one of the most fundamental problem in network analysis.Spectral clustering is widely used.In this paper,we apply the non-backtracking operator and the Bethe Hessian operator to estimate the number of communities.Under the stochastic block model,estimating the number of commu-nities K from the non-backtracking matrix is the number of the eigenvalues that are separated from the bulk of radius.The number of communities K is the number of negative eigenvalues of H(r).First,we introduce the non-backtracking matrix and the Bethe Hessian ma-trix based methods for estimating the number of communities.Second,we strictly prove the consistency of the Bethe Hessian matrix based method for estimating the number of communities under common condition.Finally under more representative probabilistic matrix PO,we compare three methods of BHa,BHac and NB under the stochastic block model.The main result is given through the following theorem:Theorem 2 Given that A is the adjacency matrix,let P = E[A]and rank(P)= K.(i)Assume that maxPij?1/2.Given that q = d*(1-d*/n),d*= n maxi,j Pij.Assume that q/(logn)8,?? with sufficiently large n,if Asn??,K is a consistent estimator ofK.(ii)Assume that maxi,j pij ?1/2.For sufficiently largen,if Asn??,K is a consistent estimator of K.