Using graph clustering, we improve accuracy of Kronecker social networks which are protected by differential privacy. Ensuring the differential privacy implicates addition of marginal changes to the network and publishing the modified network data. In many cases, it induces a large gap between the original network and the modified graph statistics, such that very little useful information can be inferred from the published graph. We use the fact that network structures in all graph clusters are similar, to improve the utility of the publication methods based on Kronecker graphs. Instead of anonymizing the social network as a whole, we anonymize each cluster of the network separately, and combine the sanitized results thereafter. We justify why this idea provides an anonymized social network with high utility and also prove that our output social network ensures rigorous differential privacy guarantees. Our experimental results show that our mechanism exhibits good agreement of the structural properties with the real graphs, and outperforms the existing anonymization techniques for certain utility measures. © 2020 IEEE.