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: 3980
Venue: SIGMOD
Year: 2008
Pagerank: 0.00016478924
Overall Rank: 803 | 94.42%
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
505	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00021491332
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00011318916
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
3,161	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB	7.4613905e-05
4,039	Differential Privacy in Telco Big Data Platform	2015	VLDB	6.5075964e-05
4,349	Class-based graph anonymization for social network data	2009	VLDB	6.2647606e-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
10,102	PrivAGS: Differentially Private Attributed Graph Synthesis	2026	SIGMOD	4.1945683e-05
12,207	Surrogate Parenthood: Protected and Informative Graphs	2011	VLDB	4.1945683e-05
12,312	Anonymized Data: Generation, Models, Usage	2009	SIGMOD	4.1945683e-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.00032707646
304	On the Complexity of Optimal K-Anonymity	2004	PODS	0.00028290121

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,930	Privacy Preservation by Disassociation	2012	VLDB	4.427232e-05
6,410	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.0753667e-05
4,979	Fast Data Anonymization with Low Information Loss	2007	VLDB	5.7878768e-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
2,718	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.2409647e-05
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00011318916
5,351	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	5.5531181e-05
4,349	Class-based graph anonymization for social network data	2009	VLDB	6.2647606e-05
3,101	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.5598015e-05