The ability of social networks to disseminate information across individuals and groups is based on the social influence that people have on each other.

In this context, the so-called influence maximization problem consists in identifying the most influential nodes of a given social network.

This problem has practical relevance in a wide range of applications and despite the underlying computational complexity, several solution techniques have been presented in the related literature. Nonetheless, bringing together technical feasibility and satisfactory accuracy is still a challenging open research issue.

In this work, we address the influence maximization problem with two complementary contributions. First, we analyze two well-known influence diffusion models, namely the independent cascade and the linear threshold models, and provide a new methodology for addressing the problem of computing the influence spread in a given network. Subsequently, we propose a novel approach to select an initial set of nodes that optimizes the influence spread in large-scale scenarios.

We apply these techniques to several large-scale experiments in real-world scenarios achieving results comparable with the best-performing state-of-the-art algorithms in a shorter computational time.