Preservation of Attribute Couplet Attack by Node Addition in Social Networks

Social Network is one of the most desired platform where an immense amount of data are available from many different social platforms. Publishing data without hiding sensitive data or diplomatic data about individuals is a crucial problem which cannot guarantees the privacy. Therefore published data needs to remove identifying particulars of the individuals (anonymized) before the data is released. Anonymizing data is more challenging and a popular privacy preserving model for data publishing in social networks. However even after anonymizing the data sets, attackers try to find new methods to derive private information of individuals with some background knowledge and identify them. One of such method is attribute couplet attack where the attacker has some background information about the data and derive the identity using a pair of node attributes. In the existing approach, the k-couplet anonymity achieves the privacy under the attribute couplet attack by using edge modification approach. This will change the distance properties between nodes and might also introduce undesirable and misleading fake relations. In this paper, we design an algorithm named Couplet Anonymization by using node addition approach. Adding new nodes and connecting them to some of the nodes in the original network can avoid this attribute couplet attack and gives a better chance to preserve the network properties. This node addition helps to reduce the misleading fake relations and also preserves the utility of the social networks.