[k₁, k₂]-anonymization of shortest paths

Privacy preserving network publishing has been studied extensively in recent years. Although more works have adopted un-weighted graphs to model network relationships, weighted graph modeling can provide deeper analysis of the degree of relationships. Previous works on weighted graph privacy have concentrated on preserving the shortest path characteristic between pairs of vertices. Two common types of privacy have been proposed. One type of privacy tried to add random noise edge weights to the graph but still maintain the same shortest path. The other privacy, k-shortest path privacy, minimally perturbed edge weights so that there exists k shortest paths. However, the k-shortest path privacy only considers anonymizing same fixed number of shortest paths for all pairs of source and destination vertices. In this work, we present a new concept called [k₁, k₂]-shortest path privacy to allow different number of shortest paths for different pairs of vertices. A published network graph with [k₁, k₂]-shortest path privacy has at least k' indistinguishable shortest paths between the source and destination vertices, where k₁≤k'≤k₂. A heuristic algorithm based on modifying only Non-Visited (NV) edges is proposed and experimental results showing the feasibility and characteristics of the proposed approach are presented.