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: 9908
Venue: VLDB
Year: 2009
Pagerank: 7.4613905e-05
Overall Rank: 3,161 | 78.02%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,683	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	8.315553e-05
3,101	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.5598015e-05
4,940	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	5.8180285e-05
5,351	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	5.5531181e-05
5,485	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	5.4813218e-05
6,185	Privacy-Aware Data Management in Information Networks	2011	SIGMOD	5.1666285e-05
6,410	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.0753667e-05
8,309	Personalized Privacy Protection in Social Networks	2011	VLDB	4.5435639e-05
9,561	T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph	2023	SIGMOD	4.3254416e-05
10,102	PrivAGS: Differentially Private Attributed Graph Synthesis	2026	SIGMOD	4.1945683e-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
225	Generalizing Data to Provide Anonymity when Disclosing Information	1998	PODS	0.00032707646
634	m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets	2007	SIGMOD	0.00018895628
654	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00018613167
803	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016478924
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00011318916
2,718	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.2409647e-05
8,312	Privacy Preserving Serial Data Publishing By Role Composition	2008	VLDB	4.5435639e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,541	Privacy-Enhancing k-Anonymization of Customer Data	2005	PODS	4.7157092e-05
4,349	Class-based graph anonymization for social network data	2009	VLDB	6.2647606e-05
13,407	Privacy Preserving Social Graphs for High Precision Community Detection	2014	SIGMOD	-
3,381	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.1604078e-05
455	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD	0.00022717354
803	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016478924
6,410	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.0753667e-05
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00011318916
8,309	Personalized Privacy Protection in Social Networks	2011	VLDB	4.5435639e-05
5,351	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	5.5531181e-05