We consider the problem of controlling the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers $k$ and $\ell$, is it possible to limit the diffusion to at most $k$ other nodes of the network by immunizing at most $\ell$ nodes? We consider several parameters associated to the input, including: the bounds $k$ and $\ell$, the maximum node degree $\Delta$, the treewidth, and the neighborhood diversity of the network. We first give $W[1]$ or $W[2]$-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.


翻译:我们考虑在网络中控制有害物品扩散的问题,例如疾病传染扩散或传播假新闻。我们假设了传播线性阈值模式,每个节点都有测量对传染耐药性的阈值。我们研究了问题的参数复杂性:鉴于一个网络,一组最初被污染的节点,以及两个整数,一万元和一万元,我们能否通过在最多1千元的节点上进行免疫,将传播限制在网络中最多不超过1千元的其他节点上?我们考虑了与输入有关的几个参数,包括:约束值美元和1千元,最大节点值$和1千元,树枝,以及网络的周边多样性。我们首先给每个考虑的参数以1千元或2千元的硬度结果。然后我们给某些参数组合提供固定参数算法。

0
下载
关闭预览

相关内容

Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
5+阅读 · 2018年11月27日
Arxiv
0+阅读 · 2021年3月31日
Arxiv
0+阅读 · 2021年3月30日
Arxiv
0+阅读 · 2021年3月30日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
5+阅读 · 2018年11月27日
Top
微信扫码咨询专知VIP会员