  Information spread is an intriguing topic to study in network science, which
investigates how information, influence, or contagion propagate through
networks. Graph burning is a simplified deterministic model for how information
spreads within networks. The complicated NP-complete nature of the problem
makes it computationally difficult to solve using exact algorithms.
Accordingly, a number of heuristics and approximation algorithms have been
proposed in the literature for the graph burning problem. In this paper, we
propose an efficient genetic algorithm called Centrality BAsed
Genetic-algorithm (CBAG) for solving the graph burning problem. Considering the
unique characteristics of the graph burning problem, we introduce novel genetic
operators, chromosome representation, and evaluation method. In the proposed
algorithm, the well-known betweenness centrality is used as the backbone of our
chromosome initialization procedure. The proposed algorithm is implemented and
compared with previous heuristics and approximation algorithms on 15 benchmark
graphs of different sizes. Based on the results, it can be seen that the
proposed algorithm achieves better performance in comparison to the previous
state-of-the-art heuristics. The complete source code is available online and
can be used to find optimal or near-optimal solutions for the graph burning
problem.
