  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.
