(34.201.11.222) 您好!臺灣時間:2021/02/25 04:21
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:伍峻億
研究生(外文):Chun-I Wu
論文名稱:有效率的影響力最大化演算法
論文名稱(外文):Efficient Algorithm For Influence Maximization
指導教授:陳以錚
指導教授(外文):Yi-Cheng Chen
口試委員:黃俊龍張世豪
口試委員(外文):Jiun-Long HuangShih-Hao Chang
口試日期:2017-05-26
學位類別:碩士
校院名稱:淡江大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:32
中文關鍵詞:病毒式行銷社群網路行銷影響力最大化演算法分群法
外文關鍵詞:Virtual marketingInfluence maximization problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:51
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著使用智慧型手機的人口快速增長,以及社群網路的蓬勃發展,病毒式行銷 以及社群網路行銷受到許多公司企業的愛戴,行銷人員常常需要尋找社群網路中具有影響力的個體來進行行銷,希望這些具影響力的人能將產品資訊傳遞給周圍的使用者,進而使整體的影響力最大化,如何找到有影響力的種子使用者成為時下熱門的議題,本論文提出了一套以社群結構為基礎的影響力最大化演算法,有效的減少影響力重疊的問題,同時加速演算法的執行,在真實的社群網路實驗結果中證實了此方法不僅能有效的保證結果的準確度,在執行效率以及擴展性上有著優越的表現。
Since the surge of the popularity of social network, recently, there has been a tremendous wave of interest in the investigation of influence maximization problem. Given a social network structure, the problem of influence maximization is to determine a minimum set of nodes that could maximize the spread of influences. Nowadays, due to the dramatic size growing of social network, the efficiency and scalability of algorithms for influence maximization become more and more crucial. Although many recent studies have focused on the problem of influence maximization, these works, in general, are time consuming when a large-scale social network is given. In this paper, by exploiting potential community structure, we develop an efficient algorithm EIM (standing for Efficient Influence Maximization) that reduces the execution time and memory usage while guarantee the accuracy of results. The experimental results on real datasets indicate that our algorithms not only significantly outperform state-of-the-art algorithms in efficiency but also possess graceful scalability.
Table of Contents

Chinese Abstract……………………………………………………….. I
Abstract……………………………………………………………… II
Table of Contents…………………………………………………….. IV
List of Figures……………………………………………………….. V
List of Tables……………………………………………………….. VI
List of Algorithms………………………………………………….. VII
Chapter 1 1
Introduction 1
Chapter 2 5
Preliminaries 5
2.1 Problem Formulation 5
Definition 1 (Social Network) 5
Definition 2 (Influence Maximization Problem) 6
2.2 Reverse Reachable Sampling(RRS) 6
Definition 3 (Reverse Reachable Set) 6
2.3 Tang et.al.’s enhancement on RRS 8
2.4 Observations 9
Chapter 3 11
Related Work 11
3.1 Diffusion Models 11
3.2 Influence Maximization Algorithms 12
Chapter 4 16
Proposed Solution 16
4.1 Graph partition 16
Definition 4 (Similarities Scores) 17
Definition 5 (Modularity) 18
4.2 Quota Allocation 18
4.3 Seed set generation 20
4.4 Performance Analytics 21
Chapter 5 22
Experiments 22
5.1 Experiment Settings 22
5.2 Experiment Result 23
Chapter 6 Conclusions 28
Reference 29



List of Figures

Fig. 1: An example of Reverse Reachable Sampling 7
Fig. 2: The Algorithm Flow. 16
Fig. 3: Influence spread on Epinions.. 23
Fig. 4: Running time on Epinions 24
Fig. 5: Influence spread on DBLP 24
Fig. 6: Running time on DBLP. 25
Fig. 7: Influence spread on LiveJournal. 26
Fig. 8: Running time on LiveJournal 27


List of Table

Tab. 1: Dataset characteristic 22


List of Algorithms

Algorithm. 1: Quota Allocation 19
[1] Y.C Chen, W.Y Zhu, W.C Peng, W.C Lee, and S.Y Lee. CIM: community based influence maximization in social networks. ACM Transactions on Intelligent Systems and Technology (TIST), vol. 5, no.2,
[2] D. Kempe, J. Kleinberg, and E. Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data
[3] Domingos. 2005. Mining social networks for viral marketing. IEEE Intell. Syst. 20, 1, 80–93.
[4] Domingos and M. Richardson. 2001. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’01). 57–66.
[5] Domingos and M. Richardson. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’02).61–70.
[6] Gomez-Rodriguez, J. Leskovec, and A. Krause. 2010. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (KDD’10). 1019–1028.
[7] Honglei Zhuang. Influence Maximization in Dynamic Social Networks
[8] Chayant Tantipathananandh, Tanya Berger-Wolf, David Kempe. A Framework For Community Identification in Dynamic Social Networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’07).
[9] Guangmo Tong, Student Member, IEEE. Adaptive Influence Maximization in Dynamic Social Networks
[10] Su-Chen Lin, Shou-De Lin, Ming-Syan 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).
[11] 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, 2011.
[12] Wen-Yuan Zhu, Wen-Chih Peng, Ling-Jyh Chen, Kai Zheng and Xiaofang 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).
[13] Yu Wang, Gao Cong, Guojie Song, Kunqing 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 in Data Mining (KDD’10).
[14] U. N. Raghavan, R. Albert, and S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. In Phys.Rev.E76, 2007.
[15] Brendan Lucier , Joel Oren , Yaron 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).
[16] C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, Portland, Oregon, USA
[17] Y. Tang, X. Xiao, and Y. Shi. Influence maximization. Near-optimal time complexity meets practical efficiency. In SIGMOD, 2014.
[18] Manuel Gomez-Rodriguez. Influence Maximization in Continuous Time Diffusion Networks. In Proceedings of the 29 th International Conference on Machine Learning, Edinburgh, Scotland, UK, 2012.
[19] Yajun Yang, Jeffrey Xu Yu, Hong Gao, Jian Pei, Jianzhong Li. Mining most frequently changing component in evolving graphs. World Wide Web (2014)
[20] Yu Yang, Zhefeng Wang, Jian Pei and Enhong Chen. Tracking Influential Nodes in Dynamic Networks
[21] ROGERS. 2003. Diffusion of Innovations. 5th Ed., Free Press, New York, NY.
[22] 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.
[23] 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.
[24] 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.
[25] Valente. 1995. Network Models of the Diffusion of Innovations. Hampton Press.
[26] Young. 2000. The diffusion of innovations in social networks. Economics Working Paper 437, Johns Hopkins University.
[27] Myers and J. Leskovec. 2010. On the convexity of latent social network inference. In Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS’10). 1741–1749.
[28] Wang and X. Feng. 2009. A potential-based node selection strategy for influence maximization in a social network. In Proceedings of the 5th International Conference on Advanced Data Mining and Applications (ADMA’09). 350–361.
[29] https://snap.stanford.edu/data/
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