Influence Maximization-Cost Minimization in Social Networks Based on a Multiobjective Discrete Particle Swarm Optimization Algorithm

Influence maximization is to extract a small gathering of influential people from a network in order to obtain the largest influence spread. As a key issue in viral marketing, this problem has been extensively studied in the literature. However, despite a great deal of work that has been done, the traditional influence maximization model cannot fully capture the characteristics of real-world networks, since it usually assumes that the cost of activating each individual among the seed set is the same and ignores the cost differences of activating them. In fact, if a company plans to market its products or ideas, it always provides the reward for each disseminator of the seed group according to his or her degree of influence spread. All companies expect to obtain the maximum influence with minimum cost, or acceptable cost, for them. Motivated by this observation, we propose a new model, called influence maximization-cost minimization (IM-CM), which can capture the characteristics of real-world networks better. To solve this new model, we propose a multiobjective discrete particle swarm optimization algorithm for IM-CM. The algorithm can take both individual cost and individual influence into consideration. Besides, the results of this algorithm can also provide a variety of choices for decision makers to choose on the basis of their budgets. Finally, experiments on three real-world networks demonstrate that our algorithm has excellent effectiveness and efficiency.