Abstract
Online Social Networks (OSNs) data are published to be used for the purpose of analysis in scientific research. Yet, offering such data in its crude structure raises serious privacy concerns. An adversary may attack the privacy of certain victims easily by collecting local background knowledge about individuals in a social network such as information about its neighbors. The subgraph attack that is based on frequent pattern mining and members' background information may be used to breach the privacy in the published social networks. Most of the current anonymization approaches do not guarantee the privacy preserving of identities from attackers in case of using the frequent pattern mining and background knowledge. In this paper, a secure kappa-anonymity algorithm that protects published social networks data against subgraph attacks using background information and frequent pattern mining is proposed. The proposed approach has been implemented and tested on real datasets. The experimental results show that the anonymized OSNs can preserve the major characteristics of original OSNs as a tradeoff between privacy and utility.