Privacy concerns of users threaten the usage of online social networks (OSN). In this regard, privacy preserving of OSN emerged as a convincing solution for preserving the privacy of users and uncovering useful insights from the social network data. In this article, we propose a novel algorithm based on the fuzzy sets and rewiring algorithm for preserving the privacy of users. This article presents the algorithm called privacy-preserving rewiring algorithm (PPRA), which can be used for anonymizing the social network data. The algorithm is validated by showing its effectiveness on four real-world datasets across three major graph mining tasks. The proposed PPRA algorithm will help in preserving the privacy of users in the OSN graph while simultaneously maintaining the utility that can be generated from the OSN graph structure. IEEE