Strategic Evasion of Centrality Measures

Among the most fundamental tools for social network analysis are centrality measures, which are designed to rank nodes according to various criteria. Similarly to other tools, they were built around the assumption that individuals in the network do not act strategically to evade analysis. Even the centrality analysis of covert networks typically assumes that the investigated network is not strategically manipulated. To circumvent this problem, a recent study of Waniek et al. attempted to understand how a member of a social network could try to mislead centrality measures. Their model, however, is based on the assumption that the network analyser (the seeker) is oblivious to any evasion attempts by the leaders of the network (the evaders). In this paper, we present the first analysis of a strategic game between the seeker and the evader drawing conclusions on which centralities to use best in such situations.