本研究由倪培昆、朱建明和王国庆共同完成，作者分别来自中国科学院大学工程科学学院与中国科学院大学应急管理科学与工程学院。该论文发表于《中国管理科学》第29卷第9期，出版时间为2021年9月。论文题为《在线社交网络虚假信息交互量最小化的边阻断策略研究》，属于管理科学与网络信息治理的交叉研究领域。

随着在线社交媒体的快速发展，用户获取与传播信息的方式发生了深刻变化。社交媒体平台赋予普通用户自由发布、接受和转发信息的权利，但同时也导致信息真实性把关弱化，使虚假信息在平台上迅速扩散。突发事件中，敏感或吸引眼球的虚假信息极易形成网络舆情，干扰应急处置，甚至造成社会恐慌。例如2011年日本福岛核事故引发的抢盐事件、2012年阿富汗地震谣言导致居民大规模离家等，均表明虚假信息传播能够带来严重社会后果。因此，如何有效限制或阻断虚假信息在社交网络中的传播，已成为网络空间治理的关键问题。

现有研究多基于流行病学模型或经典影响扩散模型（如独立级联模型IC、线性阈值模型LT），通常假设信息传播概率恒定，主要关注如何识别并阻断节点（用户）或边（连接）以最小化受污染用户规模。然而，这些研究往往忽略了用户之间的虚假信息交互量以及信息强化效应（记忆效应）。信息交互量反映了用户之间讨论、转发、评论等参与程度，交互量越高，虚假信息越容易形成“热搜”等热门话题，吸引更多人参与，从而形成恶性循环。基于此，本文提出并研究了一个新的问题——在线社交网络中虚假信息交互量最小化问题，目标是从社交网络边集中选择并阻断k条边，使得阻断后用户之间的虚假信息交互总量最小。

论文首先对该问题进行了理论分析。给定有向社交网络G=(V,E,P,H)，其中V表示用户集，E表示边集，P表示影响概率集，H表示用户间信息交互量集。在IC模型下，节点被传播源S影响的概率可通过其所有父邻居节点的影响概率递归计算。作者证明了该最小化问题是NP-困难的，同时证明了目标函数的计算是#P-困难的。进一步，作者定义了一个新的参量——虚假信息交互量损失值AL，用于衡量阻断某条边后用户间虚假信息交互量的减少程度。基于该参量，原始的最小化目标函数被转换为最大化损失值的目标函数。理论分析表明，该目标函数既不是次模函数，也不是超模函数，说明该问题难以直接借助经典的次模优化方法求解，具有较高计算复杂性。

针对该问题，论文提出了一种两阶段贪婪算法TSGA。第一阶段为候选集获取阶段。作者提出三个定理以剔除网络中“不重要”的边，从而缩小搜索空间。定理2指出：若一条边的两个端点均已被传播源影响（即属于已接受虚假信息的用户集合AS），阻断该边不会影响已经发生的交互量；定理3指出：若某个未被影响的节点的父邻居集为空，则阻断其出边不会对虚假信息交互总量产生影响；定理4指出：若某个未被影响的节点只有一个父邻居，则阻断其出边的影响可通过阻断其入边来更好实现。基于这些规则，算法去除了大量冗余边，得到候选边集ESA。实验表明，在三个真实网络数据集中，候选集规模占总边集的比例显著降低，例如在CGSColl数据集中减少52%，在PClimate数据集中减少超过80%，在Higgs数据集中减少约89%，极大地提升了算法运行效率。

第二阶段为阻断边选择阶段。该阶段采用贪心策略，每次从候选集中选择具有最大虚假信息交互量损失值AL的边加入阻断集E’，然后从网络中移除该边，并利用定理1更新剩余节点的被影响概率以及各候选边的AL值，重复该过程直到选出k条边。算法最后通过EMR方法估计阻断后的虚假信息传播范围，并计算交互总量。由于在IC模型下节点被影响概率的计算依赖于其所有父邻居节点，每阻断一条边都会改变网络拓扑，因此每次选择后需要重新更新概率与损失值。TSGA的时间复杂度为O(n·msa)，其中n为节点数，msa为候选边数。

实验部分在三个真实世界的数据集上进行：CGSColl为科学合作网络，包含约6000个节点和12000条边；PClimate为社交网络数据集，包含约102000个节点和330000条边；Higgs为Twitter传播网络，包含约304000个节点和461000条边。由于数据集缺少节点间影响概率，实验中采用了两种影响概率设置方法：统一概率p=0.5以及考虑信息强化效应的动态概率p=EEI。在EEI模型中，影响概率随用户间交互量增加而上升，本文设置参数b=0.2，pmax=0.8，p(1)=0.1，从而模拟交互量越高则传播概率越高的现象。

实验将TSGA与三种现有启发式方法进行了比较：KED（k边删除法）、OD（出度评分法）以及RAM（任意阻断算法）。结果显示，在不同数据集和不同影响概率条件下，TSGA均能有效降低用户间虚假信息交互总量。在阻断相对较少的边时，TSGA即能使交互总量显著下降，表现出较高效率。虽然KED在部分条件下性能接近TSGA，但其在不同数据集和影响概率下的表现不稳定；OD算法在部分网络中需要阻断大量边后才能引起明显变化，甚至出现“断崖式”下降，说明其性能受网络结构影响较大；RAM算法效果最差。TSGA则在所有实验场景中表现出稳定且优于其他算法的性能。

进一步，实验还评估了阻断后虚假信息传播值的变化。结果表明，在不同的影响概率和数据集中，TSGA限制虚假信息传播的能力同样优于其他算法。虚假信息传播值与交互总量之间的相关性并不强，说明仅以受污染节点规模为目标的方法可能无法有效降低用户间的交互热度。TSGA通过直接针对交互量优化，能够在降低传播范围的同时更显著地抑制用户参与强度。

本研究的学术价值主要体现在三个方面：第一，提出了虚假信息交互量最小化这一新的问题，将研究视角从传统的受污染节点规模扩展到用户间交互强度，更贴近现实中虚假信息“上热搜”、形成舆论热点的传播特征。第二，理论上证明了问题的NP-困难性与目标函数计算#P-困难性，并指出目标函数既非次模亦非超模，为后续研究提供了明确的复杂性边界。第三，在方法上提出了结合网络结构规则的候选集缩减策略与贪心阻断策略的TSGA算法，能够在保持较高解质量的同时显著降低计算开销。

应用价值方面，该方法可为社交平台治理虚假信息提供辅助决策支持。例如，平台可根据用户间历史交互数据识别高交互量连接，在突发舆情初期选择性阻断部分传播路径，降低虚假信息的热度与扩散范围，为真相发布和舆情引导争取时间。此外，该策略也可用于信息安全管理、公共卫生事件中的谣言防控等场景。

本研究的亮点在于：将信息交互量纳入优化目标，突破了仅关注受污染用户规模的局限；引入信息强化效应以更真实地刻画传播过程；提出三定理有效缩减候选边集，提升了大规模网络中的求解效率；通过三个真实网络数据集的实验验证了算法的有效性与稳定性。研究为在线社交网络虚假信息治理提供了新的建模思路和算法工具。