近年來由於社群網路的蓬勃發展，使得人們利用社群網路來接收或傳遞訊息已經變成一個很基本的媒介。許多店家都希望藉由病毒式行銷(Viral Marketing)的特性，在社群網路上推銷他們的產品或是活動。因此在過去的研究中，有許多Influence Maximization的研究討論如何找出社群網路上有效推銷者。試圖藉由這些推銷者達到產品或活動行銷的目的。然而我們發現這類的問題在選擇有效推銷者的過程中忽略了社群群眾本身對於訊息本身的偏好，同時對於活動具有時效性的情況下將面臨一些問題。因此，在這篇論文中，我們針對如何社群網路的使用者中找出一組有效的推銷者，使其傳遞訊息給查詢所要的目標對象時間最短。我們將這樣的問題稱為Diffusion Minimization on Specific Targets problem (DM-ST) 。論文中正式定義DM-ST的問題，並且證明此問題為NP-hard。為了解決此問題，我們提出了diffusion cascade model和label-based propagation probabilistic model來模擬真實世界的傳遞行為和資訊的傳遞機率。並提出了兩個演算法: Baseline algorithm和LDT algorithm。前者利用貪婪的方式，找出近似解的答案。後者藉由建立樹狀結構與兩個過濾的機制，減少搜尋空間，加速演算法的執行時間。最後我們提出了一系列的實驗來評測各個演算法的成效。實驗結果顯示了我們提出的演算法有較佳的傳遞時間及執行效率。

In recent years, people have begun utilizing social networks as a platform for receiving or propagating information because it’s flourishing. Numerous shops want to promote their products or activities through social networks via viral marketing. Therefore, in previous studies, lots of research of Influence Maximization is to focus on how to find effective salesmen in social networks, and try to sell products or activities for marketing through these men. However, we find those problems of selecting effective salesmen will ignore that people have preferences on the information, and also have time-sensitive issues. Therefore, in this paper, we address the problem of identifying a small number of individuals through whom the information can be diffused to the specific targets as soon as possible, referred to as the diffusion minimization on specific targets problem (DM-ST). We formally define the DM-ST problem, and show that it is NP-hard. In order to solve this problem, we proposed diffusion cascade model and label-based propagation probabilistic model to simulate real world diffusion behavior and information propagation probability. And proposed two algorithms: Baseline algorithm and LDT algorithm. The former use greedy-based way to find the approximate solution by spending less time. The latter is more efficient algorithm; by creating LDT and two pruning mechanisms such that reducing the search space and accelerating the execution time. Finally, extensive experiments are proposed to evaluate the efficiency of each algorithm, and the result show that our algorithms have better performance.

