On the (Im)possibility of Preserving Utility and Privacy in Personalized Social Recommendations

May 3 2010, 2:15am

"In this paper, we study whether 'social recommendations', or recommendations that utilize a user's social network, can be made without disclosing sensitive links between users. More precisely, we quantify the loss in utility when existing recommendation algorithms are modified to satisfy a strong notion of privacy called differential privacy. We propose lower bounds on the minimum loss in utility for any recommendation algorithm that is differentially private."