Injecting uncertainty in graphs for identity obfuscation

Paolo Boldi, Francesco Bonchi, Aristides Gionis, Tamir Tassa

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


Data collected nowadays by social-networking applications create fascinating opportunities for building novel services, as well as expanding our understanding about social structures and their dynamics. Unfortunately, publishing socialnetwork graphs is considered an ill-advised practice due to privacy concerns. To alleviate this problem, several anonymization methods have been proposed, aiming at reducing the risk of a privacy breach on the published data, while still allowing to analyze them and draw relevant conclusions. In this paper we introduce a new anonymization approach that is based on injecting uncertainty in social graphs and publishing the resulting uncertain graphs. While existing approaches obfuscate graph data by adding or removing edges entirely, we propose using a finer-grained perturbation that adds or removes edges partially: this way we can achieve the same desired level of obfuscation with smaller changes in the data, thus maintaining higher utility. Our experiments on real-world networks confirm that at the same level of identity obfuscation our method provides higher usefulness than existing randomized methods that publish standard graphs.

שפה מקוריתאנגלית
עמודים (מ-עד)1376-1387
מספר עמודים12
כתב עתProceedings of the VLDB Endowment
מספר גיליון11
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יולי 2012

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Injecting uncertainty in graphs for identity obfuscation'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי