Preserving the Relationship Privacy of the published social-network data based on Compressive Sensing

With the constant increase of social-network data published, the privacy preservation becomes more and more important. Although some literature algorithms apply K-anonymity to the relational data to prevent an adversary from significantly perpetrating privacy breaches, the inappropriate choice of K has a big impact on the quality of privacy protection and data utility. We propose a technique named Relationship Privacy Preservation based on Compressive Sensing (RPPCS) in this paper to anonymize the relationship data of social networks. The network links are randomized from the recovery of the random measurements of the sparse relationship matrix to both preserve the privacy and data utility. Two comprehensive sets of real-world relationship data on social networks are applied to evaluate the performance of our anonymization technique. Our performance evaluations based on Collaboration Network and Gnutella Network demonstrate that our scheme can better preserve the utility of the anonymized data compared to peer schemes. Privacy analysis shows that our scheme can resist the background knowledge attack.