Before revision:  As we show, such  estimator has a nearly-linear computational complexity for sparse graphs under certain assumptions.
After revision:  As we show, such an estimator has a nearly-linear computational complexity for sparse graphs under certain assumptions.