大规模社会网络K-出入度匿名方法

doi:10.19678/j.issn.1000-3428.0056038

计算机工程 ›› 2020, Vol. 46 ›› Issue (11): 164-173. doi: 10.19678/j.issn.1000-3428.0056038

大规模社会网络K-出入度匿名方法

张晓琳¹, 刘娇¹, 毕红净², 李健¹, 王永平¹

1. 内蒙古科技大学信息工程学院, 内蒙古包头 014010;
2. 唐山师范学院计算机科学系, 河北唐山 063000

收稿日期:2019-09-18 修回日期:2019-11-06 发布日期:2019-11-15
作者简介:张晓琳(1966-),女,教授,主研方向为大规模社会网络隐私保护;刘娇,硕士研究生;毕红净,讲师、硕士;李健,硕士研究生;王永平,讲师。
基金资助:
国家自然科学基金"面向云计算环境的大规模社会网络隐私保护技术研究"（61562065）；内蒙古自治区自然科学基金"有效保护社区结构的大规模社会网络隐私保护技术研究"（2019MS06001）。

K-In&Out-Degree Anonymity Method for Large Scale Social Networks

ZHANG Xiaolin¹, LIU Jiao¹, BI Hongjing², LI Jian¹, WANG Yongping¹

1. School of Information Engineering, Inner Mongolia University of Science and Technology, Baotou, Inner Mongolia 014010, China;
2. Department of Computer Science, Tangshan Normal University, Tangshan, Hebei 063000, China

Received:2019-09-18 Revised:2019-11-06 Published:2019-11-15

摘要/Abstract

摘要： 现有社会网络隐私保护技术在处理大规模社会网络有向图时数据处理效率较低，且匿名数据发布通常不能满足社区结构分析的需求。为此，提出一种基于层次社区结构的大规模社会网络K-出入度匿名（KIODA）算法。该算法基于层次社区结构划分社区，采用贪心算法分组并匿名K-出入度序列，分布式并行添加虚拟节点以实现K-出入度匿名，基于GraphX图数据处理平台传递节点间的信息，根据层次社区熵的变化情况选择虚拟节点对并进行合并删除，从而减少信息损失。实验结果表明，KIODA算法在处理大规模社会网络有向图数据时具有较高的执行效率，并在匿名后保证了数据发布时社区结构分析结果的可用性。

关键词: 层次社区结构, 社会网络有向图, K-出入度匿名, 社区划分, GraphX框架

Abstract: Existing privacy protection techniques are inefficient when applied to directed graphs of large-scale social networks,and publishing anonymous data does not meet the needs of community structure analysis.To address the problem,this paper proposes a K-In&Out-Degree Anonymity(KIODA) algorithm for large-scale social networks based on hierarchical community structure.The algorithm divides the community based on hierarchical community structure.The greedy algorithm is used to group K-in&out-degree sequences and make them anonymous,and the virtual nodes are added in parallel to achieve K-in&out-degree anonymity.Then information exchanges between nodes are implemented based on the GraphX platform.Virtual node pairs are selected based on the changes of the hierarchical community entropy,and are merged and deleted to reduce information loss.Experimental results show that the KIODA algorithm improves the efficiency of processing directed graphs of large-scale social networks,and ensures the availability of community structure analysis results in data publishing after the anonymity is realized.

Key words: hierarchical community structure, directed graph of social networks, K-In&Out-Degree Anonymity(KIODA), community division, GraphX framework

中图分类号:

TP391

张晓琳, 刘娇, 毕红净, 李健, 王永平. 大规模社会网络K-出入度匿名方法[J]. 计算机工程, 2020, 46(11): 164-173.

ZHANG Xiaolin, LIU Jiao, BI Hongjing, LI Jian, WANG Yongping. K-In&Out-Degree Anonymity Method for Large Scale Social Networks[J]. Computer Engineering, 2020, 46(11): 164-173.

http://www.ecice06.com/CN/Y2020/V46/I11/164

图/表 20

20201124085735

20201124085738

20201124085741

20201124085744

20201124085747

20201124085750

20201124085752

20201124085756

20201124085759

20201124085801

20201124085805

20201124085809

20201124085812

20201124085815

20201124085818

20201124085822

20201124085825

20201124085829

20201124085832

20201124085836

参考文献

