Abstract
One of the most relevant problems in social networks is influence maximization, that is the problem of finding the set of the most influential nodes in a network, for a given influence propagation model. As the problem is NP-hard, recent works have attempted to solve it by means of computational intelligence approaches, for instance Evolutionary Algorithms. However, most of these methods are of limited applicability for real-world large-scale networks, for two reasons: on the one hand, they require a large number of candidate solution evaluations to converge; on the other hand, each evaluation is computationally expensive in that it needs a considerable number of Monte Carlo simulations to obtain reliable values. In this work, we consider a possible solution to such limitations, by evaluating a surrogate-assisted Multi-Objective Evolutionary Algorithm that uses an approximate model of influence propagation (instead of Monte Carlo simulations) to find the minimum-sized set of most influential nodes. Experiments carried out on two social networks datasets suggest that approximate models should be carefully considered before using them in influence maximization approaches, as the errors induced by these models are in some cases too big to benefit the algorithmic performance.
Original language | English |
---|---|
Title of host publication | GECCO 2018 Companion |
Subtitle of host publication | Proceedings of the 2018 Genetic and Evolutionary Computation Conference Companion |
Publisher | Association for Computing Machinery |
Pages | 1258-1265 |
Number of pages | 8 |
ISBN (Electronic) | 9781450357647 |
DOIs | |
Publication status | Published - 6 Jul 2018 |
Event | Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto Terrsa, Kyoto, Japan Duration: 15 Jul 2018 → 19 Jul 2018 http://gecco-2018.sigevo.org/index.html/tiki-index.php |
Conference
Conference | Genetic and Evolutionary Computation Conference, GECCO 2018 |
---|---|
Abbreviated title | GECCO 2018 |
Country/Territory | Japan |
City | Kyoto |
Period | 15/07/18 → 19/07/18 |
Other | A recombination of the 27th International Conference on Genetic Algorithms (ICGA) and the 23rd Annual Genetic Programming Conference (GP) |
Internet address |
Keywords
- Influence maximization
- Multi-Objective Evolutionary Algorithm
- Social Networks
- Surrogate models