Establishing Herd Immunity is Hard Even in Simple Geometric Networks

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00363799" target="_blank" >RIV/68407700:21240/23:00363799 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-32296-9_5" target="_blank" >https://doi.org/10.1007/978-3-031-32296-9_5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-32296-9_5" target="_blank" >10.1007/978-3-031-32296-9_5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Establishing Herd Immunity is Hard Even in Simple Geometric Networks

Popis výsledku v původním jazyce

We study the following model of disease spread in a social network. In the beginning, all individuals are either ``infected'' or ``healthy''. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbours are already infected. We represent the social network as a graph. Inspired by the real-world restrictions in the current epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph families, such as interval graphs and grid graphs.

Název v anglickém jazyce

Establishing Herd Immunity is Hard Even in Simple Geometric Networks

Popis výsledku anglicky

We study the following model of disease spread in a social network. In the beginning, all individuals are either ``infected'' or ``healthy''. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbours are already infected. We represent the social network as a graph. Inspired by the real-world restrictions in the current epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph families, such as interval graphs and grid graphs.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-19557S" target="_blank" >GA22-19557S: Nové výzvy ve výpočetní socální volbě</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 18th Workshop on Algorithms and Models for the Web Graph

ISBN

978-3-031-32295-2

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

68-82

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Toronto

Datum konání akce

23. 5. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—