微信服务号

微信订阅号

2025-4-24- 19
Home > Archive>Volume 29, Issue 3, 2018 >772-785. DOI:10.13328/j.cnki.jos.005436
PDF HTML XML Export Cite reminder
Effective and Efficient Approach for Graph De-Anonymization
Author:
Affiliation:

Clc Number:

TP311

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)

  • Article
    • | |
  • Metrics
    • |
  • Reference [19]
    • |
  • Related
    • | | |
  • Comments
    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.

    Reference
    [1] Backstrom L, Dwork C, Kleinberg J. Wherefore art thou r3579x?:Anonymized social networks, hidden patterns, and structural steganography. In:Proc. of the 16th Int'l Conf. on World Wide Web. ACM Press, 2007. 181-190.[doi:10.1145/1242572.1242598]
    [2] Wang Y, Zheng B. Preserving privacy in social networks against connection fingerprint attacks. In:Proc. of the 2015 IEEE 31st Int'l Conf. on Data Engineering. IEEE. 2015. 54-65.[doi:10.1109/ICDE.2015.7113272]
    [3] Wu X, Ying X, Liu K, Chen L. A survey of privacy-preservation of graphs and social networks. In:Proc. of the Managing and Mining Graph Data. Springer-Verlag, 2010. 421-453.[doi:10.1007/978-1-4419-6045-0_14]
    [4] Liu K, Terzi E. Towards identity anonymization on graphs. In:Proc. of the 2008 ACM SIGMOD Int'l Conf. on Management of Data. ACM Press, 2008. 93-106.[doi:10.1145/1376616.1376629]
    [5] Zhou B, Pei J. Preserving privacy in social networks against neighborhood attacks. In:Proc. of the 2008 IEEE 24th Int'l Conf. on Data Engineering. IEEE, 2008. 506-515.[doi:10.1109/ICDE.2008.4497459]
    [6] Bonchi F, Gionis A, Tassa T. Identity obfuscation in graphs through the information theoretic lens. In:Proc. of the Information Sciences. Elsevier, 2014. 232-256.[doi:10.1016/j.ins.2014.02.035]
    [7] Zheleva E, Getoor L. Preserving the privacy of sensitive relationships in graph data. In:Proc. of the Privacy, Security, and Trust in KDD. Berlin, Heidelberg:Springer-Verlag, 2008. 153-171.[doi:10.1007/978-3-540-78478-4_9]
    [8] Narayanan A, Shmatikov V. De-Anonymizing social networks. In:Proc. of the 200930th IEEE Symp. on Security and Privacy. IEEE, 2009. 173-187.[doi:10.1109/SP.2009.22]
    [9] Narayanan A, Shi E, Rubinstein BI. Link prediction by de-anonymization:How we won the kaggle social network challenge. In:Proc. of the 2011 Int'l Joint Conf. on Neural Networks (IJCNN). IEEE, 2011. 1825-1834.[doi:10.1109/IJCNN.2011.6033446]
    [10] Yartseva L, Grossglauser M. On the performance of percolation graph matching. In:Proc. of the 1st ACM Conf. on Online Social Networks. ACM Press, 2013. 119-130.[doi:10.1145/2512938.2512952]
    [11] Kazemi E, Hassani SH, Grossglauser M. Growing a graph matching from a handful of seeds. Proc. of the VLDB Endowment, 2015, 8(10):1010-1021.[doi:10.14778/2794367.2794371]
    [12] Korula N, Lattanzi S. An efficient reconciliation algorithm for social networks. Proc. of the VLDB Endowment, 2014,7(5):377-388.[doi:10.14778/2732269.2732274]
    [13] Fu H, Zhang A, Xie X. Effective social graph deanonymization based on graph structure and descriptive information. ACM Trans. on Intelligent Systems and Technology (TIST), 2015,6(4):49.[doi:10.1145/2700836]
    [14] Henderson K, Gallagher B, Li L, Akoglu L, Eliassi-Rad T, Tong H, Faloutsos C. It's who you know:Graph mining using recursive structural features. In:Proc. of the 17th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2011. 663-671.[doi:10.1145/2020408.2020512]
    [15] Jeh G, Widom J. SimRank:A measure of structural-context similarity. In:Proc. of the 8th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2002. 538-543.[doi:10.1145/775047.775126]
    [16] Blondel VD, Gajardo A, Heymans M, Senellart P, Van Dooren P. A measure of similarity between graph vertices:Applications to synonym extraction and Web searching. Siam Review, 2004,46(4):647-666.[doi:10.1137/S0036144502415960]
    [17] Jin R, Lee VE, Hong H. Axiomatic ranking of network role similarity. In:Proc. of the 17th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2011. 922-930.[doi:10.1145/2020408.2020561]
    [18] Perozzi B, Al-Rfou R, Skiena S. Deepwalk:Online learning of social representations. In:Proc. of the 20th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2014. 701-710.[doi:10.1145/2623330.2623732]
    [19] Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q. Line:Large-Scale information network embedding. In:Proc. of the 24th Int'l Conf. on World Wide Web. ACM Press, 2015. 1067-1077.[doi:10.1145/2736277.2741093]
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:4289
  • PDF: 7433
  • HTML: 3347
  • Cited by: 0
History
  • Received:July 22,2017
  • Revised:September 05,2017
  • Online: December 05,2017
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038253Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063