In Eq.(3.2), the matrix $L_k$ should be called normalized adjacency matrix rather than normalized laplacian matrix.
In the time complexity analysis at the end of Section 3, the *second* summation $\sum_i=1^g$ should be $\sum_j=1^g$.