Journal
JOURNAL OF MACHINE LEARNING RESEARCH
Volume 23, Issue -, Pages -Publisher
MICROTOME PUBL
Keywords
blockmodel; eigenmodel; minimax rates; social network; spectral clustering
Ask authors/readers for more resources
This paper presents a simple community detection algorithm that achieves consistency and optimality for a broad and flexible class of sparse latent space models. The algorithm is based on spectral clustering and local refinement through normalized edge counting, and it is easy to implement and computationally efficient. The proof of optimality is based on an interesting equivalence between likelihood ratio test and edge counting in a simple vs. simple hypothesis testing problem, which could be of independent interest.
We show that a simple community detection algorithm originated from stochastic block -model literature achieves consistency, and even optimality, for a broad and flexible class of sparse latent space models. The class of models includes latent eigenmodels (Hoff, 2008). The community detection algorithm is based on spectral clustering followed by local refine-ment via normalized edge counting. It is easy to implement and attains high accuracy with a low computational budget. The proof of its optimality depends on a neat equivalence between likelihood ratio test and edge counting in a simple vs. simple hypothesis testing problem that underpins the refinement step, which could be of independent interest.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available