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