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.