社交网络中的虚假信息经加边修正最大化问题

在线社交网络如微信等的普及，使人们更加关注信息传播的问题。虚假信息在社交网络中进行传播可能会造成很严重的后果，比如经济损失或者公众恐慌等。因此，需要采取相关的措施来控制虚假信息的传播。传统的虚假信息控制方法主要通过向网络中的部分节点传播真实信息，让真实信息和虚假信息进行竞争来减小虚假信息的影响。文中将传播真实信息和加边的方式相结合，提出了一个虚假信息修正最大化问题。该问题是NP-难的，其目标函数值的计算是#P-难的。由于目标函数既不是次模的也不是超模的，因此采用三明治近似策略来求解该问题。为此，构造目标函数的次模的上界和下界函数，利用反向影响采样技术在基数约束下求解上界和下界函数，最终得到原问题的一个数据相关的近似解。通过在3个真实网络的数据集上进行仿真实验，验证了所提算法的有效性。