Graph burning and cooling
An interactive, probabilistic and optimization approach
M.R. Susanna (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Yukihiro Murakami – Mentor (TU Delft - Discrete Mathematics and Optimization)
N.D. Verhulst – Mentor (TU Delft - Discrete Mathematics and Optimization)
L.J.J. van Iersel – Mentor (TU Delft - Discrete Mathematics and Optimization)
J. Komjáthy – Graduation committee member (TU Delft - Applied Probability)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Networks appear in many important areas such as transportation systems, social interactions, and computer infrastructures. Understanding how processes spread across such systems is essential for predicting and controlling events like the transmission of diseases, the diffusion of information, or the spread of computer viruses.
This thesis studies the burning number, a measure that indicates the speed at which a process spreads over a network. While most existing research assumes a standard burning process in which every neighbor of a burning node becomes burned with probability 1, this work extends the model to a different setting. We develop an algorithm that incorporates a probability of spreading less than 1, allowing us to compute the expected number of rounds needed to burn an entire graph for any given sequence of nodes. This approach provides more realistic insights into spreading processes and can be applied to a variety of real-world problems.
In addition to the theoretical contribution, we also design and implement an interactive Python tool that visualizes and simulates the burning process for any user-specified graph. This tool makes it possible to experiment with different graphs and contributes to better understanding, teaching, and exploration of the burning number problem.
Finally, this thesis also addresses the related concept the cooling number. For this problem we introduce an integer linear program (ILP) formulation and propose a 2-approximation algorithm to compute a lower bound of the cooling number quickly.
We stated a conjecture about 3-legged spider graphs. This conjecture claims that there exists an optimal cooling sequence such that the source nodes are clustered per leg. As a first step towards the proof of the conjecture, we showed that for a general spider, all the sources of one leg can be clustered at the start of the cooling sequence.