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: hfa87e6b445d9aae7
Venue: SIGMOD
Year: 2008
Pagerank: 0.00012503902
Overall Rank: 1,010 | 93.24%
DOI: 10.1145/1376616.1376629

Incoming Non-self Citations Over Time

Authors

1. Kun Liu (IBM)
2. Evimaria Terzi (IBM)

BibTeX Citation

@inproceedings{liu_sigmod08,
        title = {{Towards Identity Anonymization on Graphs}},
        author = {Liu, Kun and Terzi, Evimaria},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376629},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376629},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
880	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00013249752
1,373	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00010869791
2,021	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	9.160422e-05
2,979	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB	7.77653e-05
3,046	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.7023081e-05
4,107	Differential Privacy in Telco Big Data Platform	2015	VLDB	6.7901733e-05
4,228	Class-based graph anonymization for social network data	2009	VLDB	6.7078243e-05
5,045	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	6.2887092e-05
5,345	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	6.1567883e-05
5,597	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	6.0539934e-05
6,426	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.7716317e-05
6,440	Privacy-Aware Data Management in Information Networks	2011	SIGMOD	5.7674913e-05
8,740	Personalized Privacy Protection in Social Networks	2011	VLDB	5.2705676e-05
10,661	PrivAGS: Differentially Private Attributed Graph Synthesis	2026	SIGMOD	4.9605343e-05
12,742	Surrogate Parenthood: Protected and Informative Graphs	2011	VLDB	4.9605343e-05
12,845	Anonymized Data: Generation, Models, Usage	2009	SIGMOD	4.9605343e-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
347	Generalizing Data to Provide Anonymity when Disclosing Information	1998	PODS	0.00020249479
406	On the Complexity of Optimal K-Anonymity	2004	PODS	0.00019009895

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,426	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD
2	3,177	Achieving Anonymity via Clustering	2006	PODS
3	4,826	Fast Data Anonymization with Low Information Loss	2007	VLDB
4	13,966	Privacy Preserving Social Graphs for High Precision Community Detection	2014	SIGMOD
5	3,305	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
6	2,496	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB
7	1,373	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB
8	5,345	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD
9	4,228	Class-based graph anonymization for social network data	2009	VLDB
10	3,046	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB