臺灣博碩士論文加值系統

Social influence is an important phenomenon in social networks. Information can be propagated through users in social networks since people are easily influenced by their friends when making decisions. A user is said to be influenced by his/her friends if this user performs the same action after his/her friends do it. This phenomenon is just like a virus which may spread over the entire network. As a result, the so-called viral marketing has become an interesting marketing strategy in social networks. This problem of influence maximization is to find a small set of users that maximize the spread of influence throughout the social network. Different from the top-k query problem, the maximization problem needs to consider the overlapping of influence spread among users. Recently, many approaches are proposed to solve this problem under different influence cascade models. However, since the size of the data in social networks is usually large, those approaches always need very long processing time. In this thesis, we propose an efficient algorithm based on a pruning strategy which can effectively decrease the size of the data in advance. Moreover, a series of experiments are performed to evaluate the proposed algorithm. The experiment results reveal that our method outperforms the previous works.

社會影響力在社會網絡中是個重要的現象。各種資訊在社會網絡中能夠在使用者之間傳遞，因此使用者在決策時容易受到他們朋友的影響。當一個使用者在他/她的朋友執行了某一個動作之後執行了相同的動作，這個使用者就稱為被他/她的朋友所影響。這個現象就像病毒一樣會散撥到整個網絡之中。因此，在社會網絡中，所謂的病毒式行銷就成了一個令人感興趣的行銷策略。影響力最大化的這個問題是希望找到一小群使用者可以在整個社會網絡上擁有最大的影響範圍。與top-K問題不同之處在於最大化的問題必須考慮使用者與使用者之間重複的部份。近年來，許多的方法在不同的模型之下被提出用以解決這個問題。然而，由於社會網絡的資料量通常都是非常龐大的，這些方法都需要非常冗長的執行時間。在這篇論文中，我們提供了一個基於削減策略的演算法，可以有效率的提前減少資料量的大小。除此之外，我們進行了一系列的實驗來評估這個演算法，而實驗結果也顯示我們的方法是優於其他之前的方法的。

Acknowledgement i
Abstract ii
Table of Contents iii
List of Figures iv
1 Introduction 1
2 Related Works 5
3 Preliminaries 8
3.1 Problem Definition 8
3.2 Kernel Ideas 13
4 ECE Algorithm 18
4.1 Process on finding Lower Bound 18
4.2 The ECE Algorithm 21
5 Performance Evaluation 23
5.1 Experiment Setup 23
5.2 Experiment Results 25
6 Conclusions 30
References 31

[1] A. Anagnostopoulos, R. Kumar, and M. Mahdian. Influence and Correlation in Social Networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2008, Las Vegas, Nevada, USA, pp. 7-15.
[2] N. Agarwal, H. Liu, L. Tang, and P. S. Yu. Identifying the Influential Bloggers in a Community. In Proceedings of the International Conference on Web Search and Web Data Mining, WSDM2008, Palo Alto, California, USA, pp. 207-218.
[3] J. Brown and P. Reinegen. Social Ties and Word-of-Mouth Referral Behavior. Journal of Consumer Research 14, 3 (December, 1987) pp. 350-362.
[4] W. Chen, Y. Wang, and S. Yang. Efficient Influence Maximization in Social Networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2009, Paris, France, pp. 199-208.
[5] W. Chen, C. Wang, and Y. Wang. 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, KDD2010, Washington, DC, USA, pp. 1029-1038.
[6] P. Domingos and M. Richardson. Mining the Network Value of Customers. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2001, San Francisco, CA, USA, pp. 57-66.
[7] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. Discovering Leaders from Community Actions. In Proceedings of the 17th ACM Conference on Information and Knowledge Management, CIKM2008, Napa Valley, California, USA, pp. 499-508.
[8] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. Learning Influence Probabilities in Social Networks. In Proceedings of the Third International Conference on Web Search and Web Data Mining, WSDM2010, New York, NY, USA, pp. 241-250.
[9] D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the Spread of Influence through a Social Network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2003, Washington, DC, USA, pp. 137-146.
[10] J. Leskovec. Stanford Large Network Dataset Collection. http://snap.stanford.edu/data/
[11] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective Outbreak Detection in Networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2007, San Jose, California, USA, pp. 420-429.
[12] T. Lappas, E. Terzi, D. Gunopulos, and H. Mannila. Finding Effectors in Social Networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2010, Washington, DC, USA, pp. 1059-1068.
[13] M. Mathioudakis and N. Koudas. Efficient Identification of Starters and Followers in Social Media. In Proceedings of the 12th International Conference on Extending Database Technology, EDBT2009, Saint Petersburg, Russia, pp. 708-719.
[14] M. Richardson and P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2002, Edmonton, Alberta, Canada, pp. 61-70.
[15] J. Tang, J. Sun, C. Wang, and Z. Yang. Social Influence Analysis in Large-scale Networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2009, Paris, France, pp. 807-816.
[16] Y. Wang, G. Cong, G. Song, and K. Xie. Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2010, Washington, DC, USA, pp. 1039-1048.