Privacy Protection Method for k Degree Anonymity Based on Node Classification

doi:10.19678/j.issn.1000-3428.0054407

Abstract

Abstract: Existing k degree anonymous privacy protection methods usually damage the graph structure significantly and cannot resist structural background knowledge attacks.To address the problem,this paper proposes an improved k degree anonymous privacy protection method.The method introduces the concept of community,and divides nodes into two types which including nodes in the community and edge nodes that connect communities.The importance of nodes is differentiated,and the degree anonymity of the nodes in the community and the community sequence anonymity of the edge nodes are implemented,thereby the k degree anonymity of the entire social network is completed.Experimental results show that the proposed method reduces the practical loss of data,and can resist attacks that take node degree and community relationship as background knowledge.Thus,privacy protection is enhanced.

Key words: social network, privacy protection, edge node, k degree anonymity, community

摘要： 针对传统k度匿名隐私保护方法严重破坏图结构和无法抵抗结构性背景知识攻击的问题，提出改进的k度匿名隐私保护方法。引入社区的概念，将节点划分为社区内节点和连接社区的边缘节点两类，通过区分不同节点的重要性，实现社区内节点的度匿名和边缘节点的社区序列匿名，从而完成整个社交网络的k度匿名。实验结果表明，该方法可降低数据实用性损失，抵抗以节点的度和节点所在社区关系为背景知识的攻击，提升隐私保护力度。

关键词: 社交网络, 隐私保护, 边缘节点, k度匿名, 社区

CLC Number:

TP393

JIN Ye, DING Xiaobo, GONG Guoqiang, Lü Ke. Privacy Protection Method for k Degree Anonymity Based on Node Classification[J]. Computer Engineering, 2020, 46(3): 138-143.

金叶, 丁晓波, 龚国强, 吕科. 基于节点分类的k度匿名隐私保护方法[J]. 计算机工程, 2020, 46(3): 138-143.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0054407

http://www.ecice06.com/EN/Y2020/V46/I3/138

Figures/Tables 10

References

[1] HEATHERLY R,KANTARCIOGLU M.Preventing private information inference attacks on social networks[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(8):1849-1862.
[2] LIU Xiangyu,WANG Bin,YANG Xiaochun.Survey on privacy preserving techniques for publishing social network data[J].Journal of Software,2014,25(3):576-590.(in Chinese)刘向宇,王斌,杨晓春.社会网络数据发布隐私保护技术综述[J].软件学报,2014,25(3):576-590.
[3] JI S,MITTAL P,BEYAH R.Graph data anonymization,de-anonymization attacks,and de-anonymizability quantification:a survey[J].IEEE Communications Surveys and Tutorials,2017,19(2):1305-1326.
[4] SWEENEY L.k-anonymity:a model for protecting privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):557-570.
[5] JIA Junjie,YAN Guolei.A personalized (p,k)-anonymity privacy protection algorithm[J].Computer Engineering,2018,44(1):176-181.(in Chinese)贾俊杰,闫国蕾.一种个性化(p,k)匿名隐私保护算法[J].计算机工程,2018,44(1):176-181.
[6] MACHANAVAJJHALA A,GEHRKE J,KIFER D,et al.L-diversity:privacy beyond k-anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2006:1-24.
[7] JIANG Wenhuo,ZHAN Qinghua,LIU Wenjuan,et al.Clustering-anonymity approach for privacy preservation of graph data-publishing[J].Journal of Software,2017,28(9):2323-2333.(in Chinese)姜火文,占清华,刘文娟,等.图数据发布隐私保护的聚类匿名方法[J].软件学报,2017,28(9):2323-2333.
[8] REN Xiangmin,JIA Boxuan,WANG Kechao,et al.Research on K-anonymity privacy protection of social network[J].Applied Mechanics and Materials,2014,530-531:701-704.
[9] LIU K,TERZI E.Towards identity anonymization on graphs[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2008:93-106.
[10] CASAS-ROMA J,HERRERA-JOANCOMARTÍ J.k-Degree anonymity and edge selection:improving data utility in large networks[J].Knowledge and Information Systems,2017,50(2):447-474.
[11] YU F,CHEN M,YU B,et al.Privacy preservation based on clustering perturbation algorithm for social network[J].Multimedia Tools and Applications,2018,77(9):11241-11258.
[12] LÜ Y,MA T,TANG M,et al.An efficient and scalable density-based clustering algorithm for datasets with complex structures[J].Neurocomputing,2016,171:9-22.
[13] OKADA R,WATANABE C,KITAGAWA H.A k-anonymization algorithm on social network data that reduces distances between nodes[C]//Proceedings of the 33rd International Symposium on Reliable Distributed Systems Workshops.Washington D.C.,USA:IEEE Press,2014:76-81.
[14] WATTS D J.Networks,dynamics,and the small-world phenomenon[J].American Journal of Sociology,1999,105(2):1-10.
[15] NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.
[16] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):1-14.
[17] LI Yidong,SHEN Hong,LANG Congyan,et al.Practical anonymity models on protecting private weighted graphs[J].Neurocomputing,2016,218:359-370.
[18] Stanford large network dataset collection[EB/OL].[2019-02-13].http://snap.stanford.edu/data/index.html.
[19] LI M,LIU Z,DONG K.Privacy preservation in social network against public neighborhood attacks[C]//Proceedings of 2016 IEEE Trustcom/BigDataSE/ISPA.Washington D.C.,USA:IEEE Press,2016:1-5.
[20] TAI C H,YU P S,YANG D N,et al.Privacy-preserving social network publication against friendship attacks[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington D.C.,USA:IEEE Press,2011:1262-1273.
[21] ZHANG X K,FEI S,SONG C,et al.Label propagation algorithm based on local cycles for community detection[J].International Journal of Modern Physics B,2015,29(5):5-29.

Please choose a citation manager

Content to export