Research on Algorithms for Network Interdiction Problem

今年，我们的重点是信息网络中的知识传播。这些网络的一个典型特性是它们的规模庞大，使得经典算法难以应用。在以前的研究中，我们引入了一个模型来评估不同参与者（例如，引文网络中的文章）在传播这种知识中的影响力，我们遇到了（并解决了）一些困难。这两个主要的困难来自于信息网络的时间属性。在我们的引用网络示例中，我们认为文章一旦提交就是静态的。然而，这不是可以自由更新的预印本文章的情况。首先，影响力的循环存在，允许自我满足。其次，它也提出了一个问题，即文章的每个版本产生的知识量。我们提供了一种方法来deconstrate网络与小周期。该方法还可用于近似计算具有任何循环大小的网络中的知识传输。为了处理文章的更新（版本控制）和动态引用，我们需要一个可以捕获任意时间段的交互时间模型。本文将经典的流图和割图的定义推广到流图。

In this year we have focused on the transmission of knowledge in information networks. A typical property of those networks is their massive scale, making classical algorithms difficult to apply. In previous research, we have introduced a model to evaluate the influence of the different actors (for instance, the articles in a citation network) in the transmission of this knowledge.We encountered (and solved) several difficulties. The two major difficulties come from the temporal property of information networks. In our citation network example, we had considered that articles were static once submitted. However, it is not the case of pre-print articles that can be freely updated. First, cycles of influence exist, allowing self-gratification. Second, it also raises the question of the amount of knowledge produced by each version of an article.We provided a method to decycle networks with small cycles. This method is also used to approximate the transmission of knowledge in networks with any cycle size. Such an extension is possible due to the nature of knowledge influence to fade at each interaction.To handle the updates of articles (versioning) and dynamic citations, we needed a temporal model for interactions that can capture any arbitrary timeframe. We extended the definition of the classical flow and cut in graphs to stream graphs.