在线社交网络虚假信息交互量最小化的边阻断策略研究

在线社交媒体的蓬勃发展改变了人们获取信息的模式，大量的信息通过社交平台传播，信息内容的真实性把关弱化，各类虚假信息依托社交媒体野蛮生长，网络空间治理，培育健康的网络生态意义重大。本文通过最小化用户之间的虚假信息交互量，研究社交网络中虚假信息传播路径的阻断策略。给定在线社交网络G=（V，E，P，H），H表示用户之间信息交互量，已知虚假信息传播源集合S?V，虚假信息交互量最小化问题是从E中选取哪K条边，使得这些边被阻断之后，虚假信息在用户之间的交互总量最小。首先证明了该问题是NP-困难的，进而证明了问题的目标函数计算是#P-困难。其次，证明了该问题目标函数既不是次模函数也不是超模函数。再次，提出了两阶段贪婪算法（TSGA）来解决该问题，即先获取候选集合E^sa，然后选取阻断集合E'。最后，通过实际在线社交网络数据对模型和算法的有效性进行了分析，实验表明本文提出的算法比现有算法更加有效。

Disinformation Diffusion Activity Minimization by Edge Blocking in Online Social Networks

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.