Proceedings of the VLDB Endowment · 2011 · 178 citations · 21 references
ComputingEconomicsPrivacy EngineeringRecommender SystemsSocial InfluenceDifferential PrivacyPrivacy-preserving AnalyticsPrivacy-preserving ProtocolsPrivacy-preserving RecommendationSocial RecommendationDifferential Privacy In RecommendationLower BoundsPrivacyPrivacy Risk Analysis In RecommendationSensitive Information ManagementSensitive Information ProtectionSocial Graph AnalysisSocial Graph Recommendation
With the recent surge of social networks such as Facebook, new forms of recommendations have become possible -- recommendations that rely on one's social connections in order to make personalized recommendations of ads, content, products, and people. Since recommendations may use sensitive information, it is speculated that these recommendations are associated with privacy risks. The main contribution of this work is in formalizing trade-offs between accuracy and privacy of personalized social recommendations. 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 then adapt two privacy preserving algorithms from the differential privacy literature to the problem of social recommendations, and analyze their performance in comparison to our 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.
21
The link prediction problem for social networks
David Liben‐Nowell, Jon Kleinberg · 2003 · 1.6K citations
Computing, Data Science, Data Mining +16
Towards Sharp Inapproximability For Any 2-CSP
Per Austrin · 2007 · 1.4K citations
Tables of Integrals and Other Mathematical Data.
H. B. Dwight · Biometrika · 1963 · 925 citations
Tables of Integrals and Other Mathematical Data.
J. W. W., H. B. Dwight · Mathematics of Computation · 1962 · 894 citations