Hiding From Centrality Measures: A Stackelberg Game Perspective

Marcin Waniek, Jan Woznica, Kai Zhou, Yevgeniy Vorobeychik, Tomasz P. Michalak, Talal RahwanIEEE TKDE 2023 · OpenReview

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.

Introduction

Centrality measures such as Degree, Closeness, and Betweenness are fundamental tools for identifying influential nodes within a network. While these measures are often employed for positive ends, such as identifying key influencers in marketing, they are also utilized by law enforcement to disrupt criminal or terrorist organizations. Conversely, individuals in sensitive contexts, such as activists in authoritarian regimes, may seek to evade such detection. This paper explores the strategic "cat-and-mouse" game between a seeker, who employs centrality measures to identify important nodes, and an evader, who strategically modifies their connections to remain hidden.

The research addresses three primary questions:

  1. Predictability: Can an evader anticipate the impact of local network changes on their rank without global knowledge?
  2. Complexity: What is the computational difficulty of finding an optimal set of modifications to minimize centrality?
  3. Equilibrium: How do the seeker and evader interact when both act strategically in a game-theoretic framework?

Methodology and Sensitivity Analysis

The authors categorize network edges relative to the evader into three classes: $\zeta_1$ (incident to the evader), $\zeta_2$ (between the evader's neighbors), and $\zeta_3$ (the remainder of the network). Through sensitivity analysis, they demonstrate that even with limited local knowledge, an evader can reliably predict rank changes. For instance, removing a $\zeta_1$ edge or adding a $\zeta_2$ edge almost universally decreases the evader's rank across major centrality measures.

Illustration of network transformation from graph $G$ to $H$, used in the computational complexity analysis.

Computational Complexity

The study defines the Local Hiding problem: identifying a set of edge modifications within a fixed budget to drop the evader's rank below a safety threshold $\delta$. Using reductions from the $k$-Clique problem, the authors prove that this problem is NP-complete for Degree centrality. Furthermore, they establish that while Degree centrality allows for a 2-approximation, Closeness and Betweenness centralities are significantly more resilient to optimal manipulation, lacking approximation within logarithmic boundaries.

The Hiding Trade-off

Hiding is not without cost. An evader typically wishes to maintain some level of influence within the network while lowering their visibility. The authors model this via a utility function that balances rank reduction with influence maintenance (using Independent Cascade and Linear Threshold models).

Utility functions for ranking ($U_e^R$) and influence ($U_e^I$) used to model the evader's trade-off.

Empirical results show that for massive networks (up to 100,000 nodes), the ROAM (Remove One, Add Many) heuristic is a highly effective practical strategy. It allows evaders to significantly improve their utility compared to simple edge removal by strategically adding edges elsewhere to dilute their own relative importance.

Stackelberg Game Modeling

The interaction is formalized as a Stackelberg game where the seeker (leader) selects a centrality measure and the evader (follower) responds by modifying the network. This confrontation is formulated as a Mixed-Integer Quadratic Program (MIQP) and subsequently linearized into a Mixed-Integer Linear Program (MILP) for computational efficiency.

Key insights from the equilibrium analysis include:

  • Seeker Strategy: The optimal seeker strategy often involves a mixed strategy, using different centrality measures with varying probabilities depending on the network topology.
  • Evader Strategy: Evaders who prioritize rank reduction over influence (higher $\phi$ values) achieve greater expected utility, suggesting that "going dark" is often more effective than attempting to remain influential while hiding.

Conclusion

This work provides a comprehensive analysis of the strategic landscape of hiding from centrality measures. While finding optimal hiding strategies is computationally hard, simple heuristics and local knowledge can be remarkably effective. Future research directions include extending the model to group-based hiding and exploring dynamic, temporal network environments where hiding strategies must evolve over time.

Summary updated

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.
BibTeX
@article{waniek2023hiding,
  author = {Marcin Waniek and Jan Woznica and Kai Zhou and Yevgeniy Vorobeychik and Tomasz P. Michalak and Talal Rahwan},
  title = {{Hiding From Centrality Measures: A Stackelberg Game Perspective}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  url = {https://openreview.net/forum?id=zeDTld43b6},
}
Figure