Hiding From Centrality Measures: A Stackelberg Game Perspective

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

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
Pages (from-to)1-14
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
DOIs
Publication statusAccepted/In press - 17 Apr 2023

Keywords

  • Centrality measure
  • complexity analysis
  • Computational complexity
  • Games
  • Image edge detection
  • Internet
  • Privacy
  • social network
  • Social networking (online)
  • stackelberg game
  • Terrorism

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