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: 9909
Venue: VLDB
Year: 2009
Pagerank: 7.4545379e-05
Overall Rank: 3,169 | 77.98%
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,686	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	8.31087e-05
3,106	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.5550946e-05
4,942	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	5.8124358e-05
5,360	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	5.5477372e-05
5,494	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	5.4770961e-05
6,190	Privacy-Aware Data Management in Information Networks	2011	SIGMOD	5.1604866e-05
6,406	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.0704962e-05
8,303	Personalized Privacy Protection in Social Networks	2011	VLDB	4.5392079e-05
9,561	T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph	2023	SIGMOD	4.3212967e-05
10,102	PrivAGS: Differentially Private Attributed Graph Synthesis	2026	SIGMOD	4.1905499e-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.0003266103
633	m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets	2007	SIGMOD	0.00018881387
654	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00018594644
800	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016463554
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.000113084
2,721	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.2331032e-05
8,306	Privacy Preserving Serial Data Publishing By Role Composition	2008	VLDB	4.5392079e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,475	Privacy-Enhancing k-Anonymization of Customer Data	2005	PODS	4.714352e-05
4,346	Class-based graph anonymization for social network data	2009	VLDB	6.2588738e-05
13,420	Privacy Preserving Social Graphs for High Precision Community Detection	2014	SIGMOD	-
3,382	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.1538038e-05
458	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD	0.00022698513
800	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016463554
6,406	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.0704962e-05
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.000113084
8,303	Personalized Privacy Protection in Social Networks	2011	VLDB	4.5392079e-05
5,360	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	5.5477372e-05