社交网络高效高精度去匿名化算法

来源：软件学报杂志2018年第3期北京时间：

作者：刘家霖,史舒扬,张悦眉,邵蓥侠,崔斌

单位：刘家霖，高可信软件技术教育部重点实验室(北京大学), 北京 10087111,史舒扬，高可信软件技术教育部重点实验室(北京大学), 北京 10087102,张悦眉，高可信软件技术教育部重点实验室(北京大学), 北京 10087103,邵蓥侠，高可信软件技术教育部重点实验室(北京大学), 北京 10087104,崔斌，高可信软件技术教育部重点实验室(北京大学), 北京 10087105

摘要：自从社交网络成为重要的研究课题，社交网络隐私保护也成为了重要的研究内容，尤其是关于公开发布以供研究的大规模社交网络图数据的隐私保护.为了评估用户的隐私风险，研究者们设计了不同的方法对图进行去匿名化，在不同的图网络中识别个体的身份.但是，当前的去匿名化算法或者需要高质量的种子匹配，或者在精确度和效率上颇有不足.提出一种高效高精度的无种子去匿名化算法RoleMatch，基于社交网络的拓扑结构识别个体身份.该算法包括：（1）可以快速计算的两图结点间相似度度量方法RoleSim++；（2）一种有效的结点匹配算法，此法同时考虑了结点间的相似度和中间匹配结果的反馈.在实验部分，利用LiveJournal的数据，用RoleMatch对比了多种流行的匿名化算法，并根据实际应用情景，在传统实验的基础上增加了局部去匿名化的实验，实验结果验证了所提出的去匿名化算法的优秀性能.

关键词：社交网络;去匿名化;匿名化;隐私保护;结点相似度

基金资助：国家自然科学基金（61572039）；中国博士后科学基金（2017M610020）；中国青年自然科学基金（61702015）；深圳市政府研究项目（JCYJ20151014093505032）