請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57193完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 廖婉君(Wanjiun Liao) | |
| dc.contributor.author | Li-Yang Cheng | en |
| dc.contributor.author | 鄭立揚 | zh_TW |
| dc.date.accessioned | 2021-06-16T06:37:27Z | - |
| dc.date.available | 2019-08-01 | |
| dc.date.copyright | 2014-08-01 | |
| dc.date.issued | 2014 | |
| dc.date.submitted | 2014-07-31 | |
| dc.identifier.citation | [1] Pedro Domingos and Matt Richardson. Mining the network value of customers. In
Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 57–66. ACM, 2001. [2] Matthew Richardson and Pedro Domingos. Mining knowledge-sharing sites for viral marketing. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 61–70. ACM, 2002. [3] David Kempe, Jon Kleinberg, and Eva 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. [4] Masahiro Kimura and Kazumi Saito. Tractable models for information diffusion in social networks. In Knowledge Discovery in Databases: PKDD 2006, pages 259– 271. Springer, 2006. [5] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne Van- Briesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 420–429. ACM, 2007. [6] N Rama Suri and Y Narahari. Determining the top-k nodes in social networks using the shapley value. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 3, pages 1509–1512. International Foundation for Autonomous Agents and Multiagent Systems, 2008. 36 [7] Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199–208. ACM, 2009. [8] Yu Wang, Gao Cong, Guojie Song, and 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 and data mining, pages 1039–1048. ACM, 2010. [9] Amit Goyal, Wei Lu, and Laks VS Lakshmanan. Celf++: optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on World wide web, pages 47–48. ACM, 2011. [10] Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, and Antti Ukkonen. Sparsification of influence networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 529–537. ACM, 2011. [11] Chi Wang, Wei Chen, and Yajun Wang. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 25(3):545–576, 2012. [12] Yanhua Li, Wei Chen, Yajun Wang, and Zhi-Li Zhang. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In Proceedings of the sixth ACM international conference on Web search and data mining, pages 657–666. ACM, 2013. [13] Xiaoguang Fan, Guolin Niu, and Victor OK Li. An analytical model for the propagation of social influence. In Web Intelligence (WI) and Intelligent Agent Technologies (IAT), 2013 IEEE/WIC/ACM International Joint Conferences on, volume 1, pages 1–8. IEEE, 2013. 37 [14] Gerard Cornuejols, Marshall L Fisher, and George L Nemhauser. Exceptional paperlocation of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management science, 23(8):789–810, 1977. [15] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functionsxi. Mathematical Programming, 14(1):265–294, 1978. [16] Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1):107–117, 1998. [17] Leonard Kaufman and Peter J Rousseeuw. Finding groups in data: an introduction to cluster analysis, volume 344. John Wiley & Sons, 2009. [18] Sergios Theodoridis and Konstantinos Koutroumbas. Pattern Recognition. Elsevier Academic press, USA, 2006. [19] Hae-Sang Park and Chi-Hyuck Jun. A simple and fast algorithm for k-medoids clustering. Expert Systems with Applications, 36(2):3336–3341, 2009. [20] Amit Goyal, Francesco Bonchi, and Laks VS Lakshmanan. Learning influence probabilities in social networks. In Proceedings of the third ACM international conference on Web search and data mining, pages 241–250. ACM, 2010. [21] Manuel Gomez Rodriguez, Jure Leskovec, and Andreas Krause. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1019–1028. ACM, 2010. [22] Elchanan Mossel and Sebastien Roch. On the submodularity of influence in social networks. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 128–134. ACM, 2007. [23] Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM (JACM), 23(3):555–565, 1976. 38 [24] Nimrod Megiddo and Kenneth J Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182–196, 1984. [25] Stuart Lloyd. Least squares quantization in pcm. Information Theory, IEEE Transactions on, 28(2):129–137, 1982. [26] David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027–1035, 2007. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57193 | - |
| dc.description.abstract | 在病毒式行銷網路中一個常見的問題是影響力最大化問題。此問
題為如何在有限資源下從人群中找出具有影響力的人，使其能影響整 個網路中最多的人。這個問題已被證明是NP-Hard 的問題。貪婪演算 法不僅能保證有(1 − 1/e) 最佳近似解，而且貪婪演算法在其他啟發性 演算法中表現為最好的。但是，貪婪演算法在大型網路中的計算複雜 度非常高。因此，目前許多研究都注重在表現和計算時間的取捨。跟 其他多數的研究不同的是，我們想知道我們是否有辦法擊敗(或是改 善) 貪婪演算法的表現但又不需要額外增加太多的計算量。藉由把影 響力最大化問題對照到k-medians 問題，我們推導出影響力最佳化問 題可以轉換為k-medians 中找出最佳的k 個medoid 問題。基於此，我 們提出KMIC 演算法利用k-medians 的方式解決在independent cascade model 上的影響力最大化問題。我們的實驗顯示(1) 利用貪婪演算法的 結果當作KMIC 演算法的初始點，是有機會改善貪婪演算法的表現(2) 在一個比較緊密連結的網路中適當選取KMIC 演算法的初始點，亦可 以改善貪婪演算法的表現(3)KMIC 演算法適用在大型網路中。 | zh_TW |
| dc.description.abstract | One of the essential problems for viral marketing is the influence maximization problem that finds a small set of seed people to maximize their influence in the whole social network. Such a problem is known to be NP-hard and it is also known that the greedy algorithm not only achieves (1 − 1/e)-approximation for the influence maximization problem but also yields larger influence than the other heuristic algorithms in the literature. By mapping the influence maximization problem to a k-medians problem, we show that the difference between the optimal influence and the influence deduced from the optimal k medoids of the corresponding k-medians problem can be bounded by a constant. Based on this, we propose the KMIC algorithm for the influence maximization problem in the Independent Cascade model. Our experiments show that (i) it is possible to improve the performance of the greedy algorithm by using the output of the greedy algorithm as the initial setting of the KMIC algorithm, (ii) it is also possible to beat the performance of the greedy algorithm for a densely connected network by choosing an appropriate initial setting of the KMIC algorithm, and (iii) the KMIC algorithm is applicable for large networks. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T06:37:27Z (GMT). No. of bitstreams: 1 ntu-103-R01921057-1.pdf: 478222 bytes, checksum: 0ffd8645ff863ee1354ede52bf1d39ca (MD5) Previous issue date: 2014 | en |
| dc.description.tableofcontents | 1 Introduction 1
2 Review of the independent cascade model 8 2.1 The model 8 2.2 Submodularity of the influence function 10 2.3 Estimating the influence 11 3 Bounds for the influence function 12 4 A k-medians approach for influence maximization 15 4.1 An assumption on small secondary influence probabilities 15 4.2 A distance metric 16 4.3 A k-medians problem 18 5 The KMIC algorithm 21 5.1 Estimating distance measures 21 5.2 The k-medoids algorithm 22 5.3 The algorithm 23 6 Experiments 26 6.1 Experiment setup 26 6.2 Experiment results 28 7 Conclusions 34 8 Proof of Lemma 2 35 Bibliography 36 | |
| dc.language.iso | en | |
| dc.title | 大型社群網路中影響力最大化的效率演算法 | zh_TW |
| dc.title | A k-medians Approach for Influence Maximization in Large
Social Networks | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 102-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 張正尚(Cheng-Shang Chang) | |
| dc.contributor.oralexamcommittee | 陳銘憲(Ming-Syan Chen),陳和麟(Ho-Lin Chen),林軒田(Hsuan-Tien Lin) | |
| dc.subject.keyword | 影響力最大化,社群網路,網路科學,群聚演算法, | zh_TW |
| dc.subject.keyword | Influence Maximization, Social Network,Network Science,Clustering Algorithms, | en |
| dc.relation.page | 39 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2014-07-31 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-103-1.pdf 目前未授權公開取用 | 467.01 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。