動態社群網路中影響力最大化預測

Influence Maximization Prediction on Dynamic Social Network

楊亞瀚(Ya-Han Yang)

指導教授 ： 王英宏

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

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

摘要

至今有關解決影響力最大化問題已經有許多的方法及文獻，這些方法和文獻都是基於貪婪演算法。不過，因為社群網路規模日趨龐大，因此使得演算法的效率及可擴展性越來越重要。近年來有關影響力最大化問題的研究也都著重於演算法的效率，但這些方法都是以分析靜態的資料(社群網路)為主。然而現今的社群網路成長速度非常快速，在社群網絡上每分每秒都有新的關係或互動產生，我們將之稱為動態社群網路。因此在本文中我們分析的對象主要是以動態社群網路為主，藉由觀察動態社群網路結構的變化，找出變化的規則並建構出一個模型，來預測未來的社群結構，最後利用有效率的演算法來解決影響力最大化問題。我們的實驗也證實了我們的預測模型有很高的精准度，並且藉由觀察動態社群網路所預測得到未來網路結構上能得到與靜態網路不同的使用者集合，並且能得到更大的影響力散播。

關鍵字

病毒式行銷 ； 社群網路行銷 ； 影響力最大化演算法 ； 連結預測

並列摘要

Up to now, much literature has focused on influence maximization problem. These methods and literature are all based on the greedy algorithm. However, social networks are growing rapidly, so the efficiency and scalability of the algorithm have become more important. In recent years, the study on the issue of influence maximization has also focused on the efficiency of the algorithm, but these studies are all based on the analysis of the static social network. However, every minute and second has new relationships or interaction on the social network, we describe this status as the dynamic social network. Therefore, in this paper, we focus on the analysis of the dynamic social network. By observing the changes in the dynamic social network structure, we can find out the pattern of variation and build a model to predict the future network structure. Eventually, using an efficient algorithm to solve the influence maximization problem based on the dynamic social network. The experimental results show that our prediction model has a high accuracy, we also can obtain a seed set different from the analysis of static social network and get more influence spreads.

並列關鍵字

Virtual marketing ； Influence maximization problem ； link prediction

參考文獻

[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, issue 2, article 25, 2014.

[2] W. Chen, C. Wang, and Y. Wang, “Scalable influence maximization for prevalent viral marketing in large-scale social networks,” Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD’10), pp. 1029-1038, 2010.

[3] D. Kempe, J. M. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’03), pp. 137-146, 2003.

[4] P. Domingos and M. Richardson, “Mining the network value of customers,” Proceedings of the 7th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 57-66, 2001.

[5] C. Chang, P. Yang, M. Lyu, and K. Chuang, “Influence Sustainability on Social Networks,” 2015 IEEE International Conference on Data Mining (ICDM), 2015.