有效率的影響力最大化演算法

Efficient Algorithm For Influence Maximization

伍峻億(Chun-I Wu)

指導教授 ： 陳以錚

淡江大學/工學院/資訊工程學系碩士班/碩士(2017年)

https://doi.org/10.6846/TKU.2017.00135

摘要

隨著使用智慧型手機的人口快速增長，以及社群網路的蓬勃發展，病毒式行銷 以及社群網路行銷受到許多公司企業的愛戴，行銷人員常常需要尋找社群網路中具有影響力的個體來進行行銷，希望這些具影響力的人能將產品資訊傳遞給周圍的使用者，進而使整體的影響力最大化，如何找到有影響力的種子使用者成為時下熱門的議題，本論文提出了一套以社群結構為基礎的影響力最大化演算法，有效的減少影響力重疊的問題，同時加速演算法的執行，在真實的社群網路實驗結果中證實了此方法不僅能有效的保證結果的準確度，在執行效率以及擴展性上有著優越的表現。

關鍵字

病毒式行銷 ； 社群網路行銷 ； 影響力最大化演算法 ； 分群法

並列摘要

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.

並列關鍵字

Virtual marketing ； Influence maximization problem

參考文獻

[3] Domingos. 2005. Mining social networks for viral marketing. IEEE Intell. Syst. 20, 1, 80–93.

[7] Honglei Zhuang. Influence Maximization in Dynamic Social Networks

[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.