关键词: 社交网络, 虚假信息交互量, TSGA算法, 边阻断策略

Abstract: The vigorous development of online social media has changed the mode of people's access to information. A large amount of information is spread through social platforms, the authenticity of information content is weakened, all kinds of misinformation rely on social media to grow savagely, cyberspace governance, and the cultivation of healthy network ecology is of great significance. The blocking strategy of the misinformation propagation path in social networks is studied by minimizing the amount of misinformation interaction between users, that is, the set E' containing K edges is identified and blocked from the original network, so that the total amount of misinformation interaction between users after blocking is minimized. Given an acyclic social network G=(V,E,P,H), where V represents the user set (node set), e_uv∈E represents the relationship between users (edge set), h_uv∈H represents the amount of information interaction between users u and v, and p_uv∈P represents the probability that user u independently propagates misinformation to influence neighbor v. Given the information propagation model Independent Cascade model, the misinformation propagation source set S⊆V and the positive integer parameter K, the problem of minimizing the interaction of misinformation on the online social network is to find and block the set containing K edges from the edge set E so as to minimize the total amount of misinformation interaction between users, that is, the smallest f(E')=${\Sigma _{u \in V,v \in N_{E/E'}^{out}(u)}}$h_uvψ_E\E'(u), where ψ_E\E'(u) represents the probability that node u is successfully influenced by S in topology network E\E', and $N_{E/E'}^{out}(u)$ represents the set of child neighbor nodes of u in topology network E\E'. Firstly, it is proved that the problem is NP-hard, which proves that the objective function calculation of the problem is #P-hard. Secondly, it is proved that the objective function of the problem is neither submodular function nor a super-modular function. Thirdly, a two-stage heuristic algorithm (TSGA) is proposed to solve the problem by first obtaining candidate sets E^sa and then selecting blocking sets E'. In order to evaluate our proposed TSGA algorithm, it is compared with the heuristic greedy methods (KED and OD) currently popular in the field of social network, using two influence probabilities P=0.5 and P=EEI in the CGSCol, PClimate and Higgs datasets carry out simulation experiments. Experiments show that under different datasets, different influence probabilities and different evaluation indicators, it is found that the proposed TSGA is superior to other existing algorithms.

Key words: social network, disinformation diffusion activity, TSGA, edge blocking strategy