摘要：在线社交网络中的信息影响人们的观点与判断，混杂其中的虚假信息易误导决策，甚至引发非理性或激进行为。用户对虚假信息的关注度越高，受误导的概率越大。为构建和谐网络生态，本文探索点阻塞策略下虚假信息关注度最小化问题，目标是最小化被虚假信息激活用户的总关注度。首先，结合用户关注度构建关注度级联模型，借助库伦定律刻画虚假信息扩散过程中用户关注度的演化;其次，证明该问题为NP-难，且目标集函数既非次模性也非超模性;然后，将关注度最小化问题等价转化为关注度下降最大化问题，利用离散函数连续化技术及集函数凹闭合函数设计近似投影次梯度算法;最后，在YouTube、Facebook、Digg三个真实数据集上验证模型与算法有效性。实验结果表明，所提算法优于现存启发式算法，且用户对虚假信息的关注度是影响虚假信息治理的关键因素。
关键词：虚假信息;关注度;点阻塞;Lovász扩展;近似投影次梯度
论文《在线社交网络中点阻塞策略下虚假信息关注度最小化研究》发表在《计算机学报》，版权归《计算机学报》所有。本文来自网络平台，仅供参考。
Abstract：Information in online social networks influences people’s views and opinions, and misinformation mixed in is bound to mislead people’s judgment and decision-making, even triggering irrational or aggressive behaviors. The higher the attention users pay to misinformation, the more likely they are to be misled. To build a harmonious network ecological environment, this paper explores the problem of minimizing misinformation attention under the node blocking strategy, aiming to minimize the total attention of users activated by misinformation. Firstly, an attention cascade model is constructed considering users’ attention to misinformation, and Coulomb’s theorem is used to characterize the evolution of users’ attention during misinformation diffusion. Secondly, the NP-hardness of the problem is proven, and the objective set function is verified to be non-submodular and non-supermodular. Then, the attention minimization problem is equivalently transformed into the attention reduction maximization problem, and an approximate projected subgradient algorithm is designed using the continuousization technology of discrete functions and the concave closure function of set functions. Finally, the effectiveness of the proposed model and algorithm is verified on three real datasets (YouTube, Facebook, Digg). Experimental results show that the developed algorithm outperforms existing heuristic algorithms, and users’ attention to misinformation is a key factor affecting misinformation governance.
Key words：misinformation; attention; nodes blocking; Lovász extension; approximate projected subgradient
1 引言
随着移动终端普及与媒体传播技术更新，人们获取信息的途径不断拓宽，但各类信息中混杂的虚假信息、谣言等负面内容，易误导判断、引发恐慌情绪甚至过激行为。例如，新冠疫情期间“中成药双黄连口服液可抑制新型冠状病毒”的虚假信息导致产品哄抢，日本福岛核泄漏后“吃碘盐防辐射”的谣言引发民众抢购碘盐。
研究发现，用户是否因虚假信息做出非理性行为，核心取决于对该信息的关注度——仅当虚假信息与自身利益密切相关(关注度高)时，用户才易失去理智。因此，虚假信息治理的关键不仅是减少受影响用户数量，更要降低接受虚假信息用户的总关注度。本文将该问题建模为“点阻塞策略下虚假信息关注度最小化问题”，目标是通过阻塞部分用户，使最终被虚假信息激活的用户总关注度最小。
该问题与经典虚假信息影响最小化问题存在本质区别：后者以减少受影响用户数为目标，而前者更关注用户对虚假信息的关注度，两者优化目标不同(例1可佐证)。然而，现有方法面临三大挑战：一是难以精准刻画社交网络拓扑与虚假信息扩散共同作用下用户关注度的动态演化;二是问题目标集函数非次模且非超模，缺乏高效多项式时间算法;三是目标函数精确计算为P-难。
为应对上述挑战，本文核心贡献如下：
1. 提出点阻塞策略下虚假信息关注度最小化新问题，首次通过节点阻塞干预用户对虚假信息的关注度;
2. 构建关注度级联模型，刻画用户关注度演化过程，证明问题NP-难及目标集函数的非模性;
3. 引入关注度下降值参量，等价转化问题为关注度下降最大化，基于Lovász扩展与凹闭合函数属性，设计近似投影次梯度算法;
4. 在三个真实数据集上验证模型与算法有效性，证实用户关注度对虚假信息扩散的重要影响。
1.1 相关工作
虚假信息治理研究主要分为两类：一是虚假信息检测，如基于图卷积神经网络[5]、元超边结构学习[6]等方法;二是虚假信息传播抑制，如阻塞节点/连边[10,12-13]、发布正面澄清信息[10,16]等策略。但现有抑制策略均以减少受影响用户数为目标，未考虑用户关注度。
在优化算法方面，虚假信息影响最小化问题为NP-难[17]，贪心算法需依赖目标函数的次模性/超模性，而本文问题目标集函数不满足该属性，因此需探索新方法。现有非次模集函数优化的启发式算法[11,18-19]存在解质量不稳定、依赖网络拓扑等缺陷，本文将采用连续领域技术优化非次模集函数。
此外，本文与团队前期研究[21-23]的核心区别在于：前期聚焦虚假信息交互量最小化、真相运动策略、传播范围最小化，而本文以节点阻塞为核心，优化目标为用户对虚假信息的关注度。
2 问题构建
2.1 基本定义与符号
设在线社交网络为有向图 (U(V, E))，其中 (V) 为用户集，(E) 为用户间稳固关系集。每个用户 (v in V) 具有关注度向量 (C_v = {c_v(1), cdots, c_v(n)})，(n) 为信息种类数，(c_v(d) in (0,1)) 表示用户 (v) 对第 (d) 类信息的关注度(值越大关注度越高)。可通过用户浏览日志、信息发布频率等数据获取关注度向量。
本文常用符号：虚假信息源 (S)，传播的虚假信息属于第 (d) 类;用户 (v) 的相对权威性 (Ce_v = |N(v)|)((N(v)) 为用户 (v) 的邻居集);阻塞用户集 (D);被虚假信息激活的用户集 (AC);用户 (v) 被激活时对虚假信息的关注度 (c_v^*)。
2.2 关注度级联模型
以经典独立级联模型为基础，结合用户关注度与权威性，构建关注度级联模型(Attention Cascade Model, ACM)，虚假信息扩散流程如下：
1. 初始时刻 (t=0)，虚假信息源 (S) 被激活((S_0 = S))，源用户对虚假信息的关注度 (c_v^* = 1);
2. 时刻 (t geq 1)，新激活用户 (v in S_{t-1}) 以概率 (p_{vu}(t) = frac{eta c_u^t}{1 + e^{-Ce_v}}) 尝试激活子邻居 (u)((eta>0) 为常量，(c_u^t) 为用户 (u) 时刻 (t) 对虚假信息的关注度);
3. 若 (u) 被激活，更新其关注度(见2.3节)，并加入新激活集 (S_t);
4. 重复步骤2-3，直至 (S_t = emptyset)，输出被激活用户总关注度 (AS = sum_{v in AC} c_v^*)。
2.3 用户关注度演化
用户对虚假信息的关注度随传播动态演化，本文借助库伦定律刻画：用户 (u) 接收父邻居 (v) 分享的虚假信息后，关注度变化与两者关注度乘积成正比，与关注度向量相似度(K-L散度 (D_{KL}(C_u | C_v)))成反比。
考虑多父邻居交互与无交互时关注度衰减，用户 (u) 时刻 (t+1) 的关注度更新规则如下：
- 若时刻 (t) 收到多个父邻居虚假信息(父邻居集 (M_d))：
[c_u^{t+1} = frac{c_u^t + sum_{v in M_d} frac{c_u^t cdot c_v^t}{D_{KL}(C_u | C_v)}}{1 + |M_d|}]
- 若未收到虚假信息：
[c_u^{t+1} = frac{c_u^t}{log(t + 10)}]
2.4 问题正式陈述
定义1(点阻塞策略下虚假信息关注度最小化)：给定社交网络 (U(V, E))、虚假信息源 (S)、阻塞用户数上限 (q) 及关注度级联模型，从 (V setminus S) 中选择 (|D| leq q) 的用户集 (D) 阻塞，使被激活用户总关注度期望最小：
[D^* = arg min_{D subseteq V setminus S, |D| leq q} AS(D) = arg min_{D} Eleft[sum_{v in AC_{V setminus D}} c_v^* ight]]
2.5 问题属性
定理1：点阻塞策略下虚假信息关注度最小化问题为NP-难(通过规约集合覆盖问题证明)。
定理2：目标集函数 (AS(D)) 精确计算为P-难(依赖虚假信息传播结果的P-难特性)。
定理3：(AS(D)) 非负且非递增(阻塞用户越多，总关注度不会增加)。
定理4：(AS(D)) 既非次模函数也非超模函数(通过图2反例证明)。
3 优化方法
3.1 问题等价转化
引入“关注度下降值” (h(D) = AS(emptyset) - AS(D))，表示阻塞用户集 (D) 后总关注度的减少量。原问题等价转化为：
[D^* = arg max_{D subseteq V setminus S, |D| leq q} h(D)]
(h(D)) 具有非负、非递增、非次模且非超模的属性。
3.2 集函数连续化：Lovász扩展
为将离散集函数 (h(D)) 转化为连续函数，采用Lovász扩展。对任意向量 (x in [0,1]^m)((m = |V setminus S|))，将其元素降序排列为 (x_{omega(1)} geq x_{omega(2)} geq cdots geq x_{omega(m)})，定义集合链 (Phi_1^x subseteq Phi_2^x subseteq cdots subseteq Phi_m^x)((Phi_i^x = {omega(1), cdots, omega(i)}))，则 (h(D)) 的Lovász扩展为：
[h_L(x) = sum_{i=1}^m (x_{omega(i)} - x_{omega(i+1)}) h(Phi_i^x)]
(其中 (x_{omega(m+1)} = 0))
3.3 凹松弛与近似属性
引入凹闭合函数 (h_+(cdot))(逐点最大凹函数)，并定义“弱超模性”：若存在 (chi_h in [1, +infty))，对任意 (A_1 subset A_2 subset V setminus S) 和 (u otin A_2)，有 (frac{h(A_1 cup {u}) - h(A_1)}{h(A_2 cup {u}) - h(A_2)} leq chi_h)，则 (h(D)) 为 (chi_h) 弱超模。
定理5：对任意向量 (x in [0,1]^m)，设 (K_i = h(Phi_i^x) - h(Phi_{i-1}^x))，则 (K^T x geq h(D)/chi_h)(对所有 (D subseteq V setminus S))，且 (h_L(x) = K^T x in [h_+(x)/chi_h, h_+(x)])。
该定理建立了Lovász扩展与凹闭合函数的近似关系，为后续算法设计奠定基础。
4 算法设计
4.1 关注度下降值的近似估计
由于 (h(D)) 精确计算为P-难，采用蒙特卡洛模拟估计。设 (varepsilon in [0,1])(误差)、(delta>0)(置信度)，迭代采样直至满足停止条件 (AQ geq gamma_1 = 1 + 4(e-2)(1+varepsilon)ln(2/delta)/varepsilon^2)，最终估计值 (hat{h}(D) = AQ cdot |V| / N_q)((AQ) 为采样累加值，(N_q) 为采样次数)。
4.2 近似投影次梯度算法(AppPS)
基于Lovász扩展与凹闭合函数的近似属性，设计算法流程如下：
1. 初始化：设定迭代次数 (N_t)、步长 (eta = R_r/(L cdot sqrt{N_t}))((L = AS(emptyset)) 为Lipschitz常数，(R_r = 2sqrt{m}) 为域半径)，随机选择初始向量 (x^1 in F_L = {x in [0,1]^m : |x|_1 leq q});
2. 迭代更新：对 (nt = 1, 2, cdots, N_t)，计算近似次梯度 (K^{nt})，更新 (x^{nt+1} = P_C(x^{nt} + eta cdot K^{nt}))((P_C) 为投影算子);
3. 最优解选择：选取使 (h_L(x^{nt})) 最大的向量 (x^ar{})，对应的集合 (ar{D} = Phi_{|q|}^{x^ar{}}) 即为阻塞用户集;
4. 输出：通过蒙特卡洛模拟计算 (hat{AS}(ar{D}))。
命题2：AppPS算法时间复杂度为 (O(N_t cdot N_q cdot |E|))。
5 实验验证
5.1 实验设置
- 数据集：YouTube(10K节点，49K连边)、Facebook(14K节点，87K连边)、Digg(30K节点，87K连边);
- 参数设置：虚假信息源 (|S|=100)，信息种类数 (n=8)，迭代次数 (N_t=10)，阻塞用户数 (q in {20,40,cdots,200});
- 基线算法：离散梯度下降算法(SubGt)、最大度中心性算法(MaxDe)、最大接近中心性算法(MaxCs)、最大关注度算法(MaxAn)。
5.2 算法可靠性
迭代次数 (N_t) 影响解精度：当 (N_t geq 10) 时，关注度下降率均值约为0.0039，趋于收敛，因此设定 (N_t=10)。
5.3 算法有效性
1. 关注度降低效果：AppPS算法在三个数据集上均优于基线算法，比MaxDe算法至少优11.35%(图4);
2. 传播抑制效果：AppPS算法抑制虚假信息传播的性能比SubGt算法平均优23.86%，比MaxDe算法至少优19.05%(图5);
3. 算法性能排序：AppPS > SubGt > MaxDe > MaxCs > MaxAn。
5.4 关注度的影响
1. 阻塞用户数与关注度下降值正相关;
2. 不同类型虚假信息的关注度下降值差异显著(最大相差67.89%)，且数据集间治理效率不一致;
3. 用户初始关注度向量对下降值有影响，但具有同质性(图6、7)。
6 结论
本文提出点阻塞策略下虚假信息关注度最小化新问题，构建关注度级联模型，设计近似投影次梯度算法，在三个真实数据集上验证了算法有效性。实验表明，该算法能有效降低用户对虚假信息的总关注度，且用户关注度是虚假信息治理的关键因素。未来将探索其他虚假信息治理策略(如连边阻塞、动态阻塞)对关注度的影响。
参考文献
[1] Warner E L, Basen-Engquist K M, Badger T A, et al. The online cancer nutrition misinformation: A framework of behavior change based on exposure to cancer nutrition misinformation[J]. Cancer, 2022, 128(13): 2540-2548.
[2] Shahbazi M, Bunker D. Social media trust: Fighting misinformation in the time of crisis[J]. International Journal of Information Management, 2024, 77: 102780.
[3] Jain A, Dhar J, Gupta V. Rumor model on homogeneous social network incorporating delay in expert intervention and government action[J]. Communications in Nonlinear Science and Numerical Simulation, 2020, 84: 105189.
[4] Deb N, Kollu A, Alferaidi A, et al. Suppressing the spread of fake news over the social web of things: An influence maximization-based supervised approach[J]. IEEE Systems, Man, and Cybernetics Magazine, 2023, 9(4): 20-25.
[5] 徐凡, 李明昊, 黄琪, 等. 知识图谱驱动的图卷积神经网络谣言检测模型[J]. 中国科学:信息科学, 2023, 53(04): 663-681.
[6] Sun X, Yin H, Liu B, et al. Structure learning via meta hyperedge for dynamic rumor detection[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(9): 9128-9139.
[7] Gong Y, Liu S, Bai Y. Influence minimization with conformity aware competitions[J]. IEEE Systems Journal, 2023, 17(3): 3706-3717.
[8] 于凯, 宿天睿. 基于信息风险感知理论的虚假信息点对点传播建模与仿真研究[J]. 计算机科学, 2023, 50(07): 376-385.
[9] Shi Q, Yang W, Wang C, et al. Robust misinformation prevention with uncertainty on suspicious nodes[J]. Neurocomputing, 2024, 577: 127344.
[10] Yang L, Li Z. Deadline-aware misinformation prevention in social networks with time-decaying influence[J]. Expert Systems with Applications, 2024, 238: 121847.
[11] Ghoshal A K, Das N, Das S. Influence of community structure on misinformation containment in online social networks[J]. Knowledge-Based Systems, 2021, 213: 106693.
[12] Amoruso M, Anello D, Auletta V, et al. Contrasting the spread of misinformation in online social networks[J]. Journal of Artificial Intelligence Research, 2020, 69: 847-879.
[13] Wang Y, Li L, Wang Z, et al. An efficient method for restraining negative information cascades in online social networks[C] ∥Proceedings of the 2022 International Conference on Networking and Network Applications. Urumqi, China, 2022: 459-464.
[14] Yang L, Ma Z, Li Z, et al. Rumor containment by blocking nodes in social networks[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2023, 53(7): 3990-4002.
[15] Jiang Z, Chen X, Ma J, et al. Rumor Decay: Rumor dissemination interruption for target recipients in social networks[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(10): 6383-6395.
[16] Agarwal P, Aziz R A, Zhuang J. Interplay of rumor propagation and clarification on social media during crisis events - A game theoretic approach[J]. European Journal of Operational Research, 2022, 298(2): 714-733.
[17] Ni P, Zhu J, Wang G. Misinformation influence minimization by entity protection on multi-social networks[J]. Applied Intelligence, 2023, 53(6): 6401-6420.
[18] Dey P, Roy S. Centrality based information blocking and influence minimization in online social network[C] ∥Proceedings of the IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS). Bhubaneswar, India, 2017: 1-6.
[19] Ni Q, Guo J, Wu W, et al. Influence-based community partition with sandwich method for social networks[J]. IEEE Transactions on Computational Social Systems, 2022, 10(2): 819-830.
[20] Han L, Zhou Q, Tang J, et al. Identifying top-k influential nodes based on discrete particle swarm optimization with local neighborhood degree centrality[J]. IEEE Access, 2021, 9: 21345-21356.
