Genetic Programming Algorithm with a Fast Logical Search for Analyzing Graph Contagion

This paper proposes a genetic programming approach for the analysis of contagion spreading on a graph. In the analyzed problem, graph vertices can get infected from their neighbours along the edges of the graph. The genetic programming technique is used in this paper to build interpretable expressions describing the spreading of the contagion based on simulation results. Bi-objective optimization is performed with the goal of maximizing both the precision and recall of predictions produced by the optimized expressions. In this paper, a Logical Search procedure is proposed that efficiently searches though multiple combinations of expressions found in each generation of the algorithm. Presented experimental results show, that the use of the Logical Search procedure greatly increases the chances of discovering the actual contagion spreading mechanism.