skip to main content
10.1145/1242572.1242598acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
Article

Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography

Published: 08 May 2007 Publication History

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.

References

[1]
L. Adamic, E. Adar. How to search a social network. Social Networks 27(2005).
[2]
L. Adamic, O. Buyukkokten, E. Adar. A Social Network Caught in the Web. First Monday, 8(2003).
[3]
D. Agrawal. C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. Proc. PODS, 2001.
[4]
R. Agrawal, R. Srikant. Privacy-preserving data mining. Proc. SIGMOD, 2000.
[5]
N. Alon, J. Spencer, The Probabilistic Method, 1992.
[6]
L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group formation in large social networks: Membership, growth, and evolution. Proc. KDD, 2006.
[7]
M. Barbaro, T. Zeller. A Face Is Exposed for AOL Searcher No. 4417749. New York Times, 9 August 2006.
[8]
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.
[9]
B. Bollobás. Random Graphs. Cambridge, 2001.
[10]
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.
[11]
C. Dwork. Differential Privacy, Proc. ICALP, 2006.
[12]
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.
[13]
C. Dwork, F. McSherry, and K. Talwar, The Price of Privacy and the Limits of LP Decoding, submitted for publication.
[14]
P. Erdos. Some remarks on the theory of graphs. Bull. AMS 53 (1947), 292--294.
[15]
A. Evfimievski, J. Gehrke, R. Srikant. Limiting privacy breaches in privacy preserving data mining. Proc. PODS, 2003.
[16]
G. Flake, R. Tarjan, K. Tsioutsiouliklis. Graph Clustering and Minimum Cut Trees. Internet Math. 1(2004).
[17]
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.
[18]
R. Gomory, T.C. Hu. (1961). Multi-Terminal Network Flows. SIAM J. Appl. Math., 9:551--570.
[19]
G. Kossinets and D. J. Watts. Empirical Analysis of an Evolving Social Network. Science 311:88--90, 2006.
[20]
R. Kumar, R. Novak, P. Raghavan, A. Tomkins. Structure and evolution of blogspace. CACM, 47(2004).
[21]
R. Kumar, J. Novak, A. Tomkins. Structure and Evolution of Online Social Networks. Proc. KDD, 2006.
[22]
D. Liben-Nowell, R. Kumar, J. Novak, P. Raghavan, A. Tomkins. Geographic routing in social networks. PNAS 102(2005).
[23]
N. Mishra, M. Sandler. Privacy via Pseudorandom Sketches Proc. PODS, 2006.
[24]
A Narayanan, V. Shmatikov How To Break Anonymity of the Netflix Prize Dataset. arxiv cs/0610105, Oct. 2006.
[25]
J. Novak, P. Raghavan, A. Tomkins. Anti-Aliasing on the Web. Proc. WWW, 2004.
[26]
L. Sweeney. Weaving technology and policy together to maintain confidentiality. J Law Med Ethics, 25(1997).
[27]
L. Sweeney. k-anonymity: A model for protecting privacy. Intl. J. Uncertainty, Fuzziness and Knowledge-based Systems, 10(2002).

Cited By

View all
  • (2025)Recent Advances of Differential Privacy in Centralized Deep Learning: A Systematic SurveyACM Computing Surveys10.1145/371200057:6(1-28)Online publication date: 21-Jan-2025
  • (2025)Preserving Link Privacy in Uncertain Directed Social Graphs With Formal GuaranteesIEEE Transactions on Sustainable Computing10.1109/TSUSC.2024.339975410:1(108-119)Online publication date: Jan-2025
  • (2024)Publishing number of walks and katz centrality under local differential privacyProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702694(377-393)Online publication date: 15-Jul-2024
  • Show More Cited By

Index Terms

  1. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WWW '07: Proceedings of the 16th international conference on World Wide Web
    May 2007
    1382 pages
    ISBN:9781595936547
    DOI:10.1145/1242572
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 May 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. anonymization
    2. privacy in data mining
    3. social networks

    Qualifiers

    • Article

    Conference

    WWW'07
    Sponsor:
    WWW'07: 16th International World Wide Web Conference
    May 8 - 12, 2007
    Alberta, Banff, Canada

    Acceptance Rates

    Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)80
    • Downloads (Last 6 weeks)7
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2025)Recent Advances of Differential Privacy in Centralized Deep Learning: A Systematic SurveyACM Computing Surveys10.1145/371200057:6(1-28)Online publication date: 21-Jan-2025
    • (2025)Preserving Link Privacy in Uncertain Directed Social Graphs With Formal GuaranteesIEEE Transactions on Sustainable Computing10.1109/TSUSC.2024.339975410:1(108-119)Online publication date: Jan-2025
    • (2024)Publishing number of walks and katz centrality under local differential privacyProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702694(377-393)Online publication date: 15-Jul-2024
    • (2024)Privately learning smooth distributions on the hypercube by projectionsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693108(25936-25975)Online publication date: 21-Jul-2024
    • (2024)Edge Deletion based Subgraph HidingWSEAS TRANSACTIONS ON INFORMATION SCIENCE AND APPLICATIONS10.37394/23209.2024.21.3221(333-347)Online publication date: 17-Jul-2024
    • (2024)Anonymization: The imperfect science of using data while preserving privacyScience Advances10.1126/sciadv.adn705310:29Online publication date: 19-Jul-2024
    • (2024)Collecting Clustering Coefficient of Distributed Graph Data with Shuffled Differential Privacy2024 IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA)10.1109/ISPA63168.2024.00103(766-773)Online publication date: 30-Oct-2024
    • (2024)Hybrid Approach for the OSN Privacy Preservation using Artificial Intelligence2024 Asia Pacific Conference on Innovation in Technology (APCIT)10.1109/APCIT62007.2024.10673564(1-6)Online publication date: 26-Jul-2024
    • (2024)An embedding-based distance for temporal graphsNature Communications10.1038/s41467-024-54280-415:1Online publication date: 17-Nov-2024
    • (2024)AI-enhanced blockchain technology: A review of advancements and opportunitiesJournal of Network and Computer Applications10.1016/j.jnca.2024.103858(103858)Online publication date: Mar-2024
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media