De-anonymizing Social Networks with Edge-Neighborhood Graph Attacks
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 b
- PDF / 482,652 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 110 Downloads / 220 Views
2
Fujian Provincial Key Laboratory of Network Security and Cryptology, Fujian Normal University, Fujian, China [email protected] School of Mathematics and Informatics, Fujian Normal University, Fujian, China 3 Concord University College Fujian Normal University, Fujian, China
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 edgeneighborhood 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. Keywords: Social networks · Edge-Neighborhood Graph (ENG) Re-identify · Graph matching.
1
·
Introduction
With the development of communication technologies, i.e., Twitter, Facebook, WeChat etc., social networks have become an indispensable part of people’s lives. Every day, a great amount of data generated by social networks can be released for various purpose, including targeted advertising, academic research and public competition [5,6,14]. Because social network data might contain significantly sensitive and private information of users, e.g. identity, income, phone number, etc., data should be “processed” before release for privacy protection. Studies on social networks are usually graph based, where nodes represent the users of social networks and edges represent the relationships between them. Although many privacy protection strategies have been proposed, they This work is supported by the National Natural Science Foundation of China (Grant No. 61771140, No. U1405255, No. U1905211, No. 61702100, No. 171061). c Springer Nature Singapore Pte Ltd. 2020 S. Yu et al. (Eds.): SPDE 2020, CCIS 1268, pp. 726–737, 2020. https://doi.org/10.1007/978-981-15-9129-7_49
De-anonymizing Social Networks with Edge-Neighborhood Graph Attacks
727
are designed against certain attacks. A na¨ıve anonymization for social networks is to remove the users’ idetntities, however it can hardly resist the node reidentification, where adversaries have some knowledge about the targets. Liu et al. [10] propose a vertex degree attack with node degrees known by adversaries. Zhou et al. [19] propose a neighborhood attack, in which adversaries have some knowledge about victims and their neighbors which is presented by 1−neighorhood graph (NG). Ying et al. [16] propose an attack based on edge probability and vertices simi
Data Loading...
