Injecting Uncertainty in Graphs for Identity Obfuscation

Summary: Proposes injecting uncertainty into social graphs and publishing uncertain graphs for anonymization. Unlike binary edge add/remove, partial perturbation preserves more utility at the same obfuscation level, yielding higher usefulness on real networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10374
Venue: VLDB
Year: 2012
Pagerank: 7.5598015e-05
Overall Rank: 3,101 | 78.43%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,636	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	6.8976555e-05
4,179	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	6.3800553e-05
6,171	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB	5.170101e-05
6,172	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB	5.170101e-05
6,393	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.0837624e-05
6,545	Clustering Uncertain Graphs	2018	VLDB	5.0193115e-05
8,907	Shortest Paths Discovery in Uncertain Networks via Transfer Learning	2023	SIGMOD	4.427232e-05
9,580	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	4.3234342e-05
9,793	uBlade: Efficient Batch Processing for Uncertain Graph Queries	2024	SIGMOD	4.2818172e-05
11,259	Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem	2023	VLDB	4.1945683e-05
11,793	Efficient Computation of Feedback Arc Set at Web-Scale	2017	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
803	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016478924
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
1,450	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011925844
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
3,161	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB	7.4613905e-05
4,349	Class-based graph anonymization for social network data	2009	VLDB	6.2647606e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,633	Injecting Utility into Anonymized Datasets	2006	SIGMOD	0.00011060784
6,235	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD	5.1451658e-05
13,407	Privacy Preserving Social Graphs for High Precision Community Detection	2014	SIGMOD	-
5,351	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	5.5531181e-05
12,312	Anonymized Data: Generation, Models, Usage	2009	SIGMOD	4.1945683e-05
2,718	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.2409647e-05
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
4,349	Class-based graph anonymization for social network data	2009	VLDB	6.2647606e-05
803	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016478924