No Access

Partial $k$ $k$ -Anonymity for Privacy-Preserving Social Network Data Publishing

School of Computer Science and Engineering, Beihang University, Haidian, Beijing 100191, P. R. China

Guangxi Key Lab of Multi-Source Information Mining and Security, Guangxi Normal University, Guilin, Guangxi 541004, P. R. China

E-mail Address: liupeng@gxnu.edu.cn

Search for more papers by this author

Yan Bai

Institute of Technology, University of Washington Tacoma, Tacoma, WA 98402, USA

E-mail Address: yanb@uw.edu

Search for more papers by this author

Lie Wang

Guangxi Key Lab of Multi-Source Information Mining and Security, Guangxi Normal University, Guilin, Guangxi 541004, P. R. China

E-mail Address: wanglie@gxnu.edu.cn

Search for more papers by this author

, and

Xianxian Li

School of Computer Science and Engineering, Beihang University, Haidian, Beijing 100191, P. R. China

Guangxi Key Lab of Multi-Source Information Mining and Security, Guangxi Normal University, Guilin, Guangxi 541004, P. R. China

E-mail Address: lixx@gxnu.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218194017500048Cited by:15 (Source: Crossref)

Abstract

With the popularity of social networks, privacy issues with regard to publishing social network data have gained intensive focus from academia. We analyzed the current privacy-preserving techniques for publishing social network data and defined a privacy-preserving model with privacy guarantee $k$ $k$ . With our definitions, the existing privacy-preserving methods, $k$ $k$ -anonymity and randomization can be combined together to protect data privacy. We also considered the privacy threat with label information and modify the $k$ $k$ -anonymity technique of tabular data to protect the published data from being attacked by the combination of two types of background knowledge, the structural and label knowledge. We devised a partial $k$ $k$ -anonymity algorithm and implemented it in Python and open source packages. We compared the algorithm with related $k$ $k$ -anonymity and random techniques on three real-world datasets. The experimental results show that the partial $k$ $k$ -anonymity algorithm preserves more data utilities than the $k$ $k$ -anonymity and randomization algorithms.

Keywords:

References

1. L. Backstrom, C. Dwork and J. Kleinberg , Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography, in Proc. 16th Int. Conf. World Wide Web, 2007, pp. 181–190. Google Scholar
2. A. Campan and T. M. Truta , Data and structural $k$ $k$ -anonymity in social networks, in Privacy, Security, and Trust in KDD (Springer, 2009), pp. 33–54. Crossref, Google Scholar
3. J. Cheng, A. W.-C. Fu and J. Liu , $K$ $K$ -isomorphism: Privacy preserving network publication against structural attacks, in Proc. 2010 ACM SIGMOD Int. Conf. Management of Data, 2010, pp. 459–470. Google Scholar
4. S. Chester et al., $k$ $k$ -Anonymization of social networks by vertex addition, in Proc. 15th East-European Conf. ADBIS, Vol. 789, 2011, pp. 107–116. Google Scholar
5. K. L. Clarkson, K. Liu and E. Terzi , Toward identity anonymization in social networks, in Link Mining: Models, Algorithms, and Applications (Springer, 2010), pp. 359–385. Crossref, Google Scholar
6. M. Hay et al., Resisting structural re-identification in anonymized social networks, in Proc. VLDB Endowment, Vol. 1, 2008, pp. 102–114. Google Scholar
7. K. Liu and E. Terzi , Towards identity anonymization on graphs, in Proc. ACM SIGMOD Int. Conf. Management of Data, 2008, pp. 93–106. Google Scholar
8. L. Sweeney , $k$ $k$ -Anonymity: A model for protecting privacy, Int. J. Uncertain. Fuzziness Knowl.-Based Syst. 10 (2002) 557–570. Link, Web of Science, Google Scholar
9. C.-H. Tai et al., Privacy-preserving social network publication against friendship attacks, in Proc. 17th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, 2011, pp. 1262–1270. Google Scholar
10. L. Wang and X. Li , A clustering-based bipartite graph privacy-preserving approach for sharing high-dimensional data, Int. J. Softw. Eng. Knowl. Eng. 24 (07) (2014) 1091–1111. Link, Web of Science, Google Scholar
11. T. M. Truta et al., Centrality preservation in anonymized social networks, in Proc. 7th Int. Conf. Data Mining, 2011. Google Scholar
12. W. Wu et al., $k$ $k$ -Symmetry model for identity anonymization in social networks, in Proc. 13th Int. Conf. Extending Database Technology, 2010, pp. 111–122. Google Scholar
13. M. Yuan, L. Chen and P. S. Yu , Personalized privacy protection in social networks, in Proc. VLDB Endowment, Vol. 4, 2010, pp. 141–150. Google Scholar
14. B. Zhou and J. Pei , Preserving privacy in social networks against neighborhood attacks, in Proc. IEEE 24th Int. Conf. Data Engineering, 2008, pp. 506–515. Google Scholar
15. B. Zhou and J. Pei , The $k$ $k$ -anonymity and $l$ $l$ -diversity approaches for privacy preservation in social networks against neighborhood attacks, Knowl. Inf. Syst. 28 (2011) 47–77. Crossref, Web of Science, Google Scholar
16. L. Zou, L. Chen and M. T. Özsu , $K$ $K$ -automorphism: A general framework for privacy preserving network publication, in Proc. VLDB Endowment, Vol. 2, 2009, pp. 946–957. Google Scholar
17. P. Liu, L. Cui and X. Li , A hybrid algorithm for privacy preserving social network publication, in Advanced Data Mining and Applications (Springer International, 2014), pp. 267–278. Crossref, Google Scholar
18. P. Boldi et al., Injecting uncertainty in graphs for identity obfuscation, in Proc. VLDB Endowment, Vol. 5, 2012, pp. 376–1387. Google Scholar
19. M. Hay et al., Anonymizing social networks, Paper 180, Computer Science Department Faculty Publication Series, University of Massachusetts-Amherst (2007). Google Scholar
20. H. Kargupta et al., Random-data perturbation techniques and privacy-preserving data mining, Knowl. Inf. Syst. 7 (2005) 387–414. Crossref, Web of Science, Google Scholar
21. J. P. Reiter , Estimating risks of identification disclosure in microdata, J. Am. Stat. Assoc. 100 (2005) 1103–1112. Crossref, Web of Science, Google Scholar
22. X. Ying et al., Comparisons of randomization and $K$ $K$ -degree anonymization schemes for privacy preserving social network publishing, in Proc. 3rd Workshop on Social Network Mining and Analysis, 2009. Google Scholar
23. X. Ying and X. Wu , Randomizing social networks: A spectrum preserving approach, in Proc. SIAM Int. Conf. Data Mining, 2008, pp. 2739–2750. Google Scholar
24. X. Ying and X. Wu , On link privacy in randomizing social networks, Knowl. Inf. Syst. 28 (2011) 645–663. Crossref, Web of Science, Google Scholar
25. N. Vuokko and E. Terzi , Reconstructing randomized social networks, in Proc. SIAM Int. Conf. Data Mining, 2010, pp. 49–59. Google Scholar
26. B. Fung et al., Privacy-preserving data publishing: A survey of recent developments, ACM Comput. Surv. 42 (4) (2010) 14. Crossref, Web of Science, Google Scholar
27. M. I. H. Ninggal, Data privacy in social networks, Computing Series, Technical report C11/3, Deakin University, Australia, 2011. Google Scholar
28. L. Page, S. Brin, R. Motwani and T. Winograd, The PageRank citation ranking: Bringing order to the Web, Technical Report SIDL-WP-1999-0120, Stanford University, 1999. Google Scholar
29. J. J. McAuley and J. Leskovec , Learning to discover social circles in ego networks, in Proc. 25th Advances in Neural Information Processing Systems, 2010, pp. 548–556. Google Scholar
30. J. Tang, J. Sun, C. Wang and Z. Yang , Social influence analysis in large-scale networks, in Proc. 15th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, 2009, pp. 807–816. Google Scholar