基于聚类的社交网络隐私保护方法

计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 154-160.doi: 10.11896/jsjkx.180901749

基于聚类的社交网络隐私保护方法

周艺华, 张冰, 杨宇光, 侍伟敏

(北京工业大学信息学部北京100124)
(可信计算北京市重点实验室北京100124)

收稿日期:2018-09-16 修回日期:2019-04-21 出版日期:2019-10-15 发布日期:2019-10-21
作者简介:周艺华(1969-),男,博士,副教授,主要研究方向为网络与信息安全、密码学、可信计算,E-mail:zhouyh@bjut.edu.cn;张冰(1994-),女,硕士生,主要研究方向为信息安全;杨宇光(1976-),女,博士,教授,主要研究方向为信息安全与其他学科的交叉;侍伟敏(1978-),女,博士,主要研究方向为网络与信息安全、密码学、信息安全与其他学科的交叉。
基金资助:
本文受北京市自然科学基金资助项目(4182006),国家自然科学基金项目(61572053)资助。

Cluster-based Social Network Privacy Protection Method

ZHOU Yi-hua, ZHANG Bing, YANG Yu-guang, SHI Wei-min

(Faculty of Information Technology,Beijing University of Technology,Beijing 100124,China)
(Beijing Key Laboratory of Trusted Computing,Beijing 100124,China)

Received:2018-09-16 Revised:2019-04-21 Online:2019-10-15 Published:2019-10-21

摘要/Abstract

摘要： 随着社交网络的迅速发展,社交网络积累了大量的数据,它们在一定程度上反映了社会规律。针对如何在保证隐私安全的前提下挖掘出有效知识的问题,提出了基于聚类的社交网络隐私保护方法,该方法具有隐私保护力度自适应、匿名模型安全性和有效性高的特点。该方法基于用户信息和社交关系进行聚类,将社交网络中的所有节点根据节点间的距离聚类为至少包含k个节点的超点,并对超点进行匿名化处理。匿名后的超点能够有效地防范以节点属性隐私、子图结构等为背景知识的各类隐私攻击,使攻击者无法以大于1/k的概率来识别用户。根据聚类算法和社交网络的特点优化聚类过程中初始节点的选取算法和节点间距的计算方法;同时通过结合自适应思想,优化隐私保护力度的选取方法,有效地减少了信息损失,提高了数据有效性。在Matlab上使用不同的数据集进行实验验证,结果表明所提算法在信息损失和运行时间上均优于其他相关方法,进一步证明了它的有效性和安全性。

关键词: k-匿名, 聚类, 社交网络, 信息安全, 隐私保护

Abstract: With the rapid development of social networks,social networks have accumulated a large amount of data,which reflect the social laws to some extent.Aiming at mining effective knowledge under the premise of ensuring privacy,this paper proposed a clustering-based social network privacy protection method.The method has the characteristics of adaptive privacy protection strength,high security and effectiveness of anonymity model.Clustering is conducted based on user information and social relationships.It clusters all nodes in the social network into a super point containing at least k nodes according to the distance between nodes,and then the super points are anonymized.Anonymous super points can effectively prevent various types of privacy attacks taking node attribute privacy and sub-graph structure as background knowledge,so that attackers cannot identify users with a probability greater than 1/k.According to the characteristics of clustering algorithm and social network,the initial node selection algorithm and node spacing calculation method in clustering process are optimized,and by combining the adaptive thinking,the selection method of privacy protection strength is also optimized,which effectively reduces information loss and improves data validity.Experiments were carried out on Matlab platform with different data sets.The results show that the proposed method issuperior to other related methods in terms of information loss and running time,which further proves its effectiveness and security.

Key words: Clustering, Information security, K-anonymity, Privacy protection, Social network

中图分类号:

TP391

周艺华, 张冰, 杨宇光, 侍伟敏. 基于聚类的社交网络隐私保护方法[J]. 计算机科学, 2019, 46(10): 154-160. https://doi.org/10.11896/jsjkx.180901749

ZHOU Yi-hua, ZHANG Bing, YANG Yu-guang, SHI Wei-min. Cluster-based Social Network Privacy Protection Method[J]. Computer Science, 2019, 46(10): 154-160. https://doi.org/10.11896/jsjkx.180901749

