A Study Of Hypergraph Based Privacy Preserving Anonymization Techniques

With the rapid development of mobile internet and cloud computing, huge amount of data is generated in modern society. Data mining techniques enable us to discover the hidden value within big data, and assist in making decisions and improving service quality. Data publishing introduces platforms and intelligence from third parties or public. While it helps make better use of data, it brings about privacy concerns, and becomes the bottleneck of data sharing.To preserve user privacy, data publishers usually replace user identifier with meaningless symbols before publish data. This basic process cannot preserve user privacy well, as adversary may disclose user identity or sensitive information with the help of background knowledge and other datasets. To prevent this kind of attacks, various methods have been proposed, among those anonymization is a common technique.Our main contributions are as follows. First, we propose anonymization methods for cloud service data based on hypergraph. Second, we develop attack models and anonymization algorithms for geo-social networks based on constrained background knowledge. Early studies focus on relational data. We summarize advantages and shortcomings of several classical anonymity models. We also introduce some of their extensions as well as implementation techniques. With the wide spread of social networks, graph data get more and more attention. Since graph data are semi-structural, and are more complex than relational data, it is challenging to anonymize such data. Some achievements on relational data are modified to anonymize graph data. We systematically summarize the privacy models in social networks regard to privacy information, background knowledge and data utility. Hypergraph is an extension of graph. Being more expressive, it brings about more challenges to anonymization. Besides, hypergraph can also work as a tool to solve other anonymization problems. Details of our main works are as follows.Our first contribution is the study of privacy preserving techniques based on hypergraph rank set anonymization in cloud service data publication. In cloud environment, service providers offer a variety of services and applications. The data that describe usage relation between users and services or applications have high economic and analysis values, inspiring the demands for publishing such data. In this paper, hypergraph is adopted to model cloud service relation data, where users are represented by vertices and services are represented by hyperedges. We propose an attack model based on rank vector associated with vertices, and protect users from re-identification using anonymization method. We develop a two-step anonymization framework, in which we anonymize rank set first, and then reconstruct hypergraph based on the anonymized rank set, while minimizing the modification on hypergraph so as to reduce information loss. The effectiveness of our algorithms is validated by experiments.Our second contribution is the study of privacy preserving techniques based on heterogeneous data model in geo-social network data publication. Location based service is a kind of cloud service. The emerging of mobile internet makes location information more and more valuable. Various data formats make geo-social network data heterogeneous. Previous work on anonymization of geo-social network data has strong assumption about background knowledge, making huge impact on data utility. In this paper, we study background knowledge models in detail, and propose novel attack models and anonymization models. Concretely, background knowledge is defined as users’ frequent locations and part of frequent locations for part of users’ friends respectively. We also develop a complete solution based on combinatorial hypergraph to anonymize geo-social network data in two steps. We formulated practical data utility metrics that we try to optimize during anonymization process, and validate our algorithms through extensive experiments.