TY - GEN
T1 - Hiding in multilayer networks
AU - Waniek, Marcin
AU - Michalak, Tomasz P.
AU - Rahwan, Talal
N1 - Funding Information:
Marcin Waniek was supported by the Polish National Science Centre grant 2015/17/N/ST6/03686. Tomasz Michalak was supported by the Polish National Science Centre grant 2016/23/B/ST6/03599.
Publisher Copyright:
Copyright © 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2020
Y1 - 2020
N2 - Multilayer networks allow for modeling complex relationships, where individuals are embedded in multiple social networks at the same time. Given the ubiquity of such relationships, these networks have been increasingly gaining attention in the literature. This paper presents the first analysis of the robustness of centrality measures against strategic manipulation in multilayer networks. More specifically, we consider an “evader” who strategically chooses which connections to form in a multilayer network in order to obtain a low centrality-based ranking—thereby reducing the chance of being highlighted as a key figure in the network—while ensuring that she remains connected to a certain group of people. We prove that determining an optimal way to “hide” is NP-complete and hard to approximate for most centrality measures considered in our study. Moreover, we empirically evaluate a number of heuristics that the evader can use. Our results suggest that the centrality measures that are functions of the entire network topology are more robust to such a strategic evader than their counterparts which consider each layer separately.
AB - Multilayer networks allow for modeling complex relationships, where individuals are embedded in multiple social networks at the same time. Given the ubiquity of such relationships, these networks have been increasingly gaining attention in the literature. This paper presents the first analysis of the robustness of centrality measures against strategic manipulation in multilayer networks. More specifically, we consider an “evader” who strategically chooses which connections to form in a multilayer network in order to obtain a low centrality-based ranking—thereby reducing the chance of being highlighted as a key figure in the network—while ensuring that she remains connected to a certain group of people. We prove that determining an optimal way to “hide” is NP-complete and hard to approximate for most centrality measures considered in our study. Moreover, we empirically evaluate a number of heuristics that the evader can use. Our results suggest that the centrality measures that are functions of the entire network topology are more robust to such a strategic evader than their counterparts which consider each layer separately.
UR - http://www.scopus.com/inward/record.url?scp=85102225414&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102225414&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85102225414
T3 - AAAI 2020 - 34th AAAI Conference on Artificial Intelligence
SP - 1021
EP - 1028
BT - AAAI 2020 - 34th AAAI Conference on Artificial Intelligence
PB - AAAI press
T2 - 34th AAAI Conference on Artificial Intelligence, AAAI 2020
Y2 - 7 February 2020 through 12 February 2020
ER -