近年來，越來越多的社群網站受到人們廣泛的使用，例如：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.
| Identifer | oai:union.ndltd.org:CHENGCHI/G0098753025 |
| Creators | 龔偉銘 |
| Publisher | 國立政治大學 |
| Source Sets | National Chengchi University Libraries |
| Language | 中文 |
| Detected Language | English |
| Type | text |
| Rights | Copyright © nccu library on behalf of the copyright holders |
Page generated in 0.0015 seconds