Combining greedy and evolutionary algorithms to maximize influence in networks under deterministic linear threshold model
PLOS One · 2025
DOI: 10.1371/journal.pone.0331109 ↗Kurz gefasst
Fachartikel in der Zeitschrift PLOS One, 2025. Verfasst von Alexander Andreev und 2 weiteren Autor:innen. Beteiligte Einrichtung: Information Technologies and Programming Faculty, ITMO University, Saint Petersburg, Russia. Hauptthemen laut MEDLINE: Algorithms, Models, Theoretical. Die Arbeit nennt 101 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministry of Economic Development of the Russian Federation.
Abstract (Originalsprache)
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.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Information Technologies and Programming Faculty, ITMO University, Saint Petersburg, Russia.
- Laboratory of Logical and Optimization Methods for Analysis of Complex Systems, Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, Russia.
ORCID-Profile: Stepan Kochemazov
Förderung
- Ministry of Economic Development of the Russian Federation
Zitieren
APA
Andreev, A., Kochemazov, S., & Semenov, A. (2025). Combining greedy and evolutionary algorithms to maximize influence in networks under deterministic linear threshold model. PLOS One. https://doi.org/10.1371/journal.pone.0331109
Vancouver
Andreev A, Kochemazov S, Semenov A. Combining greedy and evolutionary algorithms to maximize influence in networks under deterministic linear threshold model. PLOS One. 2025. doi:10.1371/journal.pone.0331109
BibTeX
@article{Andreev2025,
author = {Andreev, Alexander and Kochemazov, Stepan and Semenov, Alexander},
title = {Combining greedy and evolutionary algorithms to maximize influence in networks under deterministic linear threshold model},
journal = {PLOS One},
year = {2025},
doi = {10.1371/journal.pone.0331109}
}
EUVIMED