The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
K-isomorphism: privacy preserving network publication against structural attacks
Abstract
Serious concerns on privacy protection in social networks have been raised in recent years; however, research in this area is still in its infancy. The problem is challenging due to the diversity and complexity of graph data, on which an adversary can use many types of background knowledge to conduct an attack. One popular type of attacks as studied by pioneer work [2] is the use of embedding subgraphs. We follow this line of work and identify two realistic targets of attacks, namely, NodeInfo and LinkInfo. Our investigations show that k-isomorphism, or anonymization by forming k pairwise isomorphic subgraphs, is both sufficient and necessary for the protection. The problem is shown to be NP-hard. We devise a number of techniques to enhance the anonymization efficiency while retaining the data utility. A compound vertex ID mechanism is also introduced for privacy preservation over multiple data releases. The satisfactory performance on a number of real datasets, including HEP-Th, EUemail and LiveJournal, illustrates that the high symmetry of social networks is very helpful in mitigating the difficulty of the problem.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
SWEENEY, L. (2002) · International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems · doi:10.1142/s0218488502001648 · Cited by 8,571
The political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619
L-diversity: privacy beyond k-anonymity
Machanavajjhala, A., Gehrke, J., Kifer, D., & Venkitasubramaniam, M. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.1 · Cited by 2,362
Protecting respondents identities in microdata release
Samarati, P. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.971193 · Cited by 2,324
Group formation in large social networks: membership, growth, and evolution
Backstrom, L., Huttenlocher, D., Kleinberg, J., & Lan, X. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150412 · Cited by 1,805
Samarati, P., & Sweeney, L. (2018) · doi:10.1184/r1/6625469 · Cited by 1,326
Structure and evolution of online social networks
Kumar, R., Novak, J., & Tomkins, A. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150476 · Cited by 1,084
Getoor, L., & Diehl, C. P. (2005) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1117454.1117456 · Cited by 973
Backstrom, L., Dwork, C., & Kleinberg, J. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242598 · Cited by 850
Towards identity anonymization on graphs
Liu, K., & Terzi, E. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376629 · Cited by 773
Microscopic evolution of social networks
Leskovec, J., Backstrom, L., Kumar, R., & Tomkins, A. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401948 · Cited by 728
Preserving Privacy in Social Networks Against Neighborhood Attacks
Zhou, B., & Pei, J. (2008) · 2008 IEEE 24th International Conference on Data Engineering · doi:10.1109/icde.2008.4497459 · Cited by 719
Anatomy: simple and effective privacy preservation
Xiao, X., & Tao, Y. (2006) · Very Large Data Bases · doi:10.5555/1182635.1164141 · Cited by 642
(α, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing
Wong, R. C.-W., Li, J., Fu, A. W.-C., & Wang, K. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150499 · Cited by 625
Self-citationThe Computer Science Department.
Tolman, H. (1971) · Cited by 554
Resisting structural re-identification in anonymized social networks
Hay, M., Miklau, G., Jensen, D., Towsley, D., & Weis, P. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453873 · Cited by 549
k-automorphism: a general framework for privacy preserving network publication
Zou, L., Chen, L., & Özsu, M. T. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687734 · Cited by 409
Preserving the Privacy of Sensitive Relationships in Graph Data
Zheleva, E., & Getoor, L. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78478-4_9 · Cited by 403
The structure of information pathways in a social communication network
Kossinets, G., Kleinberg, J., & Watts, D. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401945 · Cited by 332
(2010) · Chapman & Hall/CRC Data Mining and Knowledge Discovery Series · doi:10.1201/9781420091502-c15 · Cited by 328
Randomizing Social Networks: a Spectrum Preserving Approach
Ying, X., & Wu, X. (2008) · Proceedings of the 2008 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972788.67 · Cited by 311
Topic and role discovery in social networks
McCallum, A., Corrada-Emmanuel, A., & Wang, X. (2005) · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · Cited by 287
Center-piece subgraphs: problem definition and fast solutions
Tong, H., & Faloutsos, C. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150448 · Cited by 264
Anonymizing bipartite graph data using safe groupings
Cormode, G., Srivastava, D., Yu, T., & Zhang, Q. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453947 · Cited by 222
Measuring and extracting proximity in networks
Koren, Y., North, S. C., & Volinsky, C. T. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150432 · Cited by 132
Finding maximal cliques in massive networks by H*-graph
Cheng, J. S.-C., Ke, Y., Fu, A. W.-C., et al. (2010) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/1807167.1807217 · Cited by 104
Self-citationFinding Frequent Patterns in a Large Sparse Graph
Kuramochi, M., & Karypis, G. (2004) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.32 · Cited by 91
A Clustering Approach for Data and Structural Anonymity in Social Networks
Campan, A., & Truţă, T. M. (2008) · Cited by 88
Emergence of symmetry in complex networks
Xiao, Y., Xiong, M., Wang, W., & Wang, H. (2008) · Physical Review E · doi:10.1103/physreve.77.066108 · Cited by 53
Cited by
Measuring Large-Scale Social Networks with High Resolution
Stopczynski, A., Sekara, V., Sapiezynski, P., Cuttone, A., Madsen, M. M., Larsen, J. E., & Lehmann, S. (2014) · PLoS ONE · doi:10.1371/journal.pone.0095978 · Cited by 409
A Review of Anonymization for Healthcare Data
Olatunji, I. E., Rauch, J., Katzensteiner, M., & Khosla, M. (2024) · Big Data · doi:10.1089/big.2021.0169 · Cited by 101
Metadata
- Authors
- Cheng, J., Fu, A. W.-C., & Liu, J.
- Venue
- Proceedings of the 2010 ACM SIGMOD International Conference on Management of data
- Publisher
- ACM
- Published
- 2010-06-06
- Pages
- 459-470
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2032186932
- Cited by
- 348
- References
- 30
- FWCI
- 20.01
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.