臺灣博碩士論文加值系統

本論文呈現的是社群網路後進者的意見最大化策略。影響力最大化及意見最大化問題已擁有許多實用的應用，且已有許多廣泛的研究，然而，受限於許多社群網路上難以處理的複雜性質，影響力最大化的相關研究往往只考慮單一玩家，不巧的是，現實生活中我們時常必須面對目標網路中已存在另外的玩家的情況，此時，理解玩家之間如何競爭便成為一個十分重要的議題，為了補足這個領域所欠缺的知識，本論文呈現了後進者想達到影響力最大化可使用的策略，透過這些策略和其預見的結果，後進者可妥善評估當下最適合的選擇。

This thesis presents opinion maximization strategies for the second mover in social networks. Influence maximization and opinion maximization have many useful applications and there also have been extensive researches on them. However, due to complicated properties on social networks, researches on influence maximization often only consider single player. Unfortunately, in real world, we usually encounter scenarios that players have already existed in target network. Then, competence between players becomes one of the most significant considered issues. To fill the gap, this thesis presents strategies for second mover to maximize their influence. Through these strategies, the second mover would have several ways to evaluate what is the best for itself in present situation, and make decisions after foreseeing these results.

誌謝i
摘要ii
Abstract iii
List of Figures vi
List of Tables viii
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Opinion Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Influence Maximization . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Opinion Maximization . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 Organization of this thesis . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 System Model 7
2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Modularity of Influence . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Sub-modularity . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Giant Component and Percolation . . . . . . . . . . . . . . . . . . . . . 11
2.4 Settings and Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4.1 Spreading process . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4.2 Initial condition . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4.3 Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5.1 Degree centrality . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5.2 Betweenness centrality . . . . . . . . . . . . . . . . . . . . . . . 13
2.5.3 Eigenvector centrality . . . . . . . . . . . . . . . . . . . . . . . 13
2.6 Strategies by Intuitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6.1 Occupy and Attack . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6.2 Wall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6.3 Seeds Reinforcement . . . . . . . . . . . . . . . . . . . . . . . . 16
2.7 Proposed Algorithm: Current Vote . . . . . . . . . . . . . . . . . . . . . 16
3 Performance Evaluation 18
3.1 Experiment Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1 Facebook Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.2 Budget and Timing . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.3 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Experiment Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Occupy and Attack . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.2 Wall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.3 Betweenness Reinforcement . . . . . . . . . . . . . . . . . . . . 26
3.2.4 Degree Reinforcement . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.5 Eigenvector Reinforcement . . . . . . . . . . . . . . . . . . . . 30
3.2.6 Proposed Algorithm: Current Vote . . . . . . . . . . . . . . . . . 32
3.2.7 Comparison between Strategies . . . . . . . . . . . . . . . . . . 35
3.2.8 Comparison between Strategies at Different Entry Time . . . . . 36
3.2.9 Problem 2: Current Vote . . . . . . . . . . . . . . . . . . . . . . 37
4 Conclusion 42
Bibliography 45

[1] David Kempe, Jon Kleinberg, and Éva 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, pages 137–146. ACM, 2003.
[2] Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. Opinion maximization in social networks. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages 387–395. SIAM, 2013.
[3] AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi, Hamid Mahini, Saeed Seddighin, and Sadra Yazdanbod. Forming external behaviors by leveraging internal opinions. In Computer Communications (INFOCOM), 2015 IEEE Conference on, pages 1849–1857. IEEE, 2015.
[4] Jiuhua Zhao, Qipeng Liu, and Xiaofan Wang. Competitive dynamics on complex networks. Scientific reports, 4, 2014.
[5] Jiuhua Zhao, Qipeng Liu, Lin Wang, and Xiaofan Wang. Competitiveness maximization on complex networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016.
[6] Abhimanyu Das, Sreenivas Gollapudi, and Kamesh Munagala. Modeling opinion dynamics in social networks. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 403–412. ACM, 2014.
[7] Morris H DeGroot. Reaching a consensus. Journal of the American Statistical Association, 69(345):118–121, 1974.
[8] Rainer Hegselmann, Ulrich Krause, et al. Opinion dynamics and bounded confidence models, analysis, and simulation. Journal of artificial societies and social simulation, 5(3), 2002.
[9] Gérard Weisbuch, Guillaume Deffuant, Frédéric Amblard, and Jean-Pierre Nadal. Meet, discuss, and segregate! Complexity, 7(3):55–63, 2002.
[10] Peter Clifford and Aidan Sudbury. A model for spatial conflict. Biometrika, 60(3): 581–588, 1973.
[11] Richard A Holley and Thomas M Liggett. Ergodic theorems for weakly interacting infinite systems and the voter model. The annals of probability, pages 643–663, 1975.
[12] Mehmet E Yildiz, Roberto Pagliari, Asuman Ozdaglar, and Anna Scaglione. Voting models in random networks. In Information Theory and Applications Workshop (ITA), 2010, pages 1–7. IEEE, 2010.
[13] Ercan Yildiz, Daron Acemoglu, Asuman E Ozdaglar, Amin Saberi, and Anna Scaglione. Discrete opinion dynamics with stubborn agents. 2011.
[14] David Kempe, Jon Kleinberg, Sigal Oren, and Aleksandrs Slivkins. Selection and influence in cultural dynamics. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC ’13, pages 585–586, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-1962-1. doi: 10.1145/2482540.2482566. URL http://doi.acm.org/10.1145/2482540.2482566.
[15] Wei Chen, Chi Wang, and Yajun 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, pages 1029–1038. ACM, 2010.
[16] Tim Carnes, Chandrashekhar Nagarajan, Stefan M Wild, and Anke Van Zuylen. Maximizing influence in a competitive social network: a follower’s perspective. In Proceedings of the ninth international conference on Electronic commerce, pages 351–360. ACM, 2007.
[17] Shishir Bharathi, David Kempe, and Mahyar Salek. Competitive influence maximization in social networks. Internet and Network Economics, pages 306–311, 2007.
[18] Mark Newman. Networks: an introduction. Oxford university press, 2010.
[19] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.