TY - GEN
T1 - Strategic evasion of centrality measures
AU - Waniek, Marcin
AU - Woznica, Jan
AU - Zhou, Kai
AU - Vorobeychik, Yevgeniy
AU - Rahwan, Talal
AU - Michalak, Tomasz P.
N1 - Funding Information:
Tomasz Michalak was supported by the Polish National Science Centre (grant 2016/23/B/ST6/03599). Yevgeniy Vorobeychik was supported by the National Science Foundation (IIS-1903207, IIS-1905558) and Army Research Office (MURI W911NF1810208). Kai Zhou was supported by PolyU (UGC) Internal Fund (1-BE3U). For an earlier version of this work, Marcin Waniek was supported by the Polish National Science Centre (grant 2015/17/N/ST6/03686).
Publisher Copyright:
© 2021 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2021
Y1 - 2021
N2 - Among the most fundamental tools for social network analysis are centrality measures, which quantify the importance of every node in the network. This centrality analysis typically disregards the possibility that the network may have been deliberately manipulated to mislead the analysis. To solve this problem, a recent study attempted to understand how a member of a social network could rewire the connections therein to avoid being identified as a leader of that network. However, the study was based on the assumption that the network analyzer - the seeker - is oblivious to any evasion attempts by the evader. In this paper, we relax this assumption by modelling the seeker and evader as strategic players in a Bayesian Stackelberg game. In this context, we study the complexity of various optimization problems, and analyze the equilibria of the game under different assumptions, thereby drawing the first conclusions in the literature regarding which centralities the seeker should use to maximize the chances of detecting a strategic evader.
AB - Among the most fundamental tools for social network analysis are centrality measures, which quantify the importance of every node in the network. This centrality analysis typically disregards the possibility that the network may have been deliberately manipulated to mislead the analysis. To solve this problem, a recent study attempted to understand how a member of a social network could rewire the connections therein to avoid being identified as a leader of that network. However, the study was based on the assumption that the network analyzer - the seeker - is oblivious to any evasion attempts by the evader. In this paper, we relax this assumption by modelling the seeker and evader as strategic players in a Bayesian Stackelberg game. In this context, we study the complexity of various optimization problems, and analyze the equilibria of the game under different assumptions, thereby drawing the first conclusions in the literature regarding which centralities the seeker should use to maximize the chances of detecting a strategic evader.
KW - Centrality Measure
KW - Computational Complexity
KW - Social Network
KW - Stackelberg Game
UR - http://www.scopus.com/inward/record.url?scp=85112108925&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85112108925&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85112108925
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 1377
EP - 1385
BT - 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021
Y2 - 3 May 2021 through 7 May 2021
ER -