Towards Identity Anonymization on Graphs

Summary: Defines k-degree anonymity: every node has at least k−1 others with the same degree, enabling privacy against degree-based re-identification. Presents minimal-graph-modification algorithms to reach a closest k-degree anonymous graph, leveraging degree-sequence realizability; validated on synthetic and real networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3981
Venue: SIGMOD
Year: 2008
Pagerank: 0.00016463554
Overall Rank: 800 | 94.45%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Kun Liu
2. Evimaria Terzi

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
506	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00021481335
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.000113084
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
3,169	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB	7.4545379e-05
4,038	Differential Privacy in Telco Big Data Platform	2015	VLDB	6.5067029e-05
4,346	Class-based graph anonymization for social network data	2009	VLDB	6.2588738e-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
10,102	PrivAGS: Differentially Private Attributed Graph Synthesis	2026	SIGMOD	4.1905499e-05
12,215	Surrogate Parenthood: Protected and Informative Graphs	2011	VLDB	4.1905499e-05
12,320	Anonymized Data: Generation, Models, Usage	2009	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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
305	On the Complexity of Optimal K-Anonymity	2004	PODS	0.00028264843

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,822	Achieving Anonymity via Clustering	2006	PODS	8.0624025e-05
8,934	Privacy Preservation by Disassociation	2012	VLDB	4.4229886e-05
4,981	Fast Data Anonymization with Low Information Loss	2007	VLDB	5.7823243e-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
2,721	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.2331032e-05
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.000113084
5,360	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	5.5477372e-05
4,346	Class-based graph anonymization for social network data	2009	VLDB	6.2588738e-05
3,106	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.5550946e-05