Privacy preservation of affinities in social networks

Beyond the ongoing privacy preserving social network studies which mainly focus on node de-identification and link protection, this paper is written with the intention of preserving the privacy of link's affinities, or weights, in a finite and directed social network. To protect the weight privacy of edges, we define a privacy measurement, κ-anonymity, over individual weighted edges. It is considered in this paper that modified weights of edges should be released instead of the real ones for the purpose of making weighted edges indistinguishable. We transform original weighted edges to κ-anonymous edges, while preserving the shortest paths between node pairs as much as possible. To achieve this goal, a probabilistic graph is used to model the weighted and directed social network. Based on this probabilistic graph, we present a modification algorithm on the weights of edges to accomplish a balance between preserving the privacy of edge weight and the utilities of the shortest path. Finally, we give experimental results to support our theoretical analysis.