Method and system for partitioning of deduplication domains in storage systems. The method includes constructing a data structure having multiple nodes representing data chunks and edges between the nodes representing a weighting of deduplication references between the data chunks, and performing clustering of the nodes of the data structure to split the nodes into clusters of tightly related nodes based on the weightings of the edges. The data chunks represented by a cluster of nodes are migrated to a deduplication domain to restrict deduplication to between only the data chunks in the deduplication domain.