参考文献

[1]LIU X Y,WANG B,YANG X C.Survey on Privacy Preserving Techniques for Publishing Social Network Data[J].Journal of Software,2014,25(3):576-590.
[2]LIU K,TERZI E.Towards identity anonymization on graphs [C]//ACM SIGMOD International Conference on Management of Data.ACM,2008:93-106.
[3]LIU K,DAS K,GRANDISON T,et al.Privacy-Preserving Data Analysis on Graphs and Social Networks[OL].https://www.researchgate.net/publication/290110049_Privacy-Preserving_Data_Analysis_on_Graphs_and_Social_Networks.
[4]CEN T T,HAN J M,WANG J Y,et al.Survey of K-anonymity research on privacy preservation[J].Computer Engineering & Applications,2008,44(4):130-134.(in Chinese)
岑婷婷,韩建民,王基一,等.隐私保护中K-匿名模型的综述[J].计算机工程与应用,2008,44(4):130-134.
[5]WANG Z B,SHEN M Y,ZHAO J.Privay protection technology discussion of social network based on node reconstruction.Computer Engineering and Applications,2017,53(11):131-136.(in Chinese)
王正彬,沈明玉,赵皎.基于节点重构的社交网络的隐私保护技术探讨.计算机工程与应用,2017,53(11):131-136.
[6]XIE Y,ZHENG M.A Differentiated Anonymity Algorithm for Social Network Privacy Preservation[J].Algorithms,2016,9(4):85.
[7]ZHELEVA E,GETOOR L.Preserving the Privacy of Sensitive Relationships in Graph Data[C]//ACM SIGKDD International Conference on Privacy,Security,and Trust in Kdd.Springer-Verlag,2008:153-171.
[8]ZOU L,CHEN L,ÖZSU M T.k-automorphism:a general framework for privacy preserving network publication[M].VLDB Endowment,2009.
[9]GU Y H,LIN J C,GUO D.Clusterin-based bynamic privacy preserving method for social networks.Journal on Communications,2015,36(S1),126-130.(in Chinese)
谷勇浩,林九川,郭达.基于聚类的动态社交网络隐私保护方法.通信学报,2015,36(S1):126-130.
[10]CAMPAN A,TRUTA T M.Data and Structural k-Anonymity in Social Networks[M]//Privacy,Security,and Trust in KDD.Springer Berlin Heidelberg,2008:33-54.
[11]SKARKALA M E,MARAGOUDAKIS M,GRITZALIS S,et al.Privacy Preservation by k-Anonymization of Weighted Social Networks[C]//IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.IEEE,2012:423-428.
[12]LAN L H ,JU S G,JIN H.Social Networks Data Publication Based on k-anonymity[J].Computer Science,2011,38(11):156-160.(in Chinese)
兰丽辉,鞠时光,金华.社会网络数据的k-匿名发布[J].计算机科学,2011,38(11):156-160.
[13]JIANG H W,ZHAN Q H,LIU W J,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.
[14]RONG H,MA T H,TANG M L,et al.A novel subgraph K⁺-isomorphism method in social network based on graph similarity detection [J].Soft Computing,2018,22(8):2583-2601.
[15]SAMANTHULA B K,LEI C,WEI J,et al.Privacy-Preserving and Efficient Friend Recommendation in Online Social Networks[J].Transactions on Data Privacy,2015,8(2):141-171.
[16]LIU P,BAI Y,WANG L,et al.Partial k-Anonymity for Privacy-Preserving Social Network Data Publishing[J].International Journal of Software Engineering & Knowledge Engineering,2016,27(1):71-90.
[17]YU F H,CHEN M J,YU B L,et al.Privacy preservation based on clustering perturbation algorithm for social network[J].Multimedia Tools & Applications,2018,77(9):1-18.
[18]QIAN J W,LI X Y,ZHANG C H,et al.Social Network De-Anonymization and Privacy Inference with Knowledge GraphMo-del[J].IEEE Transactions on Dependable and Secure Computing,2017,PP(99):1-1.

