Interest maximization in social networks

Nowadays, organizations use viral marketing strategies to promote their products through social networks. A graph represents the social networks. It is expensive to directly send the product promotional information to all the users in the network. In this context, as reported by Kempe et al. (in: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003) introduced the Influence Maximization (IM) problem, which identifies k most influential nodes (spreader nodes) such that the maximum number of people in the network adopt the promotional message. In this work, we propose a maximization version of PAP called the Interest Maximization problem. Different people have different levels of interest in a particular product. This is modeled by assigning an interest value to each node in the network. Then, the problem is to select k initial spreaders such that the sum of the interest values of the people (nodes) who become aware of the message is maximized. We study the Interest Maximization problem under two popular diffusion models: the Linear Threshold Model (LTM) and the Independent Cascade Model (ICM). We show that the Interest Maximization problem is NP-Hard under LTM. We give linear programming formulation for the problem under LTM. We propose four heuristic algorithms for the Interest Maximization problem: Level Based Greedy Heuristic (LBGH), Maximum Degree First Heuristic (MDFH), Profit Based Greedy Heuristic (PBGH), and Maximum Profit Based Greedy Heuristic (MPBGH). Extensive experimentation has been carried out on many real-world benchmark data sets for both diffusion models. The results show that among the proposed heuristics, MPBGH performs better in maximizing the interest value.