Social networks represent nowadays in many contexts the main source of information transmission and the way opinions and actions are influenced. For instance, generic advertisements are way less powerful than suggestions from our contacts. However, this process hugely depends on the influence of people who disseminate these suggestions. Therefore modern marketing often involves paying some targeted users, or influencers, for advertising products or ideas. Finding the set of nodes in a social network that lead to the highest information spread -the so-called Influence Maximization (IM) problem- is therefore a pressing question and as such it has recently attracted a great research interest. In particular, several approaches based on Evolutionary Algorithms (EAs) have been proposed, although they are known to scale poorly with the graph size. In this paper, we tackle this limitation in two ways. Firstly, we use approximate fitness functions to speed up the EA. Secondly, we include into the EA various graph-aware mechanisms, such as smart initialization, custom mutations and node filtering, to facilitate the EA convergence. Our experiments show that the proposed modifications allow to obtain a relevant runtime gain and also improve, in some cases, the spread results.
Graph-aware evolutionary algorithms for influence maximization / Konotopska, K.; Iacca, G.. - (2021), pp. 1467-1475. (Intervento presentato al convegno 2021 Genetic and Evolutionary Computation Conference, GECCO 2021 tenutosi a Lille nel 10-14 July 2021) [10.1145/3449726.3463138].
Graph-aware evolutionary algorithms for influence maximization
Iacca G.
2021-01-01
Abstract
Social networks represent nowadays in many contexts the main source of information transmission and the way opinions and actions are influenced. For instance, generic advertisements are way less powerful than suggestions from our contacts. However, this process hugely depends on the influence of people who disseminate these suggestions. Therefore modern marketing often involves paying some targeted users, or influencers, for advertising products or ideas. Finding the set of nodes in a social network that lead to the highest information spread -the so-called Influence Maximization (IM) problem- is therefore a pressing question and as such it has recently attracted a great research interest. In particular, several approaches based on Evolutionary Algorithms (EAs) have been proposed, although they are known to scale poorly with the graph size. In this paper, we tackle this limitation in two ways. Firstly, we use approximate fitness functions to speed up the EA. Secondly, we include into the EA various graph-aware mechanisms, such as smart initialization, custom mutations and node filtering, to facilitate the EA convergence. Our experiments show that the proposed modifications allow to obtain a relevant runtime gain and also improve, in some cases, the spread results.File | Dimensione | Formato | |
---|---|---|---|
2104.14909.pdf
accesso aperto
Tipologia:
Post-print referato (Refereed author’s manuscript)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
3.04 MB
Formato
Adobe PDF
|
3.04 MB | Adobe PDF | Visualizza/Apri |
wksp121s2-file1.pdf
Solo gestori archivio
Descrizione: first online
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
3 MB
Formato
Adobe PDF
|
3 MB | Adobe PDF | Visualizza/Apri |
3449726.3463138.pdf
Solo gestori archivio
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
2.91 MB
Formato
Adobe PDF
|
2.91 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione