  With the recent surge of social networks like Facebook, new forms of
recommendations have become possible -- personalized recommendations of ads,
content, and even new social and product connections based on one's social
interactions. 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. We also propose two recommendation algorithms that
satisfy differential privacy, analyze their performance in comparison to the
lower bound, both analytically and experimentally, and show that good private
social recommendations are feasible only for a few users in the social network
or for a lenient setting of privacy parameters.
