The community structure of complex networks reveals hidden relationships in the organization of their constituent nodes. Indeed, many practical problems stemming from different fields of knowledge such as Biology, Sociology, Chemistry and Computer Science can be modeled as a graph. Therefore, graph analysis and community detection have become a key component for understanding the inherent relational characteristics underlying different systems and processes. In this regard, distinct unsupervised quality metrics such as conductance, coverage and modularity, have upsurged in order to evaluate the clustering arrangements based on structural and topological characteristics of the cluster space. In this regard graph clustering can be formulated as an optimization problem based on the maximization of one of such metrics, for which a number of nature-inspired heuristic solvers has been proposed in the literature. This paper elaborates on a novel local search method that allows boosting the convergence of such heuristics by estimating and sampling the cluster arrangement distribution from the set of intermediate produced solutions of the algorithm at hand. Simulation results reveal a generalized better performance compared towards other community detection algorithms in synthetic and real datasets.