  With the recent surge of social networks like Facebook, new forms of
recommendations have become possible - personalized recommendations of ads,
content, and even new friend and product connections based on one's social
interactions. Since recommendations may use sensitive social information, it is
speculated that these recommendations are associated with privacy risks. The
main contribution of this work is in formalizing these expected trade-offs
between the accuracy and privacy of personalized social recommendations.
  In this paper, we study whether "social recommendations", or recommendations
that are solely based on a user's social network, can be made without
disclosing sensitive links in the social graph. 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 prove lower bounds
on the minimum loss in utility for any recommendation algorithm that is
differentially private. We adapt two privacy preserving algorithms from the
differential privacy literature to the problem of social recommendations, and
analyze their performance in comparison to the lower bounds, both analytically
and experimentally. We show that good private social recommendations are
feasible only for a small subset of the users in the social network or for a
lenient setting of privacy parameters.
