系統識別號 | U0002-0307201820564400 |
---|---|
DOI | 10.6846/TKU.2018.00085 |
論文名稱(中文) | 社群網路效能影響力最大化演算法 |
論文名稱(英文) | A Novel Algorithm for Efficient Influence Maximization in Social Networks |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 資訊工程學系碩士班 |
系所名稱(英文) | Department of Computer Science and Information Engineering |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 106 |
學期 | 2 |
出版年 | 107 |
研究生(中文) | 莊孟修 |
研究生(英文) | Meng-Shiu Chaung |
學號 | 606410057 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2018-06-29 |
論文頁數 | 35頁 |
口試委員 |
指導教授
-
王英宏(inhon@mail.tku.edu.tw)
委員 - 陳以錚(ycchen@mgt.ncu.edu.tw) 委員 - 惠霖(121678@mail.tku.edu.tw) 委員 - 王英宏(inhon@mail.tku.edu.tw) |
關鍵字(中) |
病毒式行銷 社群網路行銷 影響力最大化演算法 分群 |
關鍵字(英) |
Virtual marketing Influence maximization problem Cluster |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
由於社群網路日漸普遍,這也引起了學術界對尋找影響力最大化問題的風潮。最早的影響力最大化問題是由Kempe.Kleinberg和Tardosy在2003提出。給定一個社群網路G和常數k,在G中找出k個點,可以在擴散模型下去影響最多的使用者。由於社群網路越來越龐大,先前的演算法在這種情形下,不論在IC或LT 模型都需耗費較多的時間來執行,而且這些演算法並沒有良好的可擴展性。本篇方法透過給定邊一個確定性的值(α),並開發出一個有效率的演算法,不但可以減少執行所需要的時間,同時也保證結果的準確性,並且在實驗結果上表明,我們的演算法優於先前的演算法,並且具有良好的可擴展性。 |
英文摘要 |
The Social Network is becoming more and more common. This has also caused the wave to find influence maximization problem by the academic community. The earliest Influence maximization problem was proposed by Kempe.Kleinberg and Tardosy in 2003. Given a social network G and a constant k, finding k nodes in G which can influence most nodes in the diffusion model. As the Social Network is getting larger, the previous algorithms in this case, whether in the IC or the LT Model, take more time to execute, and these algorithms do not have good Scalability. The method in this paper given a deterministic value for edges and develops an efficient algorithm. It not only can reduce the time required for implementation, but also ensures the accuracy of results. And the experimental results show that our algorithm is better than the previous algorithm, and has good scalability. |
第三語言摘要 | |
論文目次 |
Table of Contents Chapter 1 1 Introduction 1 Chapter 2 5 Preliminaries 5 2.1 Problem Formulation 5 2.2 Reverse Reachable Sampling(RRS) 7 2.3 Tang et.al.’s enhancement on RRS 9 2.4 Chen et al.’s MIA Model 11 2.5 Observations 12 Chapter 3 14 Related Work 14 3.1 Diffusion Models 14 3.2 Influence Maximization Algorithms 15 Chapter 4 17 Proposed Solution 17 4.1 Graph partition 18 4.2 Quota Allocation 20 4.3 Calculateα 22 4.4 Seed Set Generation 23 Chapter 5 25 Experiments 25 5.1 Experiment Settings 25 5.2 Experiment Result 26 Chapter 6 31 Conclusions 31 References 32 List of Figures FIGURE 1:CASES OF REVERSE REACHABLE SAMPLES 8 FIGURE 2:THE ALGORITHM FLOW. 17 FIGURE 3:RUNNING TIME VS. K ON EMAIL-EU-CORE. 26 FIGURE 4:RUNNING TIME VS. K ON EPINIONS. 28 FIGURE 5:RUNNING TIME VS. K ON YOUTUBE. 29 List of Table TABLE 1:PROPERTIES OF SOCIAL NETWORK DATASETS 26 TABLE 2:RUNNING TIME ON EMAIL-EU-CORE 27 TABLE 3:INFLUENCE SPREAD ON EMAIL-EU-CORE 27 TABLE 4:RUNNING TIME ON EPINIONS 28 TABLE 5:INFLUENCE SPREAD ON EPINIONS 28 TABLE 6:RUNNING TIME ON YOUTUBE 29 TABLE 7:INFLUENCE SPREAD ON YOUTUBE 30 List of Algorithm Algorithm 1 : Quota Allocation 21 Algorithm 2 : ap(u,S,MIIA(v,θ)) 22 Algorithm 3 : Compute α(v,u) 22 Algorithm 4 : Proposed 24 |
參考文獻 |
[1] D. Kempe, J. M. Kleinberg, and É. Tardos. “Maximizing the spread of influence through a social network”. In KDD, pages 137–146, 2003. [2] S.C Lin, S.D Lin, M.S Chen. “A Learning-based Framework to Handle Multi-round Multi-party Influence Maximization on Social Networks”. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’15). [3] W.Y Zhu, W.C Peng, L.J Chen, K. Zheng and X. Zhou. “Modeling User Mobility for Location Promotion in Location-based Social Networks”. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’15). [4] B. Lucier , J. Oren , Y. Singer. “Influence at Scale: Distributed Computation of Complex Contagion in Networks”. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’15). [5] Y. Yang, Z. Wang, J. Pei, E. Chen."Tracking influential nodes in dynamic networks",Proceedings of the 2015 SIAM international conference on data mining, Canada, Vancouver (2015). [6] C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier. “Maximizing social influence in nearly optimal time”. In SODA, Portland, Oregon, USA. [7] Y. Tang, X. Xiao, and Y. Shi. “Influence maximization. Near-optimal time complexity meets practical efficiency”. In SIGMOD, 2014. [8] Estevez, P. Vera, and K. Saito. 2007. “Selecting the most influential nodes in social network”. In Proceedings of the International Joint Conference on Neural Networks (IJCNN’07). 2397–2402. [9] Goldenberg, B. Libai, and E. Muller. 2001. “Talk of network: A complex systems look at the underlying process of word-of-mouth”. Market. Lett. 12, 3, 211–223. [10] Ma, H. Yang, M. Lyu, and I. King. 2008. “Mining social networks using heat diffusion processes for marketing candidates selection”. In Proceedings of the 17th ACM Conference on Information and Knowledge Management (CIKM’08). 233–242. [11] Valente. 1995. “Network Models of the Diffusion of Innovations”. Hampton Press, 2015. [12] H. P Young. “The diffusion of innovation in social networks”. Sante Fe Institute Working Paper 02-04-018, 2002. ROGERS. 2003. Diffusion of Innovations. 5th Ed., Free Press, New York, NY. [13] M. Kimura and K. Saito. “Tractable models for information diffusion in social networks”. In Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, pages 259–271, 2006. [14] W. Chen , Y. Wang , S. Yang, “Efficient influence maximization in social networks”, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France [15] W. Chen, C. Wang, Y. Wang, “Scalable influence maximization for prevalent viral marketing in large scale social networks”, KDD, 2010. [16] C. Long , Raymond C.W Wong, “Minimizing Seed Set for Viral Marketing”, Proceedings of the 2011 IEEE 11th International Conference on Data Mining, p.427-436, December 11-14, 2011 [17] P. Zhang, W. Chen, X. Sun, Y. Wang, J. Zhang, “Minimizing seed set selection with probabilistic coverage guarantee in a social network”, KDD, pp. 1306-1315, 2014. [18] A. Goyal, F. Bonchi, L. V. S. Lakshmanan, and S. Venkatasubramanian. “On minimizing budget and time in influence propagation over social networks”. Social Network Analysis and Mining, 2(1), 2012. [19] Zheng, D., Liu, J., Li, R., Aslay, Ç., Chen, Y., Huang, X.: “Querying intimate-core groups in weighted graphs”. In: 11th IEEE International Conference on Semantic Computing, ICSC 2017, San Diego, CA, USA, 30 January–1 February 2017 (2017) [20] J. Leskovec , A. Krause , C. Guestrin , C. Faloutsos , J. VanBriesen , N. Glance, “Cost-effective outbreak detection in networks”, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [21] Z. Yu et al., “Who should I invite for my party?: Combining user preference and influence maximization for social events”, Proc. ACM Int. Joint Conf. Pervasive Ubiquitous Comput., pp. 879-883, 2015. [22] A. Goyal, F. Bonchi, L. V. Lakshmanan, “A data-based approach to social influence maximization”, PVLDB, 2012. [23] https://snap.stanford.edu/data/ |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信