Efficient Extraction of Target Users for Package Promotion in Big Social Networks

Lo Yao Yeh, Hsien Chu Wu

Research output: Contribution to journalArticlepeer-review


Package promotion (or product bundling and bundle promotion) is widely adopted as an effective marketing strategy to increase sales, but the social tightness of the users significantly influences their willingness to purchase certain products. However, addressing these two factors simultaneously is not a trivial task because it is critical to properly choose a set of socially tight target users to encourage them to buy the products together (social tightness factor), and the selected users should have high preference for the package of products (preference factor). To address the aforementioned challenges, in this article, we study the research problem of promoting a package of products to a set of closely related friends. We formulate a new research problem, named package-oriented group identification (PGI), which can obtain a set of t socially tight users (i.e., inducing more than k edges) who have the maximum preference for a package of items. We prove that the proposed PGI problem is NP-hard, and we develop a polynomial-time algorithm named incremental solution construction with redundancy and infeasibility avoidance for PGI (ISCP) that can effectively and efficiently obtain a good solution to the PGI problem. We compare the performance of ISCP with four other baselines on a large-scale product copurchasing data set with more than 500 k products and 1.7 M copurchasing relationships. The results show that our proposed ISCP algorithm outperforms the other baselines in terms of solution quality and efficiency.

Original languageEnglish
Article number9143462
Pages (from-to)1111-1122
Number of pages12
JournalIEEE Transactions on Computational Social Systems
Issue number5
StatePublished - Oct 2020


  • Algorithm design
  • package promotion
  • social networks
  • target group identification


Dive into the research topics of 'Efficient Extraction of Target Users for Package Promotion in Big Social Networks'. Together they form a unique fingerprint.

Cite this