Blocking Adversarial Influence in Social Networks

Feiran Jia, Kai Zhou, Charles Kamhoua, Yevgeniy Vorobeychik

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

While social networks are widely used as a media for information diffusion, attackers can also strategically employ analytical tools, such as influence maximization, to maximize the spread of adversarial content through the networks. We investigate the problem of limiting the diffusion of negative information by blocking nodes and edges in the network. We formulate the interaction between the defender and the attacker as a Stackelberg game where the defender first chooses a set of nodes to block and then the attacker selects a set of seeds to spread negative information from. This yields an extremely complex bi-level optimization problem, particularly since even the standard influence measures are difficult to compute. Our approach is to approximate the attacker’s problem as the maximum node domination problem. To solve this problem, we first develop a method based on integer programming combined with constraint generation. Next, to improve scalability, we develop an approximate solution method that represents the attacker’s problem as an integer program, and then combines relaxation with duality to yield an upper bound on the defender’s objective that can be computed using mixed integer linear programming. Finally, we propose an even more scalable heuristic method that prunes nodes from the consideration set based on their degree. Extensive experiments demonstrate the efficacy of our approaches.

Original languageEnglish
Title of host publicationDecision and Game Theory for Security - 11th International Conference, GameSec 2020, Proceedings
EditorsQuanyan Zhu, John S. Baras, Radha Poovendran, Juntao Chen
PublisherSpringer Science and Business Media Deutschland GmbH
Pages257-276
Number of pages20
ISBN (Print)9783030647926
DOIs
Publication statusPublished - 2020
Externally publishedYes
Event11th Conference on Decision and Game Theory for Security, GameSec 2020 - College Park, United States
Duration: 28 Oct 202030 Oct 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12513 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th Conference on Decision and Game Theory for Security, GameSec 2020
Country/TerritoryUnited States
CityCollege Park
Period28/10/2030/10/20

Keywords

  • Influence blocking
  • Influence maximization
  • Stackelberg game

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this