ers of a dataset such that the sum squared of distances of each point to its closest cluster center is minimized. Lloyd’s 1957 procedure [@Lloyd82] remains one of the widely used because of its speed and simplicity. It has been studied for several decades [@Lloyd82; @Wu08] and many versions of this technique has recently been developed. [@Xu19] proposed alternatives to Lloyd’s algorithm that preserves its simplicity, makes it more robust to initialization and relieves its tendency to get trapped by local minima. [@Lattanzi19] developed a new variant of $k$-means++ seeding algorithm [@Arthur07] to achieve a constant approximation guarantee.

**Our contribution.** Observed real networks differ from random graphs from their edge distribution and from their underlying structures. Erdös Renyi random graphs models [@Erdos59], where all the pairs of nodes have equal probability of being connected by an edge, independently of all other pairs fail to model real observed graphs. Additionnally, stochastic block models are not always relevant to infer their structures. To remedy this problem, we developed a new random model, closely related to stochastic block model, but better suited to model graphs that have been inferred from the observations. In practice, graphs that are studied are not known beforehand but often estimated.To achieve a good clustering recovery, random graph models are often associated to their similarity matrix to maintain the clustering structure of the graph. [@Wang16] developed a model to learn a doubly stochastic matrix which encodes the probability of each pair of data points to be connected, used to normalize the affinity matrix such that the data graph is more suitable for clustering tasks. [@Peng15] has shown that for a wide class of graphs, spectral clustering gives a good approximation of the optimal cluster. In our model, we assume that a group does not emerge by chance but because there exists an underlying structure. This randomized version of the deterministic graph with exact cluster 