structure, is used to check whether it displays the original cluster structure. [@Sussman12; @Lei15; @Rohe11] proved consistency of spectral clustering applied to stochastic block models for some specific adjacency type matrices. Even if the consistency of spectral clustering has been proved for stochastic block models, there is no convergence guarantee for general models. Thus, $k$-means can fail to reach the true underlying partitions of the graph. Moreover, spectral clustering technique fails to recover the original clusters when it comes to a higher randomization coefficient. This is mostly due to the computed eigenbasis that is not equally informative.

In order to tackle this issue, we develop an alternative method to the spectral clustering that promote a sparse eigenvectors basis solution of an $\ell_0$ optimization problem, corresponding to the indicator vectors of each cluster. Since the natural constrained $\ell_0$ is a NP-hard problem, it was then replaced by its convex relaxation $\ell_1$ [@Ramirez13]. Actually we can show that the solution of the $\ell_0$ optimization problem is still the same when replacing the $\ell_0$-norm by the $\ell_1$-norm if we add a constraint on the maximum of the coefficients. Hence, the algorithm turns out to solve an $\ell_1$-penalty optimization problem that is feasible and easy to implement, even for very large graphs. In a wider scope, research papers have explored differently regularized spectral clustering to robustly identify clusters in large networks. Although [@Zhang18] and [@Joseph16] show the effect of regularization on spectral clustering through graph conductance and respectively through stochastic block models. Equally, [@Lara19], shows on a simple block model that the spectral regularization separates the underlying blocks of the graph.

In this paper, we introduce in Section \[section2\] a new random graph model, used to solve spectral clustering (Section \[section3\]) and its new variant (Section \[section4\]) objective function. We prove the efficiency