Evaluating surrogate models for multi-objective influence maximization in social networks

Doina Bucur, Giovanni Iacca, Andrea Marcelli, Giovanni Squillero, Alberto Tonda

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    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 languageEnglish
    Title of host publicationGECCO 2018 Companion
    Subtitle of host publicationProceedings of the 2018 Genetic and Evolutionary Computation Conference Companion
    PublisherAssociation for Computing Machinery (ACM)
    Pages1258-1265
    Number of pages8
    ISBN (Electronic)9781450357647
    DOIs
    Publication statusPublished - 6 Jul 2018
    EventGenetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto Terrsa, Kyoto, Japan
    Duration: 15 Jul 201819 Jul 2018
    http://gecco-2018.sigevo.org/index.html/tiki-index.php

    Conference

    ConferenceGenetic and Evolutionary Computation Conference, GECCO 2018
    Abbreviated titleGECCO 2018
    CountryJapan
    CityKyoto
    Period15/07/1819/07/18
    OtherA 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

    Fingerprint Dive into the research topics of 'Evaluating surrogate models for multi-objective influence maximization in social networks'. Together they form a unique fingerprint.

  • Cite this

    Bucur, D., Iacca, G., Marcelli, A., Squillero, G., & Tonda, A. (2018). Evaluating surrogate models for multi-objective influence maximization in social networks. In GECCO 2018 Companion : Proceedings of the 2018 Genetic and Evolutionary Computation Conference Companion (pp. 1258-1265). Association for Computing Machinery (ACM). https://doi.org/10.1145/3205651.3208238