Graph Burning in Community-based Networks

Gennaro Cordasco¹ ; Luisa Gargano² ; Adele A. Rescigno²

¹ Università degli Studi della Campania "Luigi Vanvitelli"
² Università degli Studi di Salerno

Journal of Graph Algorithms and Applications, Special issue on Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023 , Tome 28 (2024) no. 3, pp. 11-30.

Résumé

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.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. 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.Moreover, we consider the problem of maximizing the number of satisfied groups, given a budget $k$ on the number of rounds.

Détail

DOI : 10.7155/jgaa.v28i3.2969

Keywords: Graph burning, influence spread, approximation algorithms