February 17, 2009
Lian Liu, Jinze Liu and Jun Zhang
Department of Computer Science
University of Kentucky
Lexington, KY 40506-0046, USA
The availability of digital technologies and internet develop- ment has promoted a proliferation of social networks. Due to the public awareness of privacy protection, the sharing po- tential of certain social networks may be seriously hampered by the need for a balance between the protection of sensi- tive content and public availability of data utility. So privacy preservation technologies should be exercised to protect so- cial networks against various privacy leakages and attacks. Beyond the ongoing privacy preserving social network stud- ies which mainly focus on node de-identi¯cation and link protection, this paper is written with the intention of pre- serving the privacy of link's a±nities, or weights, in a ¯nite and directed social network. To protect the weight privacy of edges, we de¯ne a privacy measurement, k-anonymous, over individual weighted edges. A k-anonymous weighted edge can make itself more indistinguishable from adjacent edges with respect to edge weights rather than node degrees. It is considered in this paper that modi¯ed weights of some edges should be released instead of the real ones to trans- form original weighted edges to k-anonymous edges, while preserving the shortest paths and the corresponding lengths between user-de¯ned 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 proba- bilistic graph, random walk, and matrix analysis, we present a modi¯cation algorithm on the weights of edges to accom- plish a balance between the weight privacy preservation and the shortest path utilization. Finally, we give experimental results to support our theoretical analysis.
Mathematics Subject Classification: