On Your Social Network De-anonymizablity: Quantification and Large Scale Evaluation with Seed Knowledge

Abstract—In this paper, we conduct the first comprehensive quantification on the perfect de-anonymizability and partial de-anonymizability of real world social networks with seed in-formation in general scenarios, where a social network can follow an arbitrary distribution model. This quantification pro-vides the theoretical foundation for existing structure based de-anonymization attacks (e.g., [1][2][3]) and closes the gap between de-anonymization practice and theory. Besides that, our quantification can serve as a testing-stone for the effectiveness of anonymization techniques, i.e., researchers can employ our quantified structural conditions to evaluate the potential de-anonymizability of the anonymized social networks. Based on our quantification, we conduct a large scale evaluation on the de-anonymizability of 24 various real world social networks by quantitatively showing: 1) the conditions for perfect and (1 ϵ) de-anonymization of a social network, where ϵ specifies the tolerated de-anonymization error, and 2) the number of users of a social network that can be successfully de-anonymized. Fur-thermore, we show that, both theoretically and experimentally, the overall structural information based de-anonymization attack is much more powerful than the seed knowledge-only based de-anonymization attack, and even without any seed information, a social network can be perfectly or partially de-anonymized. Finally, we discuss the implications of this work. Our findings are expected to shed light on the future research in the structural data anonymization and de-anonymization area, and to help data owners evaluate their structural data vulnerability before data sharing and publishing. I