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

Effective and Efficient Approach for Graph De-Anonymization

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

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.