Lars Backstrom
Jon Kleinberg
ABSTRACT
In a social network, nodes correspond topeople or other social entities, and edges correspond to social links between them. In an effort to preserve privacy, the practice of anonymization replaces names with meaningless unique identifiers. We describe a family of attacks such that even from a single anonymized copy of a social network, it is possible for an adversary to learn whether edges exist or not between specific targeted pairs of nodes.
- L. Adamic, E. Adar. How to search a social network. Social Networks 27(2005).Google Scholar
- L. Adamic, O. Buyukkokten, E. Adar. A Social Network Caught in the Web. First Monday, 8(2003).Google Scholar
- D. Agrawal. C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. Proc. PODS, 2001. Google ScholarDigital Library
- R. Agrawal, R. Srikant. Privacy-preserving data mining. Proc. SIGMOD, 2000. Google ScholarDigital Library
- N. Alon, J. Spencer, The Probabilistic Method, 1992.Google Scholar
- L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group formation in large social networks: Membership, growth, and evolution. Proc. KDD, 2006. Google ScholarDigital Library
- M. Barbaro, T. Zeller. A Face Is Exposed for AOL Searcher No. 4417749. New York Times, 9 August 2006.Google Scholar
- A.B. lum, C. Dwork, F. McSherry, K. Nissim. Practical privacy: The SuLQ framework. Proc. PODS, 2005. In Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 128--138, 2005. Google ScholarDigital Library
- B. Bollobás. Random Graphs. Cambridge, 2001.Google Scholar
- I. Dinur, K. Nissim. Revealing information while preserving privacy. Proc. PODC, 2003. In Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 202--210, 2003. Google ScholarDigital Library
- C. Dwork. Differential Privacy, Proc. ICALP, 2006. Google ScholarDigital Library
- C. Dwork, F. McSherry, K. Nissim, A. Smith. Calibrating noise to sensitivity in private data analysis. Proc. TCC, 2006. In Proceedings of the 3rd Theory of Cryptography Conference, pages 265--284, 2006. Google ScholarDigital Library
- C. Dwork, F. McSherry, and K. Talwar, The Price of Privacy and the Limits of LP Decoding, submitted for publication.Google Scholar
- P. Erdos. Some remarks on the theory of graphs. Bull. AMS 53 (1947), 292--294.Google ScholarCross Ref
- A. Evfimievski, J. Gehrke, R. Srikant. Limiting privacy breaches in privacy preserving data mining. Proc. PODS, 2003. Google ScholarDigital Library
- G. Flake, R. Tarjan, K. Tsioutsiouliklis. Graph Clustering and Minimum Cut Trees. Internet Math. 1(2004).Google Scholar
- S. Golder, D. Wilkinson B. Huberman. Rhythms of Social Interaction: Messaging within a Massive Online Network. Proc. 3rd Intl. Conf. on Communities and Technologies, 2007.Google ScholarCross Ref
- R. Gomory, T.C. Hu. (1961). Multi-Terminal Network Flows. SIAM J. Appl. Math., 9:551--570.Google Scholar
- G. Kossinets and D. J. Watts. Empirical Analysis of an Evolving Social Network. Science 311:88--90, 2006.Google ScholarCross Ref
- R. Kumar, R. Novak, P. Raghavan, A. Tomkins. Structure and evolution of blogspace. CACM, 47(2004). Google ScholarDigital Library
- R. Kumar, J. Novak, A. Tomkins. Structure and Evolution of Online Social Networks. Proc. KDD, 2006. Google ScholarDigital Library
- D. Liben-Nowell, R. Kumar, J. Novak, P. Raghavan, A. Tomkins. Geographic routing in social networks. PNAS 102(2005).Google Scholar
- N. Mishra, M. Sandler. Privacy via Pseudorandom Sketches Proc. PODS, 2006. Google ScholarDigital Library
- A Narayanan, V. Shmatikov How To Break Anonymity of the Netflix Prize Dataset. arxiv cs/0610105, Oct. 2006.Google Scholar
- J. Novak, P. Raghavan, A. Tomkins. Anti-Aliasing on the Web. Proc. WWW, 2004. Google ScholarDigital Library
- L. Sweeney. Weaving technology and policy together to maintain confidentiality. J Law Med Ethics, 25(1997).Google Scholar
- L. Sweeney. k-anonymity: A model for protecting privacy. Intl. J. Uncertainty, Fuzziness and Knowledge-based Systems, 10(2002). Google ScholarDigital Library
Index Terms
- Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography
Recommendations
Challenges in mining social network data: processes, privacy, and paradoxes
KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data miningThe profileration of rich social media, on-line communities, and collectively produced knowledge resources has accelerated the convergence of technological and social networks, producing environments that reflect both the architecture of the underlying ...
Preservation of Centrality Measures in Anonymized Social Networks
SOCIALCOM '13: Proceedings of the 2013 International Conference on Social ComputingSocial media sites became a pervasive presence in the nowadays society. We can learn a lot of useful information about human behavior and interaction by paying attention to the information and relations of social media users. This information can be ...
GASNA: greedy algorithm for social network anonymization
ASONAM '13: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and MiningThe proliferation of social networks in digital media has proved to be fruitful, but this rise in popularity is accompanied by user privacy concerns. Social network data has been published in various ways and preserving the privacy of individuals in the ...
Comments