Abstract
Social networks have a great influence in business, for which the data of social networks are usually released for research purpose. Since the published data might contain sensitive information of users, the identities of which are removed for anonymity before release. However, adversaries could still utilize some background knowledge to re-identify users. In this paper, we propose a novel attack model named edge-neighborhood graph attack (ENGA) against anonymized social networks, in which adversaries are assumed to have background knowledge about targets and their two-hop neighbors represented by 1-neighborhood graph and \(1^{*}\)-neighborhood graphs respectively. Based on such model, a de-anonymous approach is proposed to re-identify users in anonymous social networks. Theoretical analysis indicate that ENGA has a higher de-anomymization rate. And experiments conducted on synthetic data sets and real data sets illustrate the effectiveness of ENGA.
This work is supported by the National Natural Science Foundation of China (Grant No. 61771140, No. U1405255, No. U1905211, No. 61702100, No. 171061).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Campan, A., Truta, T.: A clustering approach for data and structural anonymity in social networks. In: Proceedings the 2nd ACM SIGKDD Int. Workshop Privacy Security Trust in KDD. pp. 33–54 (2008)
Chen, D., L, L., Shang, M., Cheng, Y.: Identifying influential nodes in complex networks. Physica A Statistical Mechanics and Its Applications 39(4) (2012)
Chiasserini, C.F., Garetto, M., Leonardi, E.: Social network de-anonymization under scale-free user relations. IEEE/ACM transactions on networking 24(6), 3756–3769 (2016)
Day, W., Li, N., Min, L.: Publishing graph degree distribution with node differential privacy. In: the 2016 International Conference. pp. 123–138. USA (2016)
Gross, R., Acquisti, A., Iii, H.J.H.: Information revelation and privacy in online social networks. In: Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society. pp. 71–80. ACM, USA (2005)
Jung, T., Li., X.Y., Huang, W.C., Qian, J.W., Cheng, S.: Accounttrade: Accountable protocols for big data trading against dishonest consumers. In: IEEE INFOCOM (2017)
Kiabod, M., Dehkordi, M.N., Barekatain, B.: Tsram: A time-saving k-degree anonymization method in social network. Expert Systems with Application 125, 378–396 (2019)
Langari, R.K., Sardar, S., Mousavi, S.A., Radfar, R.: Combined fuzzy clustering and fifireflfly algorithm for privacy preserving in social networks. Expert Systems with Application 141, 1–15 (2020)
Leskovec, J.: Stanford large network dataset collection. http://snap.stanford.edu/data/
Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: in Proc. ACM SIGMOD Int. Conf. Manage. Data. pp. 93–106 (2008)
Liu, Q., Wang, G., Li, F., Yang, S., Wu, J.: Preserving privacy with probabilistic indistinguishability in weighted social networks. IEEE Transactions on Parallel and Distributed Systems 28(5), 1417–1429 (2017)
Narayanan, A., Shmatikov, V.: De-anonymizing social networks. In: Proceedings of the 30th IEEE Symposium on Security and Privacy. pp. 173–187 (2009)
Qian, J., Li, X., Zhang, C., Chen, L., Jung, T., Han, J.: Social network de-anonymization and privact inference with knowledge graph model. IEEE Transactions on dependable and secure computing 99, 1–14 (2017)
Shah, C., Capra, R., Hansen, P.: Collaborative information seeking: Guest editors’ introduction. IEEE transactions on computer 47(3), 22–25 (2014)
Sharad, K., Danezis, G.: An automated social graph de-anonymization technique. Computer Science pp. 47–58 (2014)
Ying, X., Wu, X.: Randomizing social networks:a spectrum preserving approach. In: In Proceedings of the 2008 SIAM International Conference on Data Mining. p. 739-750. No. 12, SIAM (2008)
Yuan, M., Chen, L., Yu, P.S., Yu, T.: Protecting sensitive lables in social network data anonymization. IEEE Transactions on Knowledge and data engineering 25(3), 633–647 (2013)
Zheng, X., Luo, G., Cai, Z.: A fair mechanism for private data publication in online social networks. IEEE Transactions on Network Science and Engineering pp. 1–11 (2018)
Zhou, B., Pei, J.: Privacy preservation in social networks against neighborhood attacks. In: ICDE. pp. 506–515. IEEE, USA (2008)
Zou, L., Chen, L., Ozsu, M.: K-automorphism: A general framework for privacy preserving network publication. In: in Proceedings of the VLDB Endowment. vol. 2, pp. 946–957 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Zhang, H., Xu, L., Lin, L., Wang, X. (2020). De-anonymizing Social Networks with Edge-Neighborhood Graph Attacks. In: Yu, S., Mueller, P., Qian, J. (eds) Security and Privacy in Digital Economy. SPDE 2020. Communications in Computer and Information Science, vol 1268. Springer, Singapore. https://doi.org/10.1007/978-981-15-9129-7_49
Download citation
DOI: https://doi.org/10.1007/978-981-15-9129-7_49
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-9128-0
Online ISBN: 978-981-15-9129-7
eBook Packages: Computer ScienceComputer Science (R0)