Clustering is a central problem in machine learning for which graph-based approaches have proven their efficiency. In this paper, we study a relaxation of the modularity maximization problem, well-known in the graph partitioning literature. A solution of this relaxation gives to each element of the dataset a probability to belong to a given cluster, whereas a solution of the standard modularity problem is a simple partition. We introduce an efficient optimization algorithm to solve this relaxation, that is both memory efficient and local, and show that our method includes the Louvain algorithm, a state-of-the-art technique to solve the traditional modularity problem. Experiments on both synthetic and real-world data show that our approach provides meaningful information on various types of data.