Optimal Estimation of the Number of Network Communities
Jiashun Jin, Zheng Tracy Ke, Shengming Luo, Minzhe Wang
Abstract
In network analysis, how to estimate the number of communities K is a fundamental problem. We consider a broad setting where we allow severe degree heterogeneity and a wide range of sparsity levels, and propose Stepwise Goodness of Fit (StGoF) as a new approach. This is a stepwise algorithm, where for m=1, 2, … , we alternately use a community detection step and a goodness of fit (GoF) step. We adapt SCORE Jin for community detection, and propose a new GoF metric. We show that at step m, the GoF metric diverges to ∞ in probability for all m
Topics & Concepts
Metric (unit)MathematicsGoodness of fitRange (aeronautics)Degree (music)Eigenvalues and eigenvectorsAlgorithmComputer scienceApplied mathematicsStatisticsMathematical optimizationPhysicsMaterials scienceQuantum mechanicsOperations managementEconomicsAcousticsComposite materialComplex Network Analysis TechniquesOpinion Dynamics and Social InfluenceAdvanced Graph Neural Networks