K-Automorphism: A General Framework for Privacy Preserving Network Publication

Summary: Proposes k-automorphism, a framework for privacy-preserving network publication to resist structural re-identification. Develops KM, an algorithm enforcing k-automorphism and supporting dynamic releases; experiments show privacy with good performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10099
Venue: VLDB
Year: 2009
Pagerank: 7.9708764e-05
Overall Rank: 2,909 | 80.05%
DOI: 10.14778/1687627.1687734

Incoming Non-self Citations Over Time

Authors

1. Lei Zou (Huazhong University of Science and Technology)
2. Lei Chen (Hong Kong University of Science and Technology)
3. M. Tamer Özsu (University of Waterloo)

BibTeX Citation

@article{zou_vldb09,
        title = {{K-Automorphism: A General Framework for Privacy Preserving Network Publication}},
        author = {Zou, Lei and Chen, Lei and Özsu, M. Tamer},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687734},
        url = {https://doi.org/10.14778/1687627.1687734},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,960	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	9.4058693e-05
2,977	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.9035901e-05
5,227	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	6.3085805e-05
5,384	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	6.2370509e-05
5,507	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	6.1924452e-05
6,288	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.9264969e-05
6,304	Privacy-Aware Data Management in Information Networks	2011	SIGMOD	5.9210809e-05
8,478	T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph	2023	SIGMOD	5.4170414e-05
8,545	Personalized Privacy Protection in Social Networks	2011	VLDB	5.4119882e-05
10,392	PrivAGS: Differentially Private Attributed Graph Synthesis	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
338	Generalizing Data to Provide Anonymity when Disclosing Information	1998	PODS	0.00020731054
572	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00016316092
985	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00012818114
1,010	m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets	2007	SIGMOD	0.00012684067
1,326	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00011145219
2,430	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.5885381e-05
8,548	Privacy Preserving Serial Data Publishing By Role Composition	2008	VLDB	5.4119882e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,875	Privacy-Enhancing k-Anonymization of Customer Data	2005	PODS
2	4,125	Class-based graph anonymization for social network data	2009	VLDB
3	13,608	Privacy Preserving Social Graphs for High Precision Community Detection	2014	SIGMOD
4	3,232	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
5	450	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD
6	985	Towards Identity Anonymization on Graphs	2008	SIGMOD
7	6,288	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD
8	1,326	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB
9	8,545	Personalized Privacy Protection in Social Networks	2011	VLDB
10	5,227	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD