Research on Algorithms for Network Interdiction Problem

网络拦截问题算法研究

基本信息

批准号：
17F17727
负责人：
塩浦昭義
金额：
$ 0.9万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2017
资助国家：
日本
起止时间：
2017-10-13 至 2020-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17F17727/
关键词：
network flow large scale network algorithms network flow graph algorithm

项目摘要

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.

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

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Gap-planar graphs

间隙平面图

DOI：
10.1016/j.tcs.2018.05.029
发表时间：
2018
期刊：
影响因子：
1.1
作者：
Bae Sang Won;Baffier Jean;Chun Jinhee;Eades Peter;Eickmeyer Kord;Grilli Luca;Hong Seok;Korman Matias;Montecchiani Fabrizio;Rutter Ignaz;T?th Csaba D.
通讯作者：
T?th Csaba D.

Gap-Planar Graphs

间隙平面图