Abstract
Marketing through mobile social networks is convenient, low-cost, and beneficial for small companies seeking to expand their customer numbers. In the literature, many studies address the influence maximization problem, which selects initial consumers (seeds) to spread the product information such that the number of consumers receiving the product information (the influenced consumers) is maximized. However, to date, none of these schemes take the beliefs of other persons that could significantly change the consumer's behavioral intention into account. In this paper, we fill this gap by proposing a new variant of the influence maximization problem, the Budgeted Seed Selection (BSS) problem, which asks for a set of seeds with the total cost not greater than a given budget in a mobile social network such that the total expected behavioral intentions of the consumers influenced by the selected seeds are maximized. In addition, we propose an approximation algorithm for the BSS problem. We also conduct simulations to evaluate the performance of our algorithm using real traces and synthesis data. Experimental results show that our algorithm evaluates an approximately optimal seed set for the BSS problem and outperforms several greedy algorithms.