论文标题
网络中的影响优化：新的配方和有效的不平等现象
Influence Optimization in Networks: New Formulations and Valid Inequalities
论文作者
论文摘要
由于其在社交网络，流行病学和许多其他领域中的重要作用，影响力传播一直是广泛研究的主题。了解传播机制对于控制假新闻或流行病的传播至关重要。在这项工作中，我们研究了检测最小用户的问题，这些用户通过传播在网络上具有一定的影响水平，因此提供了有关该网络中传播行为的宝贵信息。我们开发混合整数编程算法来解决此问题。我们算法的核心基于新的有效不平等，切割平面和嵌入分支切割算法的分离算法。我们还引入了依靠较少变量的紧凑配方。通过广泛的计算实验，我们观察到所提出的方法可以最佳地解决许多先前开放的基准实例，否则就可以达到较小的最佳差距。这些实验还提供了各种见解，以了解不同数学公式的好处。
Influence propagation has been the subject of extensive study due to its important role in social networks, epidemiology, and many other areas. Understanding propagation mechanisms is critical to control the spread of fake news or epidemics. In this work, we study the problem of detecting the smallest group of users whose conversion achieves, through propagation, a certain influence level over the network, therefore giving valuable information on the propagation behavior in this network. We develop mixed integer programming algorithms to solve this problem. The core of our algorithm is based on new valid inequalities, cutting planes, and separation algorithms embedded into a branch-and-cut algorithm. We additionally introduce a compact formulation relying on fewer variables. Through extensive computational experiments, we observe that the proposed methods can optimally solve many previously-open benchmark instances, and otherwise achieve small optimality gaps. These experiments also provide various insights into the benefits of different mathematical formulations.
