社交网络高效高精度去匿名化算法
作者:
作者单位:

作者简介:

刘家霖(1995-),男,福建晋江人,主要研究领域为数据库;邵蓥侠(1988-),男,博士,主要研究领域为数据库,知识图谱数据管理,并行图计算,知识工程;史舒扬(1994-),男,学士,主要研究领域为数据库;崔斌(1975-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为数据库,大数据管理分析;张悦眉(1995-),女,主要研究领域为数据库.

通讯作者:

邵蓥侠,E-mail:shao.yingxia@pku.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(61572039);中国博士后科学基金(2017M610020);中国青年自然科学基金(61702015);深圳市政府研究项目(JCYJ20151014093505032)


Effective and Efficient Approach for Graph De-Anonymization
Author:
Affiliation:

Fund Project:

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)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    自从社交网络成为重要的研究课题,社交网络隐私保护也成为了重要的研究内容,尤其是关于公开发布以供研究的大规模社交网络图数据的隐私保护.为了评估用户的隐私风险,研究者们设计了不同的方法对图进行去匿名化,在不同的图网络中识别个体的身份.但是,当前的去匿名化算法或者需要高质量的种子匹配,或者在精确度和效率上颇有不足.提出一种高效高精度的无种子去匿名化算法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.

    参考文献
    相似文献
    引证文献
引用本文

刘家霖,史舒扬,张悦眉,邵蓥侠,崔斌.社交网络高效高精度去匿名化算法.软件学报,2018,29(3):772-785

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-07-22
  • 最后修改日期:2017-09-05
  • 录用日期:
  • 在线发布日期: 2017-12-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号