Blocking adversarial influence in social networks

DOI10.1007/978-3-030-64793-3_14MaRDI QIDQ2056948zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 8 December 2021

Full work available at URL https://arxiv.org/abs/2011.01346

zbMATH Keywords

Stackelberg gameinfluence maximizationinfluence blocking

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Hierarchical games (including Stackelberg games) (91A65)

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.

Recommendations

• Negative influence blocking maximization with uncertain sources under the independent cascade model
• Information diffusion blocking model of node influence-oriented in online social network
• Influence maximization in social networks with privacy protection
• Community-based rumor blocking maximization in social networks
• Influence Maximization in Social Networks
• Community-based rumor blocking maximization in social networks: algorithms and analysis

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Collective dynamics of `small-world' networks
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Machine Learning: ECML 2004

Cited in

(7)

• Detecting organization-targeted socialbots by monitoring social network profiles
• Game theory on attack graph for cyber deception
• Detecting bots and assessing their impact in social networks
• Identifying structural hole spanners to maximally block information propagation
• Negative influence blocking maximization with uncertain sources under the independent cascade model
• Defending against fake VIP in scant-transparency information systems with QoS differentiation
• Maximizing convergence time in network averaging dynamics subject to edge removal

This page was built for publication: Blocking adversarial influence in social networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056948)