On Key Techniques Of Protecting Privacy In Social Networks

In recent years, along with the development of the Internet technology and the explosive growth of social network services, e.g. Facebook and Twitter, the amount of online users in social networks has increased rapidly. Researchers from different disciplines pay more and more concerns on the social networks for mining the potential values on research and business. Social network analysis has become hot topics in the research areas of Sociology, Economics and Informatics. Compared with relational data, it could achieve more accurate and meaningful results when data mining and analysis in social network data. However, social networks usually contain individuals’ sensitive information, which makes it an important concern that how to avoid compromising individual privacy when releasing social network data. In social networks, the categories of privacy information and ways of privacy leakages become more diverse, so that it is a great challenge of protecting privacy in social networks. With respect to the categories of privacy information and ways of privacy leakages, we need to investigate corresponding privacy protecting technologies for social networks.Specifically, this dissertation conducts in-depth studies into several social network privacy protecting technologies, which preserve the data utilities of anonymized graphs and provide privacy protection for vertex identities, sensitve relationships and labels. The contributions of this dissertation are summarized as follows.(1) For vertex privacy protection, we study the problem that the adversary could launch a vertex identification attack using the weights of the edges in weighted graphs, which results in the leakage of vertex privacy. We propose a privacy protecting model for the vertices in weighted graphs and develop a generalization based anonymization approach (named GA) to achieve the privacy guaranteed by the model. Experimental results show that the privacy model and algorithm performs well in terms of protection it provides, and properties of the original weighed network can be recovered with relatively little bias through aggregation on a small number of sampled graphs.(2) For sensitive relationship protection, it is easy for adversaries to reveal sensitive relationships by performing link inferences, and we study how to protect sensitive relationship privacy against link inference attacks. We identify two types of link inference attacks, namely, one-step link inference attacks and cascaded link inference attacks. We develop a general framework for preventing link inference attacks, which adopts a novel lineage tracing mechanism to efficiently cut off the inference paths of sensitive relationships. We also propose algorithms for preventing one-step link inference attacks and cascaded link inference attacks meanwhile retaining the data utility. Experimental results show the satisfactory performance of our methods in terms of privacy protection, efficiency and practical utilities.(3) For sensitive labels protection, considering each vertex in complex social networks has a corresponding profile, we study how to protect profile privacy. We propose k-obfuscation to protect profiles against graph property based attacks (GPA). And we develop a novel safe vertex-profile mapping mechanism for obtaining k-obfuscation, named as k-mapping. We also design a number of techniques to make the k-mapping method efficient meanwhile maintaining the data utilities. Extensive experiments on real datasets show that the k-mapping method performs well in protecting the profile privacy, which results in low information loss on profiles and closeness, so that the anonymized graphs achieve high accuracy m querying.(4) For preserving graph data utility, we study preserving the reachabilities of the vertices in anonymized graphs. We design a reachability preserving anonymization (RPA for short) algorithm. The basic idea of RPA is to organize vertices into groups and greedily anonymizes each vertex with low anonymization cost on reachability. We devise a number of techniques to make RPA efficient. Firstly, we propose the reachable interval to efficiently measure the anonymization cost incurred by an edge addition. Secondly, we construct a candidate neighbor index to accelerate anonymizing each vertex. Experimental results illustrate that anonymized social networks generated by our methods preserve high data utility on reachability.(5) We implement a social network secure publishing protype demonstration system named SNSPDEMO. SNSPDEMO could evaluate the security of the social networks with respect to different types of privacy leakage. The vertices and edges with privacy leakaged could be highlighted by SNSPDEMO through the graphical interface. SNSPDEMO integrates the privacy protecting techniques proposed in this dissertation and provides corresponding privacy protection for social networks. SNSPDEMO also shows the difference between the original graph and the anonymized one.Regarding the potential threatens and challenges, this dissertation studys on key techniques of protecting privacy in social networks, including vertex privacy protection, sensitive relationship protection, sensitive labels protection and preserving graph data utility. This dissertation builds a foundation of providing a complete privacy protection for social networks.