Combining greedy and evolutionary algorithms to maximize influence in networks under deterministic linear threshold model

In the paper we consider the well-known Influence Maximization (IM) and Target Set Selection (TSS) problems for Boolean networks under Deterministic Linear Threshold Model (DLTM). The main novelty of our paper is that we state these problems in the context of pseudo-Boolean optimization and solve them using evolutionary algorithms in combination with the known greedy heuristic. We also propose a new variant of (1 + 1)-Evolutionary Algorithm, which is designed to optimize a fitness function on the subset of the Boolean hypercube comprised of vectors of a fixed Hamming weight. The properties of this algorithm suit well for solving IM. The proposed algorithm is combined with the greedy heuristic for solving IM and TSS: the latter is used to construct initial solutions. We show that the described hybrid algorithms demonstrate significantly better performance compared to the computational scheme combining the greedy heuristic with the classic variant of (1 + 1)-EA. In the experiments, the proposed algorithms are applied to both real-world networks and the random networks constructed with respect to well-known models of random graphs. The results show that the new algorithms outperform the competition and are applicable to TSS and IM under DLTM for networks with tens of thousands of vertices.