Randomized Algorithm for Privacy Preservation in Social Networks

A privacy preservation method in social networks is proposed based on Gaussian randomization multiplication. The method applies an undirected weighted graph to representing a social network and perturbs the weights of some edges by using the Gaussian randomization multiplication to maintain the shortest path of the social network and to make its length as close as possible to that in the original network in order to realize the the privacy preservation in social networks. The feasibility of the proposed algorithm and the nonexistence of the perfect algorithm are proved theoretically. Simulation results obtained by the randomization multiplication method agree well with the theoretical analysis.