Differentially private graph-link analysis based social recommendation

Modern social networks always require a social recommendation system which recommends nodes to a target node based on the existing links originate from this target. This leads to a privacy problem since the target node can infer the links between other nodes by observing the recommendations it received. As a rigorous notion of privacy, differential privacy has been used to define the link privacy in social recommendation. However, existing work shows that the accuracy of applying differential privacy to the recommendation is poor, even under an unreasonable privacy guarantee. In this paper, we find that this negative conclusion is problematic due to an overly-restrictive definition on the sensitivity. We propose a mechanism to achieve differentially private graph-link analysis based social recommendation. We make experiments to evaluate the privacy and accuracy of our proposed mechanism, the results show that our proposed mechanism achieves a better trade-off between privacy and accuracy in comparison with existing work.