Preserving utility in social network graph anonymization

To protect from privacy disclosure, the social network graph is modified in order to hide the information that potentially be used to disclose person's identity. However, when the social network graph is changed, it is a great challenge to balance between the privacy gained and the loss of data utility. In this paper, we address this problem. We propose a new graph topological-based metric to improve utility preservation in social network graph anonymization. We compare the proposed approach with the amount-of-edge-change metric that popularly used in most of previous works. Experimental evaluation shows that our approach generates anonymized social network with improved utility preservation.

Privacy preserving in location data release: A differential privacy approach

Communication devices with GPS chips allow people to generate large volumes of location data. However, location datasets have been confronted with serious privacy concerns. Recently, several privacy techniques have been proposed but most of them lack a strict privacy notion, and can hardly resist the number of possible attacks. This paper proposes a private release algorithm to randomize location datasets in a strict privacy notion, differential privacy. This algorithm includes three privacy-preserving operations: Private Location Clustering shrinks the randomized domain and Cluster Weight Perturbation hides the weights of locations, while Private Location Selection hides the exact locations of a user. Theoretical analysis on utility confirms an improved trade-off between the privacy and utility of released location data. The experimental results further suggest this private release algorithm can successfully retain the utility of the datasets while preserving users’ privacy.

Location privacy preserving for semantic-aware applications

With the increase use of location-based services, location privacy has recently raised serious concerns. To protect a user from being identified, a cloaked spatial region that contains other k-1 nearest neighbors of the user is used to replace the accurate position. In this paper, we consider location-aware applications that services are different among regions. To search nearest neighbors, we define a novel distance measurement that combines the semantic distance and the Euclidean distance to address the privacy preserving issue in the above-mentioned applications. We also propose an algorithm kNNH to implement our proposed method. The experimental results further suggest that the proposed distance metric and the algorithm can successfully retain the utility of the location services while preserving users’ privacy.

Differentially private random forest with high utility

Privacy-preserving data mining has become an active focus of the research community in the domains where data are sensitive and personal in nature. For example, highly sensitive digital repositories of medical or financial records offer enormous values for risk prediction and decision making. However, prediction models derived from such repositories should maintain strict privacy of individuals. We propose a novel random forest algorithm under the framework of differential privacy. Unlike previous works that strictly follow differential privacy and keep the complete data distribution approximately invariant to change in one data instance, we only keep the necessary statistics (e.g. variance of the estimate) invariant. This relaxation results in significantly higher utility. To realize our approach, we propose a novel differentially private decision tree induction algorithm and use them to create an ensemble of decision trees. We also propose feasible adversary models to infer about the attribute and class label of unknown data in presence of the knowledge of all other data. Under these adversary models, we derive bounds on the maximum number of trees that are allowed in the ensemble while maintaining privacy. We focus on binary classification problem and demonstrate our approach on four real-world datasets. Compared to the existing privacy preserving approaches we achieve significantly higher utility.

Privacy preserving data release for tagging recommender systems

Tagging recommender systems allow Internet users to annotate resources with personalized tags. The connection among users, resources and these annotations, often called a folksonomy, permits users the freedom to explore tags, and to obtain recommendations. Releasing these tagging datasets accelerates both commercial and research work on recommender systems. However, tagging recommender systems has been confronted with serious privacy concerns because adversaries may re-identify a user and her/his sensitive information from the tagging dataset using a little background information. Recently, several private techniques have been proposed to address the problem, but most of them lack a strict privacy notion, and can hardly resist the number of possible attacks. This paper proposes an private releasing algorithm to perturb users' profile in a strict privacy notion, differential privacy, with the goal of preserving a user's identity in a tagging dataset. The algorithm includes three privacy-preserving operations: Private Tag Clustering is used to shrink the randomized domain and Private Tag Selection is then applied to find the most suitable replacement tags for the original tags. To hide the numbers of tags, the third operation, Weight Perturbation, finally adds Laplace noise to the weight of tags. We present extensive experimental results on two real world datasets, De.licio.us and Bibsonomy. While the personalization algorithm is successful in both cases, our results further suggest the private releasing algorithm can successfully retain the utility of the datasets while preserving users' identity.

Privacy-preserving topic model for tagging recommender systems

Tagging recommender systems provide users the freedom to explore tags and obtain recommendations. The releasing and sharing of these tagging datasets will accelerate both commercial and research work on recommender systems. However, releasing the original tagging datasets is usually confronted with serious privacy concerns, because adversaries may re-identify a user and her/his sensitive information from tagging datasets with only a little background information. Recently, several privacy techniques have been proposed to address the problem, but most of these lack a strict privacy notion, and rarely prevent individuals being re-identified from the dataset. This paper proposes a privacy- preserving tag release algorithm, PriTop. This algorithm is designed to satisfy differential privacy, a strict privacy notion with the goal of protecting users in a tagging dataset. The proposed PriTop algorithm includes three privacy-preserving operations: Private topic model generation structures the uncontrolled tags; private weight perturbation adds Laplace noise into the weights to hide the numbers of tags; while private tag selection finally finds the most suitable replacement tags for the original tags, so the exact tags can be hidden. We present extensive experimental results on four real-world datasets, Delicious, MovieLens, Last.fm and BibSonomy. While the recommendation algorithm is successful in all the cases, our results further suggest the proposed PriTop algorithm can successfully retain the utility of the datasets while preserving privacy.

Privacy aware K-means clustering with high utility

