How to Hide One's Relationships from Link Prediction Algorithms Articles uri icon

authors

  • Waniek, Marcin
  • Zhou, Kai
  • Vorobeychik, Yevgeniy
  • MORO EGIDO, ESTEBAN
  • Michalak, Tomasz P.
  • Rahwan, Talal

publication date

  • August 2019

issue

  • 1

volume

  • 9

International Standard Serial Number (ISSN)

  • 2045-2322

abstract

  • Our private connections can be exposed by link prediction algorithms. To date, this threat has only
    been addressed from the perspective of a central authority, completely neglecting the possibility
    that members of the social network can themselves mitigate such threats. We fill this gap by studying
    how an individual can rewire her own network neighborhood to hide her sensitive relationships. We
    prove that the optimization problem faced by such an individual is NP-complete, meaning that any
    attempt to identify an optimal way to hide one"s relationships is futile. Based on this, we shift our
    attention towards developing effective, albeit not optimal, heuristics that are readily-applicable by
    users of existing social media platforms to conceal any connections they deem sensitive. Our empirical
    evaluation reveals that it is more beneficial to focus on 'unfriending” carefully-chosen individuals rather
    than befriending new ones. In fact, by avoiding communication with just 5 individuals, it is possible for
    one to hide some of her relationships in a massive, real-life telecommunication network, consisting
    of 829,725 phone calls between 248,763 individuals. Our analysis also shows that link prediction
    algorithms are more susceptible to manipulation in smaller and denser networks. Evaluating the error
    vs. attack tolerance of link prediction algorithms reveals that rewiring connections randomly may end
    up exposing one"s sensitive relationships, highlighting the importance of the strategic aspect. In an age
    where personal relationships continue to leave digital traces, our results empower the general public to
    proactively protect their private relationships.

subjects

  • Mathematics