DBScholar

Back to papers

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
10562
Venue
VLDB
Year
2012
Pagerank
7.9035901e-05
Overall Rank
2,977 | 79.58%
DOI
10.14778/2350229.2350240

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{boldi_vldb12,
        title = {{Injecting Uncertainty in Graphs for Identity Obfuscation}},
        author = {Boldi, Paolo and Bonchi, Francesco and Gionis, Aristides and Tassa, Tamir},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {11},
        pages = {1376--1387},
        doi = {10.14778/2350229.2350240},
        url = {https://doi.org/10.14778/2350229.2350240},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
3,559 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 7.3095916e-05
3,738 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 7.1602939e-05
5,889 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 6.0496722e-05
5,890 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 6.0496722e-05
6,037 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.9990983e-05
6,345 Clustering Uncertain Graphs 2018 VLDB 5.9059861e-05
9,062 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 5.3251649e-05
9,665 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.2406724e-05
9,948 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 5.1915905e-05
11,458 Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem 2023 VLDB 5.093636e-05
11,997 Efficient Computation of Feedback Arc Set at Web-Scale 2017 VLDB 5.093636e-05
Previous Page 1 / 1 Next

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
338 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.00020731054
985 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00012818114
1,049 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012415522
1,254 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.0001147266
1,326 Resisting Structural Re-identification in Anonymized Social Networks 2008 VLDB 0.00011145219
2,430 Anonymizing Bipartite Graph Data using Safe Groupings 2008 VLDB 8.5885381e-05
2,909 K-Automorphism: A General Framework for Privacy Preserving Network Publication 2009 VLDB 7.9708764e-05
4,125 Class-based graph anonymization for social network data 2009 VLDB 6.886347e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,669 Injecting Utility into Anonymized Datasets 2006 SIGMOD
2 6,083 Global and Local Differentially Private Release of Count-Weighted Graphs 2023 SIGMOD
3 13,608 Privacy Preserving Social Graphs for High Precision Community Detection 2014 SIGMOD
4 5,227 K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks 2010 SIGMOD
5 12,506 Anonymized Data: Generation, Models, Usage 2009 SIGMOD
6 2,430 Anonymizing Bipartite Graph Data using Safe Groupings 2008 VLDB
7 6,288 Publishing Attributed Social Graphs with Formal Privacy Guarantees 2016 SIGMOD
8 1,326 Resisting Structural Re-identification in Anonymized Social Networks 2008 VLDB
9 4,125 Class-based graph anonymization for social network data 2009 VLDB
10 985 Towards Identity Anonymization on Graphs 2008 SIGMOD