K-anonymous path privacy on social graphs

摘要

Growing popularity of social networking not only brings the convenience of information sharing but also concerns of privacy breaches. Information on social networks can be modeled as un-weighted or weighted graph data. To preserve privacy, k-anonymity on relational, set-valued, and graph data have been studied extensively in recent years. In this work, we consider the edge weight anonymity problem. In particular, to protect the weight privacy of the shortest path between two vertices on a weighted graph, we present a new concept called k-anonymous path privacy. A published social network graph with k-anonymous path privacy has at least k indistinguishable shortest paths between the source and destination vertices. Three greedy-based modification algorithms, based on modifying different types of edges, to achieve k-anonymous path privacy are proposed. Experimental results showing the feasibility and characteristics of the proposed approach are presented. The proposed techniques clearly provide different options to achieve the same level of privacy under different requirements.