基于k-度匿名的社会网络隐私保护方法

doi:10.3969/j.issn.0372-2112.2016.06.026

电子学报 ›› 2016, Vol. 44 ›› Issue (6): 1437-1444.DOI: 10.3969/j.issn.0372-2112.2016.06.026

基于k-度匿名的社会网络隐私保护方法

龚卫华¹, 兰雪锋¹, 裴小兵², 杨良怀¹

1. 浙江工业大学计算机科学与技术学院, 浙江杭州 310023;
2. 华中科技大学软件学院, 湖北武汉 430074

收稿日期:2015-01-25 修回日期:2015-10-23 出版日期:2016-06-25
- 作者简介:
- 龚卫华 男,1977年生于湖北武汉,博士,现为浙江工业大学计算机学院副教授.主要研究方向:数据挖掘、社会网络、大数据计算等.E-mail:whgong@sohu.com;兰雪锋 男,1990年生于浙江丽水,浙江工业大学硕士生.主要研究方向:社会网络、隐私保护;裴小兵 男,1971年生于湖北,博士,现为华中科技大学软件学院副教授.主要研究方向:机器学习、数据挖掘、软件工程、电信网络管理.E-mail:xiaobingp@hust.edu.cn;杨良怀 男,1967年生于浙江新昌,博士,现为浙江工业大学计算机学院教授,主要研究方向:数据库系统、数据挖掘、大数据计算等.E-mail:yanglh@zjut.edu.cn
- 基金资助:
- 浙江省自然科学基金 (No.LY13F020026,No.Y1080102,No.LY14F020017,No.LY14C130005); 国家自然科学基金 (No.61571400,No.61070042); 中国博士后科学基金 (No.2015M581957); 浙江省博士后科研项目择优资助 (No.BSH1502019)

Privacy Preservation Method Based on k-Degree Anonymity in Social Networks

GONG Wei-hua¹, LAN Xue-feng¹, PEI Xiao-bing², YANG Liang-huai¹

1. School of Computer Science and Technology, Zhejiang University of Technology, Hangzhou, Zhejiang 310023, China;
2. School of Software Engineering, Huazhong University of Science and Technology, Wuhan, Hubei 430074, China

Received:2015-01-25 Revised:2015-10-23 Online:2016-06-25 Published:2016-06-25
- Supported by:
- National Natural Science Foundation ofZhejiang Province, China (No.LY13F020026, No.Y1080102, No.LY14F020017, No.LY14C130005); National Natural Science Foundation of China (No.61571400, No.61070042); China Postdoctoral Science Foundation (No.2015M581957); Funded by Zhejiang Provincial Postdoctoral Research Program (No.BSH1502019)

摘要/Abstract

摘要：

针对当前社会网络的匿名化隐私保护方法存在信息损失量巨大、网络关系结构被改变严重等问题,提出一种保持网络结构稳定的k-度匿名隐私保护模型SimilarGraph,运用动态规划方法对社会网络按照节点度序列进行最优簇划分,然后采用移动边操作方式重构网络图以实现图的k-度匿名化.区别于传统的数值扰乱或图修改如随机增加、删除节点或边等方法,该模型的优势在于既不增加网络边数和节点数,也不破坏网络原有连通性和关系结构.实验结果表明,SimilarGraph匿名化方法不仅能有效提高网络抵御度属性攻击的能力,并且还能保持网络结构稳定,同时具有较理想的信息损失代价.

关键词: 社会网络, 隐私保护, k-度匿名, 信息损失

Abstract:

To preserve the privacy of social networks, most existing methods are applied to satisfy different anonymity models, but some serious problems are involved such as often incurring large information losses and great structural modifications of original social network after being anonymized.Therefore, an improved privacy protection model called SimilarGraph is proposed, which is based on k-degree anonymous graph derived from k-anonymity to keep the network structure stable.Where the main idea of this model is firstly to partition network nodes into optimal number of clusters according to degree sequences based on dynamic programming, and then to reconstruct the network by means of moving edges to achieve k-degree anonymity with internal relations of nodes considered.To differentiate from traditional data disturbing or graph modifying method used by adding and deleting nodes or edges randomly, the superiority of our proposed scheme lies in which neither increases the number of nodes and edges in network, nor breaks the connectivity and relational structures of original network.Experimental results show that our SimilarGraph model can not only effectively improve the defense capability against malicious attacks based on node degrees, but also maintain stability of network structure.In addition, the cost of information losses due to anonymity is minimized ideally.

