Optimal intervention in economic networks using influence maximization methods
Optimal intervention in economic networks using influence maximization methods
复制标题
使用影响力最大化方法对经济网络进行最佳干预
DOI：
10.1016/j.ejor.2021.10.042
复制
发表时间：
2021
影响因子：
6.4
通讯作者：
Minca, Andreea
中科院分区：
文献类型：
--
作者：
Klages-Mundt, Ariah;Minca, Andreea
我们考虑了Elliott-Golub-Jackson网络模型(Elliott，Golub，and Jackson，2014)中的最优干预，我们证明了它可以转化为一种类似影响力最大化的形式，解释为缺省级联的相反形式。我们对最优干预问题的分析将既定的目标结果扩展到经济网络环境，这需要额外的理论步骤。我们证明了关于最优干预的几个结果：它是NP-难的，并且不能在多项式时间内近似为一个常数因子。反过来，我们证明了将失效阈值随机化导致了问题的一个版本是单调子模块，对于该问题，可以应用现有的多项式时间内的强大近似。除了最优干预外，我们还展示了我们对其他经济网络问题的分析的实际结果：(1)计算经济网络中的期望值是困难的；(2)影响最大化算法可以对大型故障场景进行有效的重要性抽样和压力测试。我们通过从世界投入产出数据库推断出的通过投入-产出联系连接的公司网络来说明我们的结果。
We consider optimal intervention in the Elliott-Golub-Jackson network model (Elliott, Golub, and Jackson, 2014) and we show that it can be transformed into an influence maximization-like form, interpreted as the reverse of a default cascade. Our analysis of the optimal intervention problem extends well-established targeting results to the economic network setting, which requires additional theoretical steps. We prove several results about optimal intervention: it is NP-hard and cannot be approximated to a constant factor in polynomial time. In turn, we show that randomizing failure thresholds leads to a version of the problem which is monotone submodular, for which existing powerful approximations in polynomial time can be applied. In addition to optimal intervention, we also show practical consequences of our analysis to other economic network problems: (1) it is computationally hard to calculate expected values in the economic network, and (2) influence maximization algorithms can enable efficient importance sampling and stress testing of large failure scenarios. We illustrate our results on a network of firms connected through input-output linkages inferred from the World Input Output Database.