Bibliography
[1] A. Goyal, F. B. and Lakshmanan, L. V. S. (2011). A data-based approach to social influence maximization. In Proc. VLDB Endowment, volume 5, pages 73-84.
[2] C. Kim, S. Lee, S. P. and goo Lee, S. (2013). Influence maximization algorithm using markov clustering. In International Conference on Database Systems for Advanced Applications, pages 112-126, Seoul 151-742, Korea.
[3] Chaudhury, A., Basuchowdhuri, P., and Majumder, S. (2012). Spread of information in a social network using influential nodes. In Pacific Asia Conference on Knowledge Discovery and Data Mining (PAKDD), volume 7302, pages 121-132.
[4] D. M. Romero, B. M. and Kleinberg, J. (2011). Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In Proc. of ACM WWW.
[5] D. Ramage, S. D. and Liebling, D. (2010). Characterizing microblogs with topic models. In Proceedings of the Fourth International AAAI Conference on Weblogs and Social Media.
[6] Domingos, P. and Richardson, M. (2001). Mining the network value of customers. In Proc. 7th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, pages 57-66.
[7] E. Bakshy, I. Rosenn, C. M. and Adamic, L. (2012). The role of social networks in information diffusion. In Proc. of ACM WWW, Lyon, France.
[8] effective outbreak detection in networks, C. (2007). Cost-effective outbreak detection in networks. In Proc. 13th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, pages 420-429.
[9] G. Li, S. Chen, J. F. K.-l. T. and Li, W.-S. (2014). Efficient location-aware influence maximization. In ACM SIGMOD International Conference on Management of Data (SIGMOD), Snowbird, UT, USA.
[10] J. Guo, P. Zhang, C. Z. Y. C. and Guo, L. (2013). Personalized influence maximization on social networks. In ACM international conference on information and knowledge management (CIKM), San Francisco, CA, USA.
[11] J. Leskovec, M. McGlohon, C. F. N. G. and Hurst, M. (2007). Cascading behavior in large blog graphs. Technical report, Carnegie Mellon University.
[12] Kempe, D., Kleinberg, J., and Tardos, E. (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, Washington, DC, USA.
[13] Lee, J.-R. and Chung, C.-W. (2015). A query approach for influence maximization on specific users in social networks. In IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING (TKDE), volume 27.
[14] Liben-Nowell, D. and Kleinberg, J. (2008). Tracing information flow on a global scale using internet chain-letter data. In Proceedings of the National Academy of Sciences, volume 105, page 46334638.
[15] P. Bhattacharya, M. B. Z. and Ganguly, N. (2014). Inferring user interests in the twitter social network. In ACM Conference on Recommender systems, pages 357-360, Foster City, Silicon Valley, CA, USA.
[16] Ramos, J. (1999). Using tf-idf to determine word relevance in document queries. Technical report, Department of Computer Science, Rutgers University.
[17] Robertson, S. (2004). Understanding inverse document frequency : On theoretical arguments for idf. Journal of Documentation, 60(5):503-520.
[18] S. Hangal, D. MacLean, M. S. L. and Heer, J. (2010). All friends are not equal: Using weights in social graphs to improve search. In the workshop on Social Network Mining and Analysis of international conference on Knowledge discovery and data mining, SNAKDD, Washington D.C. USA.
[19] S. Myers, C. Z. and Leskovec, J. (2012). Information diffusion and external influence in networks. In ACM SIGKDD international conference on Knowledge discovery and data mining, pages 33-41.
[20] Scheinkman, J. A. (2008). Social interactions. Technical report, Princeton University and NBER. Published in The New Palgrave Dictionary of Economics.
[21] Tang, S., Yuan, J., Mao, X., Li, X. Y., C., W., and Dai, G. (2011). Relationship classification in large scale online social networks and its impact on information propagation. In IEEE International Conference on Computer Communications (INFOCOM).
[22] W. Chen, C. W. and Wang, Y. (2010). Scalable influence maximization for prevalent viral marketing in large-scale social networks. In ACM SIGKDD international conference on Knowledge discovery and data mining (SIGKDD), pages 1029-1038.
[23] W. Chen, Y. W. and Yang, S. (2009). Efficient influence maximization in social networks. In Proc. 15th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, pages 199-208.
[24] Wang, W. and Street, W. N. (2014). A novel algorithm for community detection and influence ranking in social networks. In IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Iowa City, IA 52242, USA.
[25] Watts, D. J. (2002). A simple model of global cascades on random networks. In PNAS, volume 99.
[26] Y. Wang, G. Cong, G. S. and Xie, K. (2010). Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In ACM SIGKDD international conference on Knowledge discovery and data mining (SIGKDD), pages 1039-1048.
[27] Z. Lu, Y. W. and Cao, G. (2014). Information diffusion in mobile social networks: The speed perspective. In Proc. IEEE INFOCOM.
[28] Zongqing Lu, Y. W. and Cao, G. (2013). Community detection in weighted networks : Algorithms and applications. In Proc. of IEEE PerCom.
[29] Epinions webpage. http://epinions.com/.
[30] Facebook webpage. http://facebook.com/.
[31] Leskovec, J. Standford large network dataset collection. http://snap.stanford.edu/data/.
[32] Twitter webpage. http://twitter.com/.
[33] Wikipedia webpage. http://wikipedia.org/.