[1] BACKSTROM L,DWORK C,KLEINBERG J,et al.Wherefore art thou R3579X? anonymized social networks,hidden patterns,and structural steganography[J].Com-munications of the ACM,2011,54(12):133-141.
[2] SALAS J,TORRA V.Graphic sequences,distances and k-degree anonymity[J].Discrete Applied Mathematics,2015,188:25-31.
[3] BHATTACHARYA M,MANI P.Preserving privacy in social network graph with K-anonymize degree sequence generation[C]//Proceedings of 2015 International Conference on Software,Knowledge,Information Management and Applications.Washington D.C.,USA:IEEE Press,2015:1-7.
[4] MACWAN K R,PATEL S J.K-NMF anonymization in social network data publishing[J].The Computer Journal,2018,61(4):601-613.
[5] YANG Dianhui.Large scale social network privacy protection based on heuristic analysis[D].Xi'an:University of Electronic Science and Technology of China,2013.(in Chinese)杨典辉.基于启发式分析的大规模社会网络隐私保护[D].西安:电子科技大学,2013.
[6] ZHANG Xiaolin,ZHANG Wenchao,ZHANG Chen,et al.D-GSPerturb:a distributed social privacy protection algorithm based on graph structure perturbation[J].Journal of Computers,2017,28(5):51-61.
[7] SUN Yongjiao,YUAN Ye,WANG Guoren,et al.Splitting anonymization:a novel privacy-preserving approach of social network[J].Knowledge and Information Systems,2016,47(3):595-623.
[8] KASIVISWANATHAN S P,NISSIM K,RASKHODNIKOVA S,et al.Analyzing graphs with node differential privacy[M].Berlin,Germany:Springer,2013:457-476.
[9] 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.
[10] LIU K,TERZI E.Towards identity anonymization on graphs[C]//Proceedings of 2008 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2008:93-106.
[11] CASAS-ROMA J,HERRERA-JOANCOMARTÍ J,TORRA V.k-degree anonymity and edge selection:improving data utility in large networks[J].Knowledge and Information Systems,2017,50(2):447-474.
[12] MACWAN K R,PATEL S J.K-degree anonymity model for social network data publishing[J].Advances in Electrical and Computer Engineering,2017,17(4):117-124.
[13] YU D R,ZHAO H X,WANG L E,et al.A hierarchical k-anonymous technique of graphlet structural perception in social network publishing[M].Berlin,Germany:Springer,2019:224-239.
[14] GONG Weihua,LAN Xuefeng,PEI Xiaobing,et al.Privacy preservation method based on k-degree anonymity in social networks[J].Acta Electronica Sinica,2016,44(6):1437-1444.(in Chinese)龚卫华,兰雪锋,裴小兵,等.基于k-度匿名的社会网络隐私保护方法[J].电子学报,2016,44(6):1437-1444.
[15] LIU Xiangyu,LI Jiajia,AN Yunzhe,et al.Efficient algorithm on anonymizing social networks with reachability preservation[J].Journal of Software,2016,27(8):1904-1921.(in Chinese)刘向宇,李佳佳,安云哲,等.一种保持结点可达性的高效社会网络图匿名算法[J].软件学报,2016,27(8):1904-1921.
[16] ZHANG Xiaolin,HE Xiaoyu,ZHANG Huanxiang,et al.PLRD-(k,m):distributed k-degree-m-label anonymity with protecting link rela-tionships[J].Journal of Frontiers of Computer Science and Technology,2019,13(1):70-82.(in Chinese)张晓琳,何晓玉,张换香,等.PLRD-(k,m):保护链接关系的分布式k-度-m-标签匿名方法[J].计算机科学与探索,2019,13(1):70-82.
[17] YING Xiaowei,WU Xintao.On link privacy in randomizing social networks[J].Knowledge and Information Systems,2011,28(3):645-663.
[18] CAMPAN A,ALUFAISAN Y,TRUTA T M.Preserving communities in anonymized social networks[J].Transactions on Data Privacy,2015,8(1):55-87.
[19] WANG Huanjie,LIU Peng,LIN Shan,et al.A local-perturbation anonymizing approach to preserving community structure in released social networks[M].Berlin,Germany:Springer,2017:36-45.
[20] KUMAR S,KUMAR P.Upper approximation based privacy preserving in online social networks[J].Expert Systems with Applications,2017,88:276-289.
[21] ROUSSEAU F,CASAS-ROMA J,VAZIRGIANNIS M.Community-preserving anonymization of graphs[J].Knowledge and Information Systems,2018,54(2):315-343.
[22] CLAUSET A,MOORE C,NEWMAN M E J.Hierarchical structure and the prediction of missing links in networks[J].Nature,2008,453(7191):98-101.
[23] CHESTER S,KAPRON B M,RAMESH G,et al.Why Waldo befriended the dummy? k-anonymization of social networks with pseudo-nodes[J].Social Network Analysis and Mining,2013,3(3):381-399.
[24] CAI Bingjing,WANG Haiying,ZHENG Huiru,et al.Evaluation repeated random walks in community detection of social networks[C]//Proceedings of 2010 International Conference on Machine Learning and Cybernetics.Washington D.C.,USA:IEEE Press,2010:1849-1854.

选择文件类型/文献管理软件名称

选择包含的内容

大规模社会网络K-出入度匿名方法

K-In&Out-Degree Anonymity Method for Large Scale Social Networks

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 20

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	谢菁, 羿舒文, 张毅. 基于双曲空间嵌入的极小值社区划分算法[J]. 计算机工程, 2020, 46(6): 73-80.
[2]	蔡波斯, 陈翔. 基于行为相似度的微博社区发现研究[J]. 计算机工程, 2013, 39(8): 55-59.
[3]	廖涛, 刘宗田, 王利. 多主题文本摘要抽取的研究与实现[J]. 计算机工程, 2011, 37(6): 21-23.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

大规模社会网络K-出入度匿名方法

K-In&Out-Degree Anonymity Method for Large Scale Social Networks

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 20

参考文献

相关文章 3

编辑推荐

Metrics

本文评价