Anonymizing Multiple K-anonymous Shortest Paths for Social Graphs

To preserve privacy, k-anonymity on relational, set-valued, and graph data have been studied extensively in recent years. Information on social networks can be modeled as un-weighted or weighted graph data for sharing and publishing. We have previously proposed k-anonymous path privacy concept on weighted social graphs to preserve privacy of the shortest path [9]. A published social network graph with k-anonymous path privacy has at least k indistinguishable shortest paths between the source and destination vertices. However, previous work only considered modifying Never-Visited (NV) edges by other shortest paths. In this work, we further extend the approach and propose a new technique that can modify both NV edges and All-Visited (AV) edges to achieve the k-anonymous path privacy. Experimental results showing the characteristics of each technique are presented. It clearly provides different options to achieve the same level of privacy under different requirements.