Protecting link privacy for large correlated social networks

Recently, privacy protection attracts more and more research efforts especially for social network data. In the literature, most of existing approaches assume that social data are independent to each other which is not the case in the real world applications. In this paper, we are the first attempt to investigate the privacy protection issue when social data are correlated. We model the correlation as the probability that a vertex might be related to a given vertex, i.e., how likely a person could be friend of another person. The highly correlated vertex will not be selected as neighbor vertex in the perturbed graph. By doing this, we not only protect the direct neighbors but also the highly correlated indirect neighbor vertices. The corresponding privacy as well as the utility measurement are defined to evaluate whether the perturbed social graph is good or not. Experiments are performed on three datasets and compared with the state-of-the-art algorithm, and the promising results demonstrate that our approach can achieve comparably good results on a dense graph.