Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/60253
|
| Title: | 在有限的預算下找出影響力最大的代言人組合
Mining a set of agents in social networks for maximal influence with a limited budget |
| Authors: | 龔偉銘 |
| Contributors: | 陳良弼
龔偉銘 |
| Keywords: | 影響力
社群網路 |
| Date: | 2010 |
| Issue Date: | 2013-09-04 17:08:44 (UTC+8) |
| Abstract: | 近年來，越來越多的社群網站受到人們廣泛的使用，例如：Facebook、Plurk之類的網站都擁有大量的使用者資料。社群網路越來越受到一些研究學者的重視，很多人開始紛紛研究如何有效的運用社群網路上的資料。影響力的傳播是社群網路上一個很重要的課題，如何在社群網路上找到影響力最大的組合是個受到廣泛討論的問題。在本研究中，我們試想一間公司如果要請人來宣傳產品的話，必須支付代言人一些費用，而如何在有限的預算下聘請一些代言人來達到最大的宣傳效果就是我們研究的問題。兩個代言人的影響力總和並不單單只是將兩個代言人的影響力相加而已，因為代言人本身所影響的對象可能會重複，所以必須扣除掉一些被重複影響的人，也增加了問題的困難度。在我們提出的演算法中，可以有效的減少計算的時間並且使找出來的代言人組合所造成的影響力趨近最佳解。
Influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. In this paper, we given a social network and budget, which people should we choose could maximize the spread of influence with a limit budget. We propose a new algorithm combine cluster algorithm and dynamic programming to solve this problem.
Our experimental results show that our propose algorithm achieves better running time comparing with the CELF algorithm. But CELF algorithm achieve much better influence spread than our propose algorithm. Based on our results, we believe if we can improve the cluster algorithm than we can achieve much better influence spread. |
| Reference: | [1] D. Kempe, J. Kleinberg, and E.Tardos. Maximizing the Spread of Influence through a Social Network. In SIGKDD 2003.
[2] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In SIGKDD 2007.
[3] W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In SIGKDD 2009.
[4] Y. Wang, G. Cong, G. Song, and K. Xie. Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks. In SIGKDD 2010.
[5] B. Zhou and J. Pei. Preserving Privacy in Social Networks Against Neighborhood Attacks. In ICDE 2008.
[6] N. Shrivastava, A. Majumder and R. Rastogi. Mining (Social) Network Graphs to Detect Random Link Attacks. In ICDE 2008.
[7] W. Chen, Y. Yuan and L. Zhang. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In ICDM 2010.
[8] A. Krause, J. Leskovec, C. Guestrin, J. VanBriesen,and C. Faloutsos. Efficient sensor placement optimization for securing large water distribution networks. Water Resources Planning Management 2008.
[9] X. Xu, N. Yuruk, Z. Feng, T. A. J. Schweiger. SCAN: A Structural Clustering Algorithm for Network. In SIGKDD 2007 |
| Description: | 碩士
國立政治大學
資訊科學學系
98753025
99 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0098753025 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| 302501.pdf | 873Kb | Adobe PDF2 | 464 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
