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

Alexander Andreev, Stepan Kochemazov and Alexander Semenov

PLOS ONE, 2025, vol. 20, issue 9, 1-31

Abstract: 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.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0331109 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 31109&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0331109

DOI: 10.1371/journal.pone.0331109

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().