Confining Edge Types in K-anonymization of Shortest Paths

In recent years, the problem of privacy preservation on published social networks has become more and more important. The social media data are available on the popular on-line social network websites with rich personal information, which can be analyzed for connectivity and user behaviors. In this work, we study the problem of preserving sensitive paths in social networks. We examine the new concept called k-anonymous path privacy and propose two algorithms, based on the greedy approach with two different types of edges, namely Partially-Visited (PV) edges and None-Visited (NV) edges, which minimally perturbed the edge weights to achieve the path anonymity under different requirements. The numerical experiments showing the characteristics of the proposed algorithms are given. The results demonstrate that the proposed algorithms are feasible to achieve the k-anonymous path privacy, with different performances on directed and un-directed weighted graphs, and could be applied to different privacy requirements.