TY - GEN

T1 - Privacy preservation in social networks with sensitive edge weights

AU - Liu, Lian

AU - Wang, Jie

AU - Liu, Jinze

AU - Zhang, Jun

PY - 2009

Y1 - 2009

N2 - 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 a business transaction network, in which weights are attached to network edges that are considered to be confidential (e.g., transactions). We consider perturbing the weights of some edges to preserve data privacy when the network is published, while retaining the shortest path and the approximate cost of the path between some pairs of nodes in the original network. We develop two privacy-preserving strategies for this application. The first strategy is based on a Gaussian randomization multiplication, the second one is a greedy perturbation algorithm based on graph theory. In particular, the second strategy not only yields an approximate length of the shortest path while maintaining the shortest path between selected pairs of nodes, but also maximizes privacy preservation of the original weights. We present experimental results to support our mathematical analysis.

AB - 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 a business transaction network, in which weights are attached to network edges that are considered to be confidential (e.g., transactions). We consider perturbing the weights of some edges to preserve data privacy when the network is published, while retaining the shortest path and the approximate cost of the path between some pairs of nodes in the original network. We develop two privacy-preserving strategies for this application. The first strategy is based on a Gaussian randomization multiplication, the second one is a greedy perturbation algorithm based on graph theory. In particular, the second strategy not only yields an approximate length of the shortest path while maintaining the shortest path between selected pairs of nodes, but also maximizes privacy preservation of the original weights. We present experimental results to support our mathematical analysis.

UR - http://www.scopus.com/inward/record.url?scp=72749117908&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=72749117908&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:72749117908

SN - 9781615671090

T3 - Society for Industrial and Applied Mathematics - 9th SIAM International Conference on Data Mining 2009, Proceedings in Applied Mathematics

SP - 949

EP - 960

BT - Society for Industrial and Applied Mathematics - 9th SIAM International Conference on Data Mining 2009, Proceedings in Applied Mathematics 133

T2 - 9th SIAM International Conference on Data Mining 2009, SDM 2009

Y2 - 30 April 2009 through 2 May 2009

ER -