How to Hide One’s Relationships from Link Prediction Algorithms
How to Hide One’s Relationships from Link Prediction Algorithms
复制标题
DOI：
10.1038/s41598-019-48583-6
复制
发表时间：
2019-08
影响因子：
4.6
通讯作者：
Marcin Waniek;Kai Zhou;Yevgeniy Vorobeychik;E. Moro;Tomasz P. Michalak;Talal Rahwan
中科院分区：
文献类型：
--
作者：
Marcin Waniek;Kai Zhou;Yevgeniy Vorobeychik;E. Moro;Tomasz P. Michalak;Talal Rahwan
我们的私人连接可能会被链接预测算法暴露。到目前为止，这种威胁只从中央权威的角度来解决，完全忽视了社交网络成员自己可以减轻这种威胁的可能性。我们通过研究一个人如何重新连接她自己的网络邻居来隐藏她的敏感关系来填补这个空白。我们证明了这样一个人所面临的优化问题是NP完全的，这意味着任何试图找出一个最佳的方式来隐藏自己的关系是徒劳的。基于此，我们将注意力转移到开发有效的（尽管不是最佳的）隐藏技术上，这些技术可以被现有社交媒体平台的用户轻松应用，以隐藏他们认为敏感的任何联系。我们的实证评估显示，专注于“不友好”精心挑选的个体比结交新朋友更有益。事实上，通过避免与5个人通信，一个人可以将她的一些关系隐藏在一个庞大的现实生活中的电信网络中，该网络由248，763个人之间的829，725个电话组成。我们的分析还表明，链接预测算法更容易在更小和更密集的网络中被操纵。评估链接预测算法的错误与攻击容忍度表明，随机重新连接可能最终暴露一个人的敏感关系，突出了战略方面的重要性。在个人关系继续留下数字痕迹的时代，我们的研究结果使公众能够积极保护他们的私人关系。
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.