Key words: social network, privacy preservation, k-degree anonymity, information loss

中图分类号:

TP309.2

龚卫华, 兰雪锋, 裴小兵, 等. 基于k-度匿名的社会网络隐私保护方法[J]. 电子学报, 2016, 44(6): 1437-1444.

GONG Wei-hua, LAN Xue-feng, PEI Xiao-bing, et al. Privacy Preservation Method Based on k-Degree Anonymity in Social Networks[J]. Acta Electronica Sinica, 2016, 44(6): 1437-1444.

参考文献

[1] Boccaletti S,Latora V,Moreno Y,et al.Complex networks:structure and dynamics[J].Physics Reports,2006,424(4):175-308.
[2] Wang X F,Chen G R.Complex networks:small-world,scale-free and beyond[J].IEEE Circuits and Systems Magazine,2003,3(1):6-20.
[3] Faloutsos M,Faloutsos P,Faloutos C.On power-law relationships of the internet topology[A].ACM SIGCOMM'99[C].Cambridge,Massachusetts:ACM,1999.251-262.
[4] 童云海,陶有东,唐世渭,等.隐私保护数据发布中身份保持的匿名方法[J].软件学报,2010,21(4):771-781. Tong Yun-hai,Tao You-dong,Tang Shi-wei,et al.Identity-reserved anonymity in privacy preserving data publishing[J].Journal of Software,2010,21(4):771-781.(in Chinese)
[5] 黄茂峰,倪巍伟,王佳俊,等.一种面向聚类的对数螺线数据扰动方法[J].计算机学报,2012,35(11):2275-2282. Huang Mao-feng,Ni Wei-wei,Wang Jia-jun,et al.A logarithmic spiral based data perturbation method for clustering[J].Chinese Journal of Computers.2012,35(11):2275-2282.(in Chinese)
[6] 张啸剑,孟小峰.面向数据发布和分析的差分隐私保护[J].计算机学报,2014,37(4):927-949. Zhang Xiao-jian,Meng Xiao-feng.Differential privacy in data publication and analysis[J].Chinese Journal of Computers,2014,37(4):927-949.(in Chinese)
[7] Campan A,Truta T M,Cooper N.P-sensitive K-anonymity with generalization constraints[J].Transactions on Data Privacy,2010,3(2):65-89.
[8] Campan A,Truta TM.A clustering approach for data and structural anonymity in social networks[A].2nd ACM SIGKDD International Workshop on Privacy,Security,and Trust in KDD(PinKDD'08)[C].Las Vegas,NV:ACM,2008.33-54.
[9] 王智慧,许俭,汪卫,等.一种基于聚类的数据匿名方法[J].软件学报,2010,21(4):680-693. Wang Zhi-hui,Xu Jian,Wang Wei,et al.Clustering-Based approach for data anonymization[J].Journal of Software,2010,21(4):680-693.(in Chinese)
[10] 张健沛,谢静,杨静,等.基于敏感属性值语义桶分组的t-closeness隐私模型[J].计算机研究与发展,2014,51(1):126-137. Zhang Jianpei,Xie Jing,Yang Jing,et al.A t-closeness privacy model based on sensitive attribute values semantics bucketization[J].Journal of Computer Research and Development,2014,51(1):126-137.(in Chinese)
[11] 付艳艳,张敏,冯登国,等.基于节点分割的社交网络属性隐私保护[J].软件学报,2014,25(4):768-780. Fu Yan-yan,Zhang Min,Feng Deng-guo,et al.Attribute privacy preservation in social networks based on node anatomy[J].Journal of Software,2014,25(4):768-780.(in Chinese)
[12] Wu W T,Xiao Y H,Wang W,et al.k-symmetry model for identity anonymization in social networks[A].13th International Conference on Extending Database Technology(EDBT'10)[C].Lausanne,Switzerland:ACM,2010.111-122.
[13] Ying X,Wu X.On link privacy in randomizing social networks[J].Knowledge and Information Systems,2011,28(3):645-663.
[14] 刘华玲,郑建国,孙辞海.基于贪心扰动的社交网络隐私保护研究[J].电子学报,2013,41(8):1586-1591. Liu Hua-ling,Zheng Jian-guo,Sun Ci-hai.Privacy preserving in social networks based on greedy perturbation[J].Acta Electronica Sinica,2013,41(8):1586-1591.(in Chinese)
[15] 刘向宇,王斌,杨晓春.社会网络数据发布隐私保护技术综述[J].软件学报,2014,25(3):576-590. Liu Xiang-yu,Wang Bin,Yang Xiao-chun.Survey on privacy preserving techniques for publishing social network data[J].Journal of Software,2014,25(3):576-590.(in Chinese)
[16] Hay M,Miklau G,Jensen D,et al.Resisting structural re-identification in anonymized social networks[J].The VLDB Journal,2010,19(6):797-823.
[17] Skarkala M E,Maragoudakis M,Gritzalis S,et al.Privacy preservation by k-anonymization of weighted social networks[A].Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining(ASONAM)[C].Istanbul,Turkey:IEEE Computer Society,2012.423-428.
[18] Liu K,Terzi E.Towards identity anonymization on graphs[A].2008 ACM SIGMOD International Conference on Management of Data(SIGMOD'08)[C].New York:ACM,2008.93-106.
[19] Yuan M X,Chen L,Yu P S,et al.Protecting sensitive labels in social network data anonymization[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(3):633-647.
[20] Zhou B,Pei J.The K-anonymity and L-diversity approaches for privacy preservation in social networks against neighborhood attacks[J].Knowledge and Information Systems,2011,28(1):47-77.
[21] Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data[A].1st ACM SIGKDD Workshop on Privacy,Security,and Trust in KDD (PinKDD'07)[C].San Jose,CA:ACM,2007.153-171.
[22] Zou L,Chen L,Özsu M T.K-automorphism:a general framework for privacy preserving network publication[J].Proceedings of the VLDB Endowment,2009,2(1):946-957.

基于k-度匿名的社会网络隐私保护方法

Privacy Preservation Method Based on k-Degree Anonymity in Social Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	郭庆, 田有亮, 万良. 基于代理重加密的区块链数据受控共享方案[J]. 电子学报, 2023, 51(2): 477-488.
[2]	张少波, 原刘杰, 毛新军, 朱更明. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报, 2022, 50(9): 2181-2188.
[3]	丁毅, 沈薇, 李海生, 钟琼慧, 田明宇, 李洁. 面向CNN的区块链可信隐私服务计算模型[J]. 电子学报, 2022, 50(6): 1399-1409.
[4]	袁水莲, 皮德常, 胥萌. 基于差分隐私的轨迹隐私保护方法[J]. 电子学报, 2021, 49(7): 1266-1273.
[5]	朱健, 胡凯, 张伯钧. 智能合约的形式化验证方法研究综述[J]. 电子学报, 2021, 49(4): 792-804.
[6]	郑孝遥, 罗永龙, 汪祥舜, 孙丽萍, 陈付龙, 胡桂银, 汪小寒. 基于位置服务的分布式差分隐私推荐方法研究[J]. 电子学报, 2021, 49(1): 99-110.
[7]	高玉君, 梁刚, 蒋方婷, 许春, 杨进, 陈俊任, 王浩. 社会网络谣言检测综述[J]. 电子学报, 2020, 48(7): 1421-1435.
[8]	杨洁, 朱咸军, 周献中, 柳毅. 基于混杂社会网络的个性化Web服务推荐方法[J]. 电子学报, 2020, 48(2): 341-349.
[9]	陈传明, 林文诗, 俞庆英, 罗永龙. 一种基于单点收益的轨迹隐私保护方法[J]. 电子学报, 2020, 48(1): 143-152.
[10]	马慧芳, 刘文, 李志欣, 蔺想红. 融合耦合距离区分度和强类别特征的短文本相似度计算方法[J]. 电子学报, 2019, 47(6): 1331-1336.
[11]	宋海娜, 罗涛, 韩新宇, 李剑峰. 面向多敏感值的个性化随机响应机制设计与分析[J]. 电子学报, 2019, 47(6): 1236-1243.
[12]	杨高明, 朱海明, 方贤进, 苏树智. 局部差分隐私约束的关联属性不变后随机响应扰动[J]. 电子学报, 2019, 47(5): 1079-1085.
[13]	汪林玉, 谷科, 余飞, 尹波, 廖年冬. 基于个人意愿的社会网络团体结构与信息检测方案[J]. 电子学报, 2019, 47(4): 886-895.
[14]	朱恩强, 吴艳蕾, 许宇光, 牛云云. 基于树核度的社交网络影响最大化问题[J]. 电子学报, 2019, 47(1): 161-168.
[15]	罗恩韬, 陈淑红, 王文博, 张少波, PINIAL Khan-butt. 移动社交网络多密钥混淆的交友隐私保护方案研究[J]. 电子学报, 2018, 46(9): 2123-2130.