Techniques, an apparatus and an article of manufacture for distributed scalable clustering and community detection. A method includes generating a label for each node in a graph, wherein said label identifies a community in which a node participates, propagating each label locally within two or more segments of the graph based on a participation percentage of each node in at least one identified community within the graph, and deriving at least one cluster of nodes in the graph that corresponds to the at least one identified community based on said propagating.