  Cluster structure detection is a fundamental task for the analysis of graphs,
in order to understand and to visualize their functional characteristics. Among
the different cluster structure detection methods, spectral clustering is
currently one of the most widely used due to its speed and simplicity. Yet,
there are few theoretical guarantee to recover the underlying partitions of the
graph for general models. This paper therefore presents a variant of spectral
clustering, called 1-spectral clustering, performed on a new random model
closely related to stochastic block model. Its goal is to promote a sparse
eigenbasis solution of a 1 minimization problem revealing the natural structure
of the graph. The effectiveness and the robustness to small noise perturbations
of our technique is confirmed through a collection of simulated and real data
examples.
