2024/04/12 by Rahul Kumar Gautam, Gautam, Rahul Kumar, Anjeneya Swami Kare +3 · 1 citation
Computer Science · Physics and Astronomy · Social Sciences · #Complex Network Analysis Techniques #Digital Marketing and Social Media #FOS: Computer and information sciences #Social and Information Networks (cs.SI) #Spam and Phishing Detection
paper · pdf · doi:10.48550/arxiv.2404.08236
openalex publication_date 2024/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Nowadays, organizations use viral marketing strategies to promote their products through social networks. It is expensive to directly send the product promotional information to all the users in the network. In this context, Kempe et al. \citekempe2003maximizing introduced the Influence Maximization (IM) problem, which identifies k most influential nodes (spreader nodes), such that the maximum number of people in the network adopts the promotional message. Many variants of the IM problem have been studied in the literature, namely, Perfect Evangelising Set (PES), Perfect Awareness Problem (PAP), etc. In this work, we propose a maximization version of PAP called the \IM 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 \IM problem under two popular diffusion models: the Linear Threshold Model (LTM) and the Independent Cascade Model (ICM). We show that the \IM problem is NP-Hard under LTM. We give linear programming formulation for the problem under LTM. We propose four heuristic algorithms for the \IM problem: \LBE (\LB), Maximum Degree First Heuristic (\MD), \PBE (\PB), and Maximum Profit Based Greedy Heuristic (\MP). 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, \MP performs better in maximizing the interest value.