Hiding From Centrality Measures: A Stackelberg Game Perspective

Marcin Waniek, Jan Woznica, Kai Zhou, Yevgeniy Vorobeychik, Tomasz P. Michalak, Talal Rahwan

Research output: Contribution to journalArticlepeer-review

Abstract

Centrality measures can rank nodes in a social network according to their importance. However, in many cases, a node may want to avoid being highly ranked by such measures, e.g., as is the case with terrorist networks. In this work, we study a confrontation between the seeker - the party analyzing a social network using centrality measures - and the evader - a node attempting to decrease its ranking according to such measures. We analyze the possible outcomes of modifying, i.e., adding or removing, a single edge by the evader, showing that even without complete knowledge about the network, the effects of the modification on the evader's ranking can often be predicted. We study the computational complexity of finding a set of modifications that reduce the evader's centrality ranking in an optimal way, proving that these decision problems are NP-complete. Moreover, we provide a 2-approximation for the degree centrality, and logarithmic approximation boundaries for the closeness and betweenness centralities. Finally, we define and investigate a Stackelberg game between the seeker and the evader, providing a Mixed Integer Linear Programming formulation of finding an equilibrium. Altogether, we provide a thorough analysis of the strategic aspects of hiding from centrality measures in social networks.

Original languageEnglish (US)
Pages (from-to)10058-10071
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume35
Issue number10
DOIs
StatePublished - Oct 1 2023

Keywords

  • Centrality measure
  • Stackelberg game
  • complexity analysis
  • social network

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Hiding From Centrality Measures: A Stackelberg Game Perspective'. Together they form a unique fingerprint.

Cite this