相关文章 15

[1]	鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于分层抽样优化的面向异构客户端的联邦学习 Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients 计算机科学, 2022, 49(9): 183-193. https://doi.org/10.11896/jsjkx.220500263
[2]	汤凌韬, 王迪, 张鲁飞, 刘盛云. 基于安全多方计算和差分隐私的联邦学习方案 Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy 计算机科学, 2022, 49(9): 297-305. https://doi.org/10.11896/jsjkx.210800108
[3]	吕由, 吴文渊. 隐私保护线性回归方案与应用 Privacy-preserving Linear Regression Scheme and Its Application 计算机科学, 2022, 49(9): 318-325. https://doi.org/10.11896/jsjkx.220300190
[4]	柴慧敏, 张勇, 方敏. 基于特征相似度聚类的空中目标分群方法 Aerial Target Grouping Method Based on Feature Similarity Clustering 计算机科学, 2022, 49(9): 70-75. https://doi.org/10.11896/jsjkx.210800203
[5]	王剑, 彭雨琦, 赵宇斐, 杨健. 基于深度学习的社交网络舆情信息抽取方法综述 Survey of Social Network Public Opinion Information Extraction Based on Deep Learning 计算机科学, 2022, 49(8): 279-293. https://doi.org/10.11896/jsjkx.220300099
[6]	刘丽, 李仁发. 医疗CPS协作网络控制策略优化 Control Strategy Optimization of Medical CPS Cooperative Network 计算机科学, 2022, 49(6A): 39-43. https://doi.org/10.11896/jsjkx.210300230
[7]	王健. 基于隐私保护的反向传播神经网络学习算法 Back-propagation Neural Network Learning Algorithm Based on Privacy Preserving 计算机科学, 2022, 49(6A): 575-580. https://doi.org/10.11896/jsjkx.211100155
[8]	鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于DBSCAN聚类的集群联邦学习方法 Clustered Federated Learning Methods Based on DBSCAN Clustering 计算机科学, 2022, 49(6A): 232-237. https://doi.org/10.11896/jsjkx.211100059
[9]	郁舒昊, 周辉, 叶春杨, 王太正. SDFA:基于多特征融合的船舶轨迹聚类方法研究 SDFA:Study on Ship Trajectory Clustering Method Based on Multi-feature Fusion 计算机科学, 2022, 49(6A): 256-260. https://doi.org/10.11896/jsjkx.211100253
[10]	毛森林, 夏镇, 耿新宇, 陈剑辉, 蒋宏霞. 基于密度敏感距离和模糊划分的改进FCM算法 FCM Algorithm Based on Density Sensitive Distance and Fuzzy Partition 计算机科学, 2022, 49(6A): 285-290. https://doi.org/10.11896/jsjkx.210700042
[11]	陈景年. 一种适于多分类问题的支持向量机加速方法 Acceleration of SVM for Multi-class Classification 计算机科学, 2022, 49(6A): 297-300. https://doi.org/10.11896/jsjkx.210400149
[12]	陈佳舟, 赵熠波, 徐阳辉, 马骥, 金灵枫, 秦绪佳. 三维城市场景中的小物体检测 Small Object Detection in 3D Urban Scenes 计算机科学, 2022, 49(6): 238-244. https://doi.org/10.11896/jsjkx.210400174
[13]	魏鹏, 马玉亮, 袁野, 吴安彪. 用户行为驱动的时序影响力最大化问题研究 Study on Temporal Influence Maximization Driven by User Behavior 计算机科学, 2022, 49(6): 119-126. https://doi.org/10.11896/jsjkx.210700145
[14]	李利, 何欣, 韩志杰. 群智感知的隐私保护研究综述 Review of Privacy-preserving Mechanisms in Crowdsensing 计算机科学, 2022, 49(5): 303-310. https://doi.org/10.11896/jsjkx.210400077
[15]	邢云冰, 龙广玉, 胡春雨, 忽丽莎. 基于SVM的类别增量人体活动识别方法 Human Activity Recognition Method Based on Class Increment SVM 计算机科学, 2022, 49(5): 78-83. https://doi.org/10.11896/jsjkx.210400024

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed