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
h40e704d6027d7b5c
Venue
VLDB
Year
2012
Pagerank
7.731521e-05
Overall Rank
3,036 | 79.59%
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,632 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 7.1494448e-05
3,820 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 7.005206e-05
5,754 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 6.0058421e-05
5,951 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.9366845e-05
6,161 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.8647415e-05
6,475 Clustering Uncertain Graphs 2018 VLDB 5.7736095e-05
9,240 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 5.2056825e-05
9,840 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.1230858e-05
10,132 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 5.0751052e-05
11,770 Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem 2023 VLDB 4.9793485e-05
12,294 Efficient Computation of Feedback Arc Set at Web-Scale 2017 VLDB 4.9793485e-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
347 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.00020325683
1,008 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00012551244
1,063 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012208695
1,260 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.00011296964
1,367 Resisting Structural Re-identification in Anonymized Social Networks 2008 VLDB 0.00010911008
2,486 Anonymizing Bipartite Graph Data using Safe Groupings 2008 VLDB 8.3991285e-05
2,963 K-Automorphism: A General Framework for Privacy Preserving Network Publication 2009 VLDB 7.8060151e-05
4,210 Class-based graph anonymization for social network data 2009 VLDB 6.7332571e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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