On the relative de-anonymizability of graph data: Quantification and evaluation

In this paper, we propose a structural importance-aware approach to quantify the vulnerability/de-anonymizability of graph data to structure-based De-Anonymization (DA) attacks [1][2][3][4]. Specifically, we quantify both the seed-based and the seed-free Relative De-anonymizability (RD) of graph data for both perfect DA (successfully de-anonymizing all the target users) and partial DA (where some DA error is tolerated) under a general data model. In our relative quantification, instead of treating all the users in graph data as structurally equivalent, we adaptively quantify their RD in terms of their structural importance. Leveraging 15 real world graph datasets, we validate the accuracy of our relative quantifications and compare them with state-of-the-art seed-based and seed-free quantification techniques. The results demonstrate that our structural importance-aware relative quantifications are more sound and precise when measuring graph data's real vulnerability/de-anonymizability.