  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.
