Abstract: The release of social networks in digital media has verified many benefits in our daily life, but the user privacy breach accompanies this intensification in popularity. Various methods has been used for publishing the social network data, the privacy preservation of the individuals in the data published has become a significant concern. Several works in relational data showed that the degree of privacy preservation does not depend on the size of the equivalence classes on quasi identifier attributes; it is determined by the number and distribution of distinct sensitive values associated with each equivalence class.