Research on Algorithms for Network Interdiction Problem

在这一年里，我们把重点放在信息网络中的知识传播上。这些网络的一个典型特性是其庞大的规模，这使得经典算法很难应用。在以往的研究中，我们引入了一个模型来评估不同参与者(例如引文网络中的文章)在知识传播中的影响，我们遇到了(并解决了)几个困难。这两个主要困难来自于信息网络的时间性。在我们的引文网络例子中，我们认为文章一旦提交就是静态的。然而，预印文章不是可以自由更新的情况。首先，存在影响的循环，允许自我满足。其次，它也提出了一个问题，即每个版本的文章所产生的知识量。我们提供了一种用小周期对网络进行循环的方法。该方法还可以用来近似知识在任意周期网络中的传输。这样的扩展是可能的，因为知识影响的性质在每次交互中都会消失。为了处理文章(版本控制)和动态引文的更新，我们需要一个可以捕获任意时间框架的交互的时间模型。我们将经典流图和切入图的定义推广到流图。

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.