.png){kind=icon}
.png){kind=icon}
Return
Optimizing the Weight Stable Set Attack With Budget Constraint
.png){kind=icon}
PRE
AI
R
W
DOI：10.1109/tdsc.2026.3692750.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Identifying the most influential communicators as an issue of maximizing influence has become one of the most notable topics in social network analysis, as it has achieved success in viral marketing. Only by understanding our opponent’s way of thinking can we effectively defend against or attack them. We particularly focus on one type of such attacks called the weight stable set attack problem with budget constraint. Given a social network, each node has a weight and removal cost. This problem is to remove a subset of the nodes whose total removal cost does not exceed a given threshold, such that the maximum weight stable set in the resulting graph is minimized. We first propose a 2<inline-formula><tex-math notation="LaTeX">$\alpha$</tex-math></inline-formula>-approximation algorithm for this problem on the graph without odd cycles, where <inline-formula><tex-math notation="LaTeX">$\alpha$</tex-math></inline-formula> is the approximation ratio for the algorithm of the minimum knapsack problem. Interestingly, this algorithm can be extended to general graphs. We also design a genetic algorithm for general graphs. Finally, we conducted many experiments on both artificial networks and real-world networks. For the graph without odd cycles, the results show that our performance ratio is less than 1.21. For general graphs, we compare the algorithm that extends the idea of graphs without odd cycles with the genetic algorithm. The results show that this algorithm is better than the genetic algorithm in some settings.<sup>1</sup>
Keywords:
Stable set
approximation algorithm
bipartite graph
node attack
interdiction
Journal
IF:
7.5
Papers:
2.4K
Citations:
9.6K
Organization
Cited Papers