  Due to the technological progress of the last decades, Community Detection
has become a major topic in machine learning. However, there is still a huge
gap between practical and theoretical results, as theoretically optimal
procedures often lack a feasible implementation and vice versa. This paper aims
to close this gap and presents a novel algorithm that is both numerically and
statistically efficient. Our procedure uses a test of homogeneity to compute
adaptive weights describing local communities. The approach was inspired by the
Adaptive Weights Community Detection (AWCD) algorithm by Adamyan et al. (2019).
This algorithm delivered some promising results on artificial and real-life
data, but our theoretical analysis reveals its performance to be suboptimal on
a stochastic block model. In particular, the involved estimators are biased and
the procedure does not work for sparse graphs. We propose significant
modifications, addressing both shortcomings and achieving a nearly optimal rate
of strong consistency on the stochastic block model. Our theoretical results
are illustrated and validated by numerical experiments.
