Spread and defend infection in graphs
share
The spread of an infection, a contagion, meme, emotion, message and various other spreadable objects have been discussed in several works. Burning and firefighting have been discussed in particular on static graphs. Burning simulates the notion of the spread of "fire" throughout a graph (plus, one unburned node burned at each time-step), graph firefighting simulates the defending of nodes by placing firefighters on the nodes which have not been already burned while the fire is being spread (started by a single fire source). This article studies a combination of firefighting and burning on a graph class which is a variation (generalization) of temporal graphs. Nodes can be infected from "outside" a network. We present a notion of both upgrading (of unburned nodes, similar to firefighting) and repairing (of infected nodes). The nodes which are burned, firefighted, or repaired are chosen probabilistically. So a variable amount of nodes are infected, upgraded and repaired in each time step. In the model presented in this article, both burning and firefighting proceed concurrently, we introduce such a system to enable the community to study the notion of spread of an infection and the notion of upgrade/repair against each other. The graph class that we study these processes is a variation of temporal graph class in which at each time-step, probabilistically, a communication takes place (iff an edge exists in that time step). In addition, a node can be "worn out" and thus can be removed from the network, a new healthy node can be added to the network. This class of graphs enables systems with high complexity to be able to be simulated and studied.
READ FULL TEXT