Finding smallest initial sets to spread influence in changing networks
Zero Forcing Sets in Temporal Graphs
Discrete MathematicsComputational Complexity
Summary
This paper looks at how to find the smallest starting group of people in a network who can spread an idea (or corruption) to everyone else over time. The network changes in each time step, and the process spreads based on a rule: if someone infected has only one healthy neighbor, that neighbor gets infected next. The authors study how hard it is to pick this starting group under different scenarios and offer some ways to solve the problem efficiently in special cases. They also answer a previous question about doing the spread all at once in one time step.
What this means in practice
- •For network schedulers: Determine minimal node sets that guarantee full message spreading in dynamic communication networks with evolving connections.
- •For cybersecurity teams: Assess vulnerability and design minimal control points in time-varying networks to prevent cascading failures or spreading corruption.
A theory result. No direct application yet.
Authors
Julien Baste, Simon Dreyer, Clara Marcille, Mikaël Rabie, Ronan Toullec-Streicher
Abstract
The Zero Forcing (or corruption) of a graph is the problem of finding a minimum-size ``corrupting'' set. It corresponds to a subset of its vertices that can corrupt the whole graph by iterating the following rule: if a corrupted vertex has exactly one neighbor that is not yet corrupted, the neighbor gets corrupted. The iteration of this process comes from the fact that the corruption of a vertex might enable new corruptions (from itself or some of its neighbors). For this reason, one can consider a step of corruption, where all the possible instances of the corruption rule are applied at once. This paper investigates Zero Forcing on temporal graphs, where the topology of the graph evolves throughout the experiment. At each time step (or snapshot) of the graph, a step of corruption is resolved wherever possible. We study the problem of finding a minimum-size corrupting set such that the whole (temporal) graph is corrupted at the end of the experiment. We present a panorama of results, including NP-hardness in some not-so-restrictive scenarios, polynomial algorithms, and a solution to an open question when the whole graph must be corrupted in a single step.