Analysis of Grasshopper, a Novel Social Network De-anonymization Algorithm

Authors

  • Benedek Simon
  • Gábor György Gulyás
    Affiliation

    Laboratory of Cryptography and Systems Security (CrySyS), Dept. of Networked Systems and Services, BME

  • Sándor Imre
https://doi.org/10.3311/PPee.7878

Abstract

Social networks have an important and possibly key role in our society today. In addition to the benefits, serious privacy concerns also emerge: there are algorithms called de-anonymization attacks that are capable of re-identifying large fractions of anonymously published networks. A strong class of these attacks solely use the network structure to achieve their goals. In this paper we propose a novel structural de-anonymization attack called Grasshopper. By measurements we compare Grasshopper to the state-of-the-art algorithm, and highlight its enhanced capabilities, such as having negligible error rates and accessing yield levels that was not possible before: in cases when there is greater noise in the background knowledge. We furthermore evaluate an anonymity measure for the Grasshopper algorithm which enables the approximate ranking of nodes according to their re-identification rates. Finally, we characterize the robustness of Grasshopper in tackling identity separation, a privacy-enhancing technique that facilitate hiding of structural information.

Keywords:

social network, privacy, de-anonymization

Published Online

2015-02-11

How to Cite

Simon, B., Gulyás, G. G., Imre, S. Analysis of Grasshopper, a Novel Social Network De-anonymization Algorithm, Periodica Polytechnica Electrical Engineering, Computer Science, 58(4), pp. 161–173, 2014. https://doi.org/10.3311/PPee.7878

Issue

Section

Articles