TY - JOUR
AU - Cordasco, Gennaro
AU - Gargano, Luisa
AU - Rescigno, Adele A.
PY - 2024/09/10
Y2 - 2024/10/05
TI - Graph Burning in Community-based Networks
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 3
SE -
DO - 10.7155/jgaa.v28i3.2969
UR - https://jgaa.info/index.php/jgaa/article/view/2969
SP - 11-30
AB - <p>Graph burning is a deterministic, discrete-time process that can be used to model how influence or contagion spreads in a graph. In the graph burning process, each node starts as dormant, and becomes informed/burned over time; when a node is burned, it remains burned until the end of the process. In each round, one can burn a new node (source of fire) in the network. Once a node is burned in round $t$, in round $t+1$, each of its dormant neighbors becomes burned. The process ends when all nodes are burned; the goal is to minimize the number of rounds.<br>We study a variation of graph burning in order to model spreading processes in community-based networks. With respect to a specific piece of information, a community is {\em satisfied} when this information reaches at least a prescribed number of its members. Specifically, we consider the problem of identifying a minimum length sequence of nodes that, according to a graph burning process, allows to satisfy all the communities of the network. <br>We investigate this NP-hard problem from an approximation point of view, showing both a lower bound and a matching upper bound. We also investigate the case when the number of communities is constant and show how to solve the problem with a constant approximation factor.<br>Moreover, we consider the problem of maximizing the number of satisfied groups, given a budget $k$ on the number of rounds.</p>
ER -