Probing for high influential nodes in social networks via a co-evolutionary memetic algorithm

Jianxin Tang, Yihui Li, Jitao Qu, Xinyue Li and Yabing Yao

Physica A: Statistical Mechanics and its Applications, 2025, vol. 675, issue C

Abstract: The identification of a subset of k high influential nodes in a given network as seed nodes is a fundamental operation to address the influence maximization (IM) problem, which can be formulated as a combinatorial optimization problem and was demonstrated to be NP-hard. Solutions based on evolutionary optimization have been demonstrated to be a promising way to solve the IM problem. However, the utilization of a unified paradigm based on stochastic evolutionary searching mechanisms in the resolution process usually results in premature convergence and susceptibility to local optima. To address the issue, this paper presents a novel bi-directional co-evolutionary memetic algorithm (COMA). By adopting the co-evolution strategy and the memetic concept for reference, the proposed algorithm introduces two distinct evolution directions for the same population as its core. The algorithm employs specific evolutionary strategies for the elite individuals and the common ones to manage a trade-off between the global exploration and local exploitation operations on the partitioned populations, while preserving population diversity. Furthermore, these two evolution directions refine and select individuals based on different evaluation functions, with resulting individuals forming the population of the next generation. Extensive experiments conducted on both synthetic and real-world networks demonstrate the feasibility and effectiveness of the proposed algorithm. The experimental findings indicate that, in comparison to alternative algorithms, COMA enhances the influence spread by an average of 10% in small propagation probabilities and 5.9% in high propagation probabilities.

Keywords: Social network; Influence maximization; Independent cascade model; Co-evolutionary optimization; Memetic algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437125004807
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

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:eee:phsmap:v:675:y:2025:i:c:s0378437125004807

DOI: 10.1016/j.physa.2025.130828

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().