A new heuristic for influence maximization in social networks

Abstract

Influence Maximization (IM) is defined as the problem of finding the minimal IM-seed set of nodes maximally influential in a network. IM solution is formulated in the context of an influence spread model describing how the influence is propagated through the network. IM is relevant for applications such as viral marketing, and the analysis of infection diffusion in a community. Such communities are described by graphs model which have some kind of probabilistic description of how influence is propagated from one node to its neighbours. The cascade and threshold propagation models are the most popular in the literature. In this article, a new global heuristic search method for IM is proposed. We provide comparison over a collection of synthetic and real life graphs against other state-of-the-art heuristic search methods, namely Simulated Annealing, Genetic Algorithms, Harmony Search and the classical Greedy Search (GS) algorithm. Our new method (IMH) competes with the GS algorithm getting the minimal IM-seed set whose influence spreads the largest amount of nodes. Our method improves Greedy algorithm’s time execution.