Privacy-preserving data mining aims to keep data safe, yet useful. But algorithms providing strong guarantees often end up with low utility. We propose a novel privacy preserving framework that thwarts an adversary from inferring an unknown data point by ensuring that the estimation error is almost invariant to the inclusion/exclusion of the data point. By focusing directly on the estimation error of the data point, our framework is able to significantly lower the perturbation required. We use this framework to propose a new privacy aware K-means clustering algorithm. Using both synthetic and real datasets, we demonstrate that the utility of this algorithm is almost equal to that of the unperturbed K-means, and at strict privacy levels, almost twice as good as compared to the differential privacy counterpart.

Privacy preserving collaborative filtering for KNN attack resisting

Privacy preserving is an essential aspect of modern recommender systems. However, the traditional approaches can hardly provide a rigid and provable privacy guarantee for recommender systems, especially for those systems based on collaborative filtering (CF) methods. Recent research revealed that by observing the public output of the CF, the adversary could infer the historical ratings of the particular user, which is known as the KNN attack and is considered a serious privacy violation for recommender systems. This paper addresses the privacy issue in CF by proposing a Private Neighbor Collaborative Filtering (PriCF) algorithm, which is constructed on the basis of the notion of differential privacy. PriCF contains an essential privacy operation, Private Neighbor Selection, in which the Laplace noise is added to hide the identity of neighbors and the ratings of each neighbor. To retain the utility, the Recommendation-Aware Sensitivity and a re-designed truncated similarity are introduced to enhance the performance of recommendations. A theoretical analysis shows that the proposed algorithm can resist the KNN attack while retaining the accuracy of recommendations. The experimental results on two real datasets show that the proposed PriCF algorithm retains most of the utility with a fixed privacy budget.

Utility functions on locally connected spaces

We investigate the role of local connectedness in utility theory and prove that any continuous total preorder on a locally connected separable space is continuously representable. This is a new simple criterion for the representability of continuous preferences, and is not a consequence of the standard theorems in utility theory that use conditions such as connectedness and separability, second countability, or path-connectedness. Finally we give applications to problems involving the existence of value functions in population ethics and to the problem of proving the existence of continuous utility functions in general equilibrium models with land as one of the commodities. (C) 2003 Elsevier B.V. All rights reserved.

Functional educational characterisation of the utility of embalming fluids for anatomical education and research

Human cadavers have long been used to teach human anatomy and are increasingly used in other disciplines. Different embalming techniques have been reported in the literature; however there is no clear consensus on the opinion of anatomists on the utility of embalmed cadavers for the teaching of anatomy. To this end, we aimed to survey British and Irish anatomy teachers to report their opinions on different preservation methods for the teaching of anatomy. In this project eight human cadavers were embalmed using formalin, Genelyn, Thiel and Imperial College London- Soft Preserving (ICL-SP) techniques to compare different characteristics of these four techniques. The results of this thesis show that anatomy teachers consider hard-fixed cadavers not to be the most accurate teaching model in comparison to the human body, although it still serves as a useful teaching method (Chapter 2). In addition, our findings confirm that joints of cadavers embalmed using ICL-SP solution faithfully mimics joints of an unembalmed cadaver compared to the other techniques (Chapter 3). Embalming a human body prevents the deterioration in the quality of images and our findings highlight that the influence of the embalming solutions varied with the radiological modality used (Chapter 4). The method developed as part of this thesis enables anatomists and forensic scientists to quantify the decomposition rate of an embalmed human cadaver (Chapter 5). Formalin embalming solution showed the strongest antimicrobial abilities followed by Thiel, Genelyn and finally by ICL-SP (Chapter 6). The overarching viewpoint of this set of studies show that it is inaccurate to state that one embalming technique is ultimately the best. The value of each technique differs based on the requirement of the particular education or research area. Hence we highlight how different embalming techniques may be better suited to certain fields of study.

Semantic analysis in location privacy preserving

With the increasing use of location-based services, location privacy has recently started raising serious concerns. Location perturbation and obfuscation are most widely used for location privacy preserving. To protect a user from being identified, a cloaked spatial region that contains other k - 1 nearest neighbors of the user is submitted to the location-based service provider, instead of the accurate position. In this paper, we consider the location-aware applications that services are different among regions. In such scenarios, the semantic distance between users should be considered besides the Euclidean distance for searching the neighbors of a user. We define a novel distance measurement that combines the semantic and the Euclidean distance to address the privacy-preserving issue in the aforementioned applications. We also present an algorithm kNNH to implement our proposed method. Moreover, we conduct performance study experiments on the proposed algorithm. The experimental results further suggest that the proposed distance metric and the algorithm can successfully retain the utility of the location services while preserving users' privacy.

Utility-aware social network graph anonymization

As the need for social network data publishing continues to increase, how to preserve the privacy of the social network data before publishing is becoming an important and challenging issue. A common approach to address this issue is through anonymization of the social network structure. The problem with altering the structure of the links relationship in social network data is how to balance between the gain of privacy and the loss of information (data utility). In this paper, we address this problem. We propose a utility-aware social network graph anonymization. The approach is based on a new metric that calculates the utility impact of social network link modification. The metric utilizes the shortest path length and the neighborhood overlap as the utility value. The value is then used as a weight factor in preserving structural integrity in the social network graph anonymization. For any modification made to the social network links, the proposed approach guarantees that the distance between vertices in the modified social network stays as close as the original social network graph prior to the modification. Experimental evaluation shows that the proposed metric improves the utility preservation as compared to the number-of-change metric.