TY - JOUR
T1 - Hiding individuals and communities in a social network
AU - Waniek, Marcin
AU - Michalak, Tomasz P.
AU - Wooldridge, Michael J.
AU - Rahwan, Talal
N1 - Publisher Copyright:
© 2017 The Author(s).
PY - 2018/2/1
Y1 - 2018/2/1
N2 - The Internet and social media have fuelled enormous interest in social network analysis. New tools continue to be developed and used to analyse our personal connections, with particular emphasis on detecting communities or identifying key individuals in a social network. This raises privacy concerns that are likely to exacerbate in the future. With this in mind, we ask the question 'Can individuals or groups actively manage their connections to evade social network analysis tools?' By addressing this question, the general public may better protect their privacy, oppressed activist groups may better conceal their existence and security agencies may better understand how terrorists escape detection. We first study how an individual can evade 'node centrality' analysis while minimizing the negative impact that this may have on his or her influence. We prove that an optimal solution to this problem is difficult to compute. Despite this hardness, we demonstrate how even a simple heuristic, whereby attention is restricted to the individual's immediate neighbourhood, can be surprisingly effective in practice; for example, it could easily disguise Mohamed Atta's leading position within the World Trade Center terrorist network. We also study how a community can increase the likelihood of being overlooked by community-detection algorithms. We propose a measure of concealment-expressing how well a community is hidden-and use it to demonstrate the effectiveness of a simple heuristic, whereby members of the community either 'unfriend' certain other members or 'befriend' some non-members in a coordinated effort to camouflage their community.
AB - The Internet and social media have fuelled enormous interest in social network analysis. New tools continue to be developed and used to analyse our personal connections, with particular emphasis on detecting communities or identifying key individuals in a social network. This raises privacy concerns that are likely to exacerbate in the future. With this in mind, we ask the question 'Can individuals or groups actively manage their connections to evade social network analysis tools?' By addressing this question, the general public may better protect their privacy, oppressed activist groups may better conceal their existence and security agencies may better understand how terrorists escape detection. We first study how an individual can evade 'node centrality' analysis while minimizing the negative impact that this may have on his or her influence. We prove that an optimal solution to this problem is difficult to compute. Despite this hardness, we demonstrate how even a simple heuristic, whereby attention is restricted to the individual's immediate neighbourhood, can be surprisingly effective in practice; for example, it could easily disguise Mohamed Atta's leading position within the World Trade Center terrorist network. We also study how a community can increase the likelihood of being overlooked by community-detection algorithms. We propose a measure of concealment-expressing how well a community is hidden-and use it to demonstrate the effectiveness of a simple heuristic, whereby members of the community either 'unfriend' certain other members or 'befriend' some non-members in a coordinated effort to camouflage their community.
UR - http://www.scopus.com/inward/record.url?scp=85042772086&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85042772086&partnerID=8YFLogxK
U2 - 10.1038/s41562-017-0290-3
DO - 10.1038/s41562-017-0290-3
M3 - Article
AN - SCOPUS:85042772086
SN - 2397-3374
VL - 2
SP - 139
EP - 147
JO - Nature human behaviour
JF - Nature human behaviour
IS - 2
ER -