Structural Data De-Anonymization: Theory and Practice

In this paper, we study the quantification, practice, and implications of structural data de-anonymization, including social data, mobility traces, and so on. First, we answer several open questions in structural data de-anonymization by quantifying perfect and $1-\epsilon $ -perfect structural data de-anonymization, where $\epsilon $ is the error tolerated by a de-anonymization scheme. To the best of our knowledge, this is the first work on quantifying structural data de-anonymization under a general data model, which closes the gap between the structural data de-anonymization practice and theory. Second, we conduct the first large-scale study on the de-anonymizability of 26 real world structural data sets, including social networks, collaborations networks, communication networks, autonomous systems, peer-to-peer networks, and so on. We also quantitatively show the perfect and $1-\epsilon $ -perfect de-anonymization conditions of the 26 data sets. Third, following our quantification, we present a practical attack [a novel single-phase cold start optimization-based de-anonymization ODA algorithm]. An experimental analysis of ODA shows that $\sim 77.7$ %–83.3% of the users in Gowalla 196 591 users and 950 327 edges and 86.9%–95.5% of the users in Google+ 4 692 671 users and 90 751 480 edges are de-anonymizable in different scenarios, which implies that the structure-based de-anonymization is powerful in practice. Finally, we discuss the implications of our de-anonymization quantification and our ODA attack and provide some general suggestions for future secure data publishing.