在本篇論文，我們提出了一個基於社群網路的傳播影響力最大化上的一個嶄新的問題。給定一段時間與一群目標被影響者，這些目標影響者皆可以被其鄰居們分別影響多次，其次數ｔ稱為影響頻率，而選定一開始的k個初始影響者，將其影響頻率最大化則是本篇論文所要解決的問題。病毒式行銷不同於現有常見的傳統式行銷利用電視報紙等媒體來傳播其廣告訊息，而是藉由消費者之間的推薦，因此更能受到消費者的信賴進而達到廣告效益。在本篇論文中，我們與一般的影響力傳播模型主要有兩點不同，首先是我們考慮了目標消費者，而不是所有群眾，會更貼近實際廣告行為，與節省不必要的廣告支出；其次是影響頻率，不同於傳統模型只判斷影響與否，藉由影響次數可看出其消費者對於產品的信賴程度。由於此問題的難度是NP-hard，更能得知其問題的挑戰性。因此我們首先提出了貪婪式演算法，用來找出其k個初始影響者，並以此為基準，並提出兩個有效的啟發式演算法，能夠快速得出結
果，甚至能有機會超過貪婪式演算法的效果。

In this paper, we study a novel problem of influence maximization in social networks: Given a period of promotion time and a set of target users, each of which can be activated by its neighbors multiple times, we aim at maximizing the total acceptance frequency of these target users by initially selecting k most influential seeds. The promising viral marketing paradigm on social network is different from the current research in two main aspects. First, instead of maximizing the message spread over the entire social network, we focus on the target market since the business vendors almost specify the target users before designing its marketing strategy. Second, the status of a user is no longer a binary indicator representing either active or inactive. In the new model the user status turns to be an integer value reflecting the amount of influences delivered to that user. In this paper, we prove the NP-hard nature of this challenging problem. We further present several strategies, including two efficiently heuristic algorithms and a greedy algorithm as the baseline, to select the initial k seeds in pursuit of resulting quality close to the optimal one. As demonstrated in the empirical study on real data, instead of only providing the flexibility of striking a compromise between the execution efficiency and the resulting quality, our proposed heuristic algorithms can achieve high efficiency and meanwhile obtain the target acceptance frequency even better than the greedy result in some cases, demonstrating its prominent feasibility to resolve the challenging problem efficiently.

[1] S. Bhagat, A. Goyal, and L. V. Lakshmanan. Maximizing product adoption in social networks. In ACM International Conference on Web Search and Data Mining, 2012.
[2] S. Bharathi, D. Kempe, and M. Salek. Competitive influence maximization in social networks. In The Conference on Web and Internet Economics, pages 306–311, 2007.
[3] V. ˇCern`y. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45(1), 1985.
[4] W. Chen, A. Collins, R. Cummings, T. Ke, Z. Liu, D. Rinc´on, X. Sun, Y. Wang, W. Wei and Y. Yuan. Influence maximization in social networks when negative opinions may emerge and propagate. In SIAM International Conference on Data Mining, pages 603–612, 2011.
[5] W. Chen, W. Lu, and N. Zhang. Time-critical influence maximization in social networks with time-delayed diffusion process. In AAAI Conference on Artificial Intelligence, 2012.
[6] W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1029–1038, 2010.
[7] W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 199–208, 2009.
[8] W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In IEEE International Conference on Data Mining,
pages 88–97, 2010.
[9] P. Domingos and M. Richardson. Mining the network value of customers. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 57–66, 2001.
[10] U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4), July 1998.
[11] A. Goyal, F. Bonchi, and L. V. Lakshmanan. A data-based approach to social influence maximization. Proceedings of the VLDB Endowment, 5(1), 2011.
[12] A. Goyal, W. Lu, and L. V. Lakshmanan. Celf++: optimizing the greedy algorithm for influence maximization in social networks. In International World Wide Web Conference, pages 47–48, 2011.
[13] A. Goyal, W. Lu, and L. V. S. Lakshmanan. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In IEEE International Conference on Data Mining, pages 211–220, 2011.
[14] J. Guo, P. Zhang, C. Zhou, Y. Cao, and L. Guo. Personalized influence maximization on social networks. In ACM International Conference on Information and Knowledge Management, pages 199–208, 2013.
[15] J. Hartline, V. Mirrokni, and M. Sundararajan. Optimal marketing strategies over social networks. In International World Wide Web Conference, pages 189–198, 2008.
[16] Q. Jiang, G. Song, G. Cong, Y. Wang, W. Si, and K. Xie. Simulated annealing based influence maximization in social networks. In AAAI Conference on Artificial Intelligence, 2011.
[17] K. Jung, W. Heo, and W. Chen. Irie: Scalable and robust influence maximization in social networks. In IEEE International Conference on Data Mining, pages 918–923, 2012.
[18] D. Kempe, J. Kleinberg, and ´E. Tardos. Maximizing the spread of influence through a social network. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 137–146, 2003.
[19] M. Kimura and K. Saito. Tractable models for information diffusion in social networks. In PKDD, pages 259–271. 2006.
[20] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220, 1983.
[21] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 420–429, 2007.
[22] F.-H. Li, C.-T. Li, and M.-K. Shan. Labeled influence maximization in social networks for target marketing. In Privacy, Security, Risk and Trust, IEEE International Conference on and IEEE International Confernece on Social Computing, pages 560–563, 2011.
[23] B. Liu, G. Cong, D. Xu, and Y. Zeng. Time constrained influence maximization in social networks. In IEEE International Conference on Data Mining, pages 439–448, 2012.
[24] H. Ma, H. Yang, M. R. Lyu, and I. King. Mining social networks using heat diffusion processes for marketing candidates selection. In ACM International Conference on Information and Knowledge Management, pages 233–242, 2008.
[25] R. Narayanam and Y. Narahari. A shapley value-based approach to discover influential nodes in social networks. IEEE Transactions on Automation Science and Engineering, pages 130–147, 2011.
[26] M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 61–70, 2002.
[27] L. G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing, 8:410–421, 1979.
[28] D.-N. Yang, H.-J. Hung, W.-C. Lee, and W. Chen. Maximizing acceptance probability for active friending in online social networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 713–721, 2013.