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.
@article{nazeri2022cbag,title={CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem},author={Nazeri, Mahdi and Mollahosseini, Ali and Izadi, Iman},journal={arXiv preprint arXiv:2208.01008},year={2022}}
@book{przibram1967letters,title={Letters on wave mechanics},author={Einstein, Albert and Schrödinger, Erwin and Planck, Max and Lorentz, Hendrik Antoon and Przibram, Karl},year={1967},publisher={Vision},}
1956
Investigations on the Theory of the Brownian Movement
@book{einstein1956investigations,title={Investigations on the Theory of the Brownian Movement},author={Einstein, Albert},year={1956},publisher={Courier Corporation,},}
@article{einstein1950meaning,title={The meaning of relativity},author={Einstein, Albert and Taub, AH},journal={American Journal of Physics,},volume={18},number={6},pages={403--404},year={1950},publisher={American Association of Physics Teachers,}}
In a complete theory there is an element corresponding to each element of reality. A sufficient condition for the reality of a physical quantity is the possibility of predicting it with certainty, without disturbing the system. In quantum mechanics in the case of two physical quantities described by non-commuting operators, the knowledge of one precludes the knowledge of the other. Then either (1) the description of reality given by the wave function in quantum mechanics is not complete or (2) these two quantities cannot have simultaneous reality. Consideration of the problem of making predictions concerning a system on the basis of measurements made on another system that had previously interacted with it leads to the result that if (1) is false then (2) is also false. One is thus led to conclude that the description of reality as given by a wave function is not complete.
1905
Über die von der molekularkinetischen Theorie der Wärme geforderte Bewegung von in ruhenden Flüssigkeiten suspendierten Teilchen
A. Einstein
Annalen der physik, May 1905
Ann. Phys.
Un the movement of small particles suspended in statiunary liquids required by the molecular-kinetic theory 0f heat
