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, 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 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.

Groups Burning: Analyzing Spreading Processes in Community-Based Networks

Gargano L.;Rescigno A. A.
2023-01-01

Abstract

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, 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 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.
2023
978-3-031-27050-5
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4826074
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact