Skip to main content
Erschienen in: Journal of Combinatorial Optimization 1/2021

26.11.2020

Discount allocation for cost minimization in online social networks

verfasst von: Qiufen Ni, Smita Ghosh, Chuanhe Huang, Weili Wu, Rong Jin

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2021

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We introduce the discount allocation problem to a new online social networks (OSNs) scenario where the nodes and the relationships between nodes are determined but the states of edges between nodes are unknown. We can know the states of all the edges centered on a node only when it becomes active. Different from most previous work on influence maximization discount allocation problem in OSNs, our goal is to minimize the discount cost that the marketer spends while ensuring at least Q customers who adopt the target product in the end in OSNs. We propose an online discount allocation policy to select seed users to spread the product information. The marketer initially selects one seed user to offer him a discount and observes whether he accepts the discount. If he accepts the discount, the marketer needs to observe how well this seed user contributes to the diffusion of product adoptions and how much discount he accepts. The remaining seeds are chosen based on the feedback of diffusion results obtained by all previous selected seeds. We propose two online discount allocation greedy algorithms under two different situations: uniform and non-uniform discounts allocation. We offer selected users discounts changing from the lowest to highest in the discount rate set until the users receive the discount and become seed users in non-uniform discount allocation situation, which saves the cost of firms comparing with the previous method that providing product to users for free. We present a theoretical analysis with bounded approximation ratios for the algorithms. Extensive experiments are conducted to evaluate the performance of the proposed online discount allocation algorithms on real-world online social networks datasets and the results demonstrate the effectiveness and efficiency of our methods.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Abebe R, Adamic LA, Kleinberg J (2018) Mitigating overexposure in viral marketing. In: Thirty-second AAAI conference on artificial intelligence Abebe R, Adamic LA, Kleinberg J (2018) Mitigating overexposure in viral marketing. In: Thirty-second AAAI conference on artificial intelligence
Zurück zum Zitat Choi J, Yi Y (2018) Necessary and sufficient budgets in information source finding with querying: adaptivity gap. In: IEEE international symposium on information theory (ISIT). IEEE, pp 2261–2265 Choi J, Yi Y (2018) Necessary and sufficient budgets in information source finding with querying: adaptivity gap. In: IEEE international symposium on information theory (ISIT). IEEE, pp 2261–2265
Zurück zum Zitat Dhamal S (2018) Effectiveness of diffusing information through a social network in multiple phases. In: IEEE global communications conference (GLOBECOM). IEEE, pp 1–7 Dhamal S (2018) Effectiveness of diffusing information through a social network in multiple phases. In: IEEE global communications conference (GLOBECOM). IEEE, pp 1–7
Zurück zum Zitat Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 57–66 Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 57–66
Zurück zum Zitat Golovin D, Krause A (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. J Artif Intell Res 42:427–486MathSciNetMATH Golovin D, Krause A (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. J Artif Intell Res 42:427–486MathSciNetMATH
Zurück zum Zitat Goyal A, Bonchi F, Lakshmanan LV (2011) A data-based approach to social influence maximization. Proc VLDB Endow 5(1):73–84CrossRef Goyal A, Bonchi F, Lakshmanan LV (2011) A data-based approach to social influence maximization. Proc VLDB Endow 5(1):73–84CrossRef
Zurück zum Zitat Han K, Huang K, Xiao X, Tang J, Sun A, Tang X (2018) Efficient algorithms for adaptive influence maximization. Proc VLDB Endow 11(9):1029–1040CrossRef Han K, Huang K, Xiao X, Tang J, Sun A, Tang X (2018) Efficient algorithms for adaptive influence maximization. Proc VLDB Endow 11(9):1029–1040CrossRef
Zurück zum Zitat Han K, Xu C, Gui F, Tang S, Huang H, Luo J (2018) Discount allocation for revenue maximization in online social networks. In: Proceedings of the eighteenth ACM international symposium on mobile ad hoc networking and computing. ACM, pp 121–130 Han K, Xu C, Gui F, Tang S, Huang H, Luo J (2018) Discount allocation for revenue maximization in online social networks. In: Proceedings of the eighteenth ACM international symposium on mobile ad hoc networking and computing. ACM, pp 121–130
Zurück zum Zitat Jurvetson S (2000) What exactly is viral marketing. Red Herring 78:110–112 Jurvetson S (2000) What exactly is viral marketing. Red Herring 78:110–112
Zurück zum Zitat Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 137–146 Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 137–146
Zurück zum Zitat Opsahl T (2013) Triadic closure in two-mode networks: redefining the global and local clustering coefficients. Soc Netw 35(2):159–167CrossRef Opsahl T (2013) Triadic closure in two-mode networks: redefining the global and local clustering coefficients. Soc Netw 35(2):159–167CrossRef
Zurück zum Zitat Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 61–70 Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 61–70
Zurück zum Zitat Salha G, Tziortziotis N, and Vazirgiannis M (2018) Adaptive submodular influence maximization with myopic feedback. In: 2018 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 455–462 Salha G, Tziortziotis N, and Vazirgiannis M (2018) Adaptive submodular influence maximization with myopic feedback. In: 2018 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 455–462
Zurück zum Zitat Singer Y (2016) Influence maximization through adaptive seeding. ACM SIGecom Exch 15(1):32–59CrossRef Singer Y (2016) Influence maximization through adaptive seeding. ACM SIGecom Exch 15(1):32–59CrossRef
Zurück zum Zitat Tang S (2018) Stochastic coupon probing in social networks. In: Proceedings of the 27th ACM international conference on information and knowledge management. ACM, pp 1023–1031 Tang S (2018) Stochastic coupon probing in social networks. In: Proceedings of the 27th ACM international conference on information and knowledge management. ACM, pp 1023–1031
Zurück zum Zitat Tang S (2018) When social advertising meets viral marketing: sequencing social advertisements for influence maximization. In: Thirty-second AAAI conference on artificial intelligence, Tang S (2018) When social advertising meets viral marketing: sequencing social advertisements for influence maximization. In: Thirty-second AAAI conference on artificial intelligence,
Zurück zum Zitat Tang Y, Xiao X, and Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, pp 75–86 Tang Y, Xiao X, and Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, pp 75–86
Zurück zum Zitat Tong G, Wu W, Tang S, Du D-Z (2017) Adaptive influence maximization in dynamic social networks. IEEE/ACM Trans Netw (TON) 25(1):112–125CrossRef Tong G, Wu W, Tang S, Du D-Z (2017) Adaptive influence maximization in dynamic social networks. IEEE/ACM Trans Netw (TON) 25(1):112–125CrossRef
Zurück zum Zitat Tong G, Wang R, Li X, Wu W, Du D-Z (2019) An approximation algorithm for active friending in online social networks. In: 2019 IEEE 39th international conference on distributed computing systems (ICDCS). IEEE, pp 1264–1274 Tong G, Wang R, Li X, Wu W, Du D-Z (2019) An approximation algorithm for active friending in online social networks. In: 2019 IEEE 39th international conference on distributed computing systems (ICDCS). IEEE, pp 1264–1274
Zurück zum Zitat Wang C, Chen W, Wang Y (2012) Scalable influence maximization for independent cascade model in large-scale social networks. Data Min Knowl Discov 25(3):545–576MathSciNetCrossRef Wang C, Chen W, Wang Y (2012) Scalable influence maximization for independent cascade model in large-scale social networks. Data Min Knowl Discov 25(3):545–576MathSciNetCrossRef
Zurück zum Zitat Wang H, Liu B, Zhang X, Wu L, Wu W, Gao H (2016) List edge and list total coloring of planar graphs with maximum degree 8. J Comb Optim 32(1):188–197MathSciNetCrossRef Wang H, Liu B, Zhang X, Wu L, Wu W, Gao H (2016) List edge and list total coloring of planar graphs with maximum degree 8. J Comb Optim 32(1):188–197MathSciNetCrossRef
Zurück zum Zitat Yang Y, Mao X, Pei J, He X (2016) Continuous influence maximization: what discounts should we offer to social network users? In: Proceedings of the 2016 international conference on management of data. ACM, pp 727–741 Yang Y, Mao X, Pei J, He X (2016) Continuous influence maximization: what discounts should we offer to social network users? In: Proceedings of the 2016 international conference on management of data. ACM, pp 727–741
Zurück zum Zitat Yuan J, Tang S-J (2017) Adaptive discount allocation in social networks. In: Proceedings of the 18th ACM international symposium on mobile ad hoc networking and computing. ACM, p 22 Yuan J, Tang S-J (2017) Adaptive discount allocation in social networks. In: Proceedings of the 18th ACM international symposium on mobile ad hoc networking and computing. ACM, p 22
Metadaten
Titel
Discount allocation for cost minimization in online social networks
verfasst von
Qiufen Ni
Smita Ghosh
Chuanhe Huang
Weili Wu
Rong Jin
Publikationsdatum
26.11.2020
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 1/2021
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-020-00674-1

Weitere Artikel der Ausgabe 1/2021

Journal of Combinatorial Optimization 1/2021 Zur Ausgabe