由於近年來科技發展，傳播訊息變得相當便利，人們可以很容易地在網路上散播訊息，像是商品的廣告，而這種於社群網路上吸引用戶的用法，被稱為病毒式行銷。同時由於廠商總是一次推出許多件同類商品的系列供消費者選擇，該如何有預算限制的情形，替不同價位的商品，找出最適合的代言人，也是個相當熱門的議題。而現今的研究往往沒有考慮到實際的商業環境，消費者對於同一類型的商品，應該需求有限，而不會一味地接收到商品資訊便購買，也就是說消費者的購買能力在過往的相關研究中大多沒有限制。我們考慮到上述的情形，提出了一個嶄新的問題，即為有限預算之多產品利潤最大化(BMPM)問題，考慮消費者的消費能力，要在整體預算有限的情形，替多種商品找到合適的種子使總體的利潤最大化。因此，我們提出了BMPMGreedy演算法以及新的圖架構PWDAG以有效地解決有限預算之多產品利潤最大化問題，並於真實資料集中驗證BMPMGreedy演算法可以有效地最大化利潤。

Due to the development of technology in recent years, the propagation of information has become very convenient. People can easily propagate the information on the Internet, such as product advertisements. This use of attracting users on social networks is called viral marketing. At the same time, because companies always launch a series of similar products for consumers to select from, how to find the most potential influencer for the products of different prices with a seed budget limitation is a very hot topic. However, researches in recent years are often not suitable to the business model in reality because the consumers should have the limited demand for the same type of products. In other words, the purchasing ability of consumers is mostly unrestricted in these related researches. Considering the above situation, we propose a novel problem, called Budgeted Multiple-Product Profit Maximization (BMPM) Problem. Consider the purchasing ability of consumers, we must find suitable seeds for multiple products to maximize the overall profit when the overall budget is limited. Therefore, we propose the BMPMGreedy algorithm and a new graph structure PWDAG to effectively solve this problem. As verified by experiments on real world datasets, BMPMGreedy can maximize the overall profit with high efficiency and effectiveness.

1. Kempe, D., Kleinberg, J., & Tardos, É. (2003, August). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 137-146).
2. Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007, August). Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 420-429).
3. Goyal, A., Lu, W., & Lakshmanan, L. V. (2011, March). Celf++ optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on World wide web (pp. 47-48).
4. Chen, W., Wang, C., & Wang, Y. (2010, July). Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1029-1038).
5. Nguyen, H., & Zheng, R. (2013). On budgeted influence maximization in social networks. IEEE Journal on Selected Areas in Communications, 31(6), 1084-1094.
6. Shang, J., Zhou, S., Li, X., Liu, L., & Wu, H. (2017). CoFIM: A community-based framework for influence maximization on large-scale networks. Knowledge-Based Systems, 117, 88-100.
7. Tang, Y., Xiao, X., & Shi, Y. (2014, June). Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data (pp. 75-86).
8. Tang, J., Tang, X., & Yuan, J. (2016, November). Profit maximization for viral marketing in online social networks. In 2016 IEEE 24th International Conference on Network Protocols (ICNP) (pp. 1-10). IEEE.
9. Tang, J., Tang, X., & Yuan, J. (2017). Profit maximization for viral marketing in online social networks: Algorithms and analysis. IEEE Transactions on Knowledge and Data Engineering, 30(6), 1095-1108.
10. Zhang, H., Zhang, H., Kuhnle, A., & Thai, M. T. (2016, April). Profit maximization for multiple products in online social networks. In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications (pp. 1-9). IEEE.
11. Khan, A., Zehnder, B., & Kossmann, D. (2016, May). Revenue maximization by viral marketing: A social network host's perspective. In 2016 IEEE 32nd international conference on data engineering (ICDE) (pp. 37-48). IEEE.
12. Chen, W., Yuan, Y., & Zhang, L. (2010, December). Scalable influence maximization in social networks under the linear threshold model. In 2010 IEEE international conference on data mining (pp. 88-97). IEEE.
13. Horel, T. (2015). Notes on greedy algorithms for submodular maximization.
14. Domingos, P., & Richardson, M. (2001, August). Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 57-66).
15. Lu, W., & Lakshmanan, L. V. (2012, December). Profit maximization over social networks. In 2012 IEEE 12th International Conference on Data Mining (pp. 479-488). IEEE.
16. Zhu, Y., Lu, Z., Bi, Y., Wu, W., Jiang, Y., & Li, D. (2013, December). Influence and profit: Two sides of the coin. In 2013 IEEE 13th International Conference on Data Mining (pp. 1301-1306). IEEE.
17. Tang, J., Tang, X., & Yuan, J. (2018, April). Towards profit maximization for online social network providers. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications (pp. 1178-1186). IEEE.
18. Mirrokni, V. S., Roch, S., & Sundararajan, M. (2012, December). On fixed-price marketing for goods with positive network externalities. In International workshop on internet and network economics (pp. 532-538). Springer, Berlin, Heidelberg.
19. Teng, Y. W., Tai, C. H., Yu, P. S., & Chen, M. S. (2015, August). An effective marketing strategy for revenue maximization with a quantity constraint. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1175-1184).
20. Zhu, Y., Li, D., Yan, R., Wu, W., & Bi, Y. (2017). Maximizing the influence and profit in social networks. IEEE Transactions on Computational Social Systems, 4(3), 54-64.
21. Huang, K., Wang, S., Bevilacqua, G., Xiao, X., & Lakshmanan, L. V. (2017). Revisiting the stop-and-stare algorithms for influence maximization. Proceedings of the VLDB Endowment, 10(9), 913-924.
22. Tang, J., Tang, X., Xiao, X., & Yuan, J. (2018, May). Online processing algorithms for influence maximization. In Proceedings of the 2018 International Conference on Management of Data (pp. 991-1005).
23. Tang, J., Tang, X., & Yuan, J. (2017, July). Influence maximization meets efficiency and effectiveness: A hop-based approach. In 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) (pp. 64-71). IEEE.
24. Tang, J., Tang, X., & Yuan, J. (2018). An efficient and effective hop-based approach for influence maximization in social networks. Social Network Analysis and Mining, 8(1), 10.
25. Tang, Y., Xiao, X., & Shi, Y. (2014, June). Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data (pp. 75-86).
26. Zhang, Y., Yang, X., Gao, S., & Yang, W. (2019). Budgeted Profit Maximization Under the Multiple Products Independent Cascade Model. IEEE Access, 7, 20040-20049.