1 Introduction
With the explosion of social network services in the last decades, hundreds of millions of people can easily interact with each other. The vast prevalence of social networks facilitates large-scale viral marketing through ”word-of-mouth” effects, where each individual recommends a product to his/her friends, contributing to a large number of adoptions of the product. In order to succeed in a viral marketing campaign, it is required to choose a few influential individuals and provide incentives (e.g., free samples of the product and/or cash) to create a cascade of product adoptions as large as possible. Obtaining such a set of users is commonly known as the “influence maximization (IM) problem”. In particular, for a given network G and a probability model representing diffusion mechanism in the network, IM aims to select a set of users (called seed set) which maximizes the expected number of users that are affected in the diffusion process.