Privacy Preserving in Social Networks Against Sensitive Edge Disclosure

Lian Liu, Jie Wang, and Jun Zhang
Laboratory for High Performance Scientific Computing and Computer Simulation
Department of Computer Science
University of Kentucky
Lexington, KY 40506-0046, USA

Jinze Liu
Department of Computer Science
University of Kentucky
Lexington, KY 40506-0046, USA

Abstract

With the development of emerging social networks, such as Facebook and MySpace, security and privacy threats arising from social network analysis bring a risk of disclosure of confidential knowledge when the social network data is shared or made public. In addition to the current social network anonymity de-identification techniques, we study a situation, such as in business transaction networks or intelligence communities (terrorist networks), in which the network edges (transaction cost or terrorist contact frequency) as well as the corresponding weights are considered to be private. We consider preserving weights (data privacy) of some edges, while trying to preserve close shortest path lengths and exactly the same shortest paths (data utility) of some pairs of nodes. We develop two privacy-preserving strategies for this application. The first strategy is based on a Gaussian randomization multiplication, and the second one is a greedy perturbation algorithm which is based on the graph theory. Especially, the second strategy can not only keep a close shortest path length and exactly the same shortest path for certain selected paths, but also maximize the weight privacy preservation, demonstrated by our mathematical analysis and experiments.


Key words: Social networks, privacy preserving, shortest path, edge disclosure

Mathematics Subject Classification:


Download the the PDF file lianliu2.pdf.
Technical Report CMIDA-HiPSCCS 006-08, Department of Computer Science, University of Kentucky, Lexington, KY, 2008.

The research work of J. Zhang was supported in part by NSF under grants CCF-0527967 and CCF 0727600, in part by NIH under grant 1R01HL086644-01, in part by Alzheimer's Association under grant NIGR-06-25460, and in part by KSEF under grant KSEF-148-502-06-186.