Efficient Algorithm for Privacy Breach in Anonymized Social Networks

• Pamela Tabak UFRJ
• Daniel Ratton Figueiredo UFRJ

DOI: https://doi.org/10.5753/etc.2018.3137

Abstract

Companies that control social networks often release data, including the users’ relationship network, removing their identity to preserve their privacy. This work defines and evaluates a two-step methodology to reveal relationships between users of a social network. In the first phase, artificial nodes (users) are inserted and connected to a set of victim users. The second phase identifies the artificial nodes in the anonymized network and reveals relationships between the victim users. The algorithms were implemented and the results indicate that they are effective in revealing relationships between victims, breaking their privacy.

References

Backstrom, L., Dwork, C., and Kleinberg, J. (2007). Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography. In Proc. of Intern. Conf. WWW.

Hay, M., Miklau, G., Jensen, D., Towsley, D., and Weis, P. (2008). Resisting structural re-identification in anonymized social networks. Proc. VLDB Endow., 1(1):102–114.

Leskovec, J. and Krevl, A. (2018). SNAP Datasets: Stanford large network dataset collection.