Journal of Software:2018.29(3):772-785

(高可信软件技术教育部重点实验室(北京大学), 北京 100871)
Effective and Efficient Approach for Graph De-Anonymization
LIU Jia-Lin,SHI Shu-Yang,ZHANG Yue-Mei,SHAO Ying-Xia,CUI Bin
(Key Laboratory of High Confidence Software Technologies, Ministry of Education(Peking University), Beijing 100871, China)
Chart / table
Similar Articles
Article :Browse 1494   Download 1489
Received:July 22, 2017    Revised:September 05, 2017
> 中文摘要: 自从社交网络成为重要的研究课题,社交网络隐私保护也成为了重要的研究内容,尤其是关于公开发布以供研究的大规模社交网络图数据的隐私保护.为了评估用户的隐私风险,研究者们设计了不同的方法对图进行去匿名化,在不同的图网络中识别个体的身份.但是,当前的去匿名化算法或者需要高质量的种子匹配,或者在精确度和效率上颇有不足.提出一种高效高精度的无种子去匿名化算法RoleMatch,基于社交网络的拓扑结构识别个体身份.该算法包括:(1)可以快速计算的两图结点间相似度度量方法RoleSim++;(2)一种有效的结点匹配算法,此法同时考虑了结点间的相似度和中间匹配结果的反馈.在实验部分,利用LiveJournal的数据,用RoleMatch对比了多种流行的匿名化算法,并根据实际应用情景,在传统实验的基础上增加了局部去匿名化的实验,实验结果验证了所提出的去匿名化算法的优秀性能.
Abstract:Ever since social networks became the focus of a great number of researches, the privacy risks of published network data have also raised considerable concerns. To evaluate users' privacy risks, researchers have developed methods to de-anonymize graphs and identify same person in different graphs, yet the existing algorithms either requires high-quality seed mappings, or have low accuracy and high expense. In this paper, an effective and efficient seedless de-anonymization algorithm, "RoleMatch" is proposed. This algorithm is based on the network topology and consists of (1) a new cross-graph node similarity measurement "RoleSim++" with fast computation method, and (2) an effective node matching algorithm considering both similarities and feedbacks. In experiments, the algorithm is tested with graphs anonymized in several popular anonymization ways, using the data from LiveJournal. In addition to the traditional symmetric experiments, an asymmetric experiment setting is proposed to mimic closer to real-world application. The results from those experiment show that with the proposed algorithm the de-anonymization work achieves superior performance compared with existing de-anonymization algorithms.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61572039);中国博士后科学基金(2017M610020);中国青年自然科学基金(61702015);深圳市政府研究项目(JCYJ20151014093505032) 国家自然科学基金(61572039);中国博士后科学基金(2017M610020);中国青年自然科学基金(61702015);深圳市政府研究项目(JCYJ20151014093505032)
Foundation items:National Natural Science Foundation of China (61572039);China Postdoctoral Science Foundation (2017M 610020);National Natural Science Foundation of China for Young Scholar (61702015);Shenzhen Goverment Research Project (JCYJ 20151014093505032)
Reference text:


LIU Jia-Lin,SHI Shu-Yang,ZHANG Yue-Mei,SHAO Ying-Xia,CUI Bin.Effective and Efficient Approach for Graph De-Anonymization.Journal of Software,2018,29(3):772-785