在未標記資料上利用增強式學習解決影響力最大化之問題

Exploiting Reinforcement-Learning for Influence Maximization without Human-Annotated Data

黃彥樺(Yen-Hua Huang)

指導教授 ： 林守德

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.02713

摘要

在影響力最大化的研究上近幾十年間已有大量以策略導向進行選擇的方式之研究。在其中已證明貪婪演算法(Greedy Algorithm)能夠達到至少涵蓋63%以上的最大擴散範圍，因此是個非常強大且有競爭力的演算法。在此我們提出以學習為主框架的方式來解決影響力最大化問題，目標是超越貪婪演算法的影響範圍和效率。我們提出的增強式學習架構與分類器相結合的模型，不僅減輕了資料上所需標記的訓練數據，而且還允許逐步發展的影響最大化的策略，能夠在每個狀況下找出其適合的策略，最後的表現不論在執行時間和影響範圍都打敗貪婪演算法。

關鍵字

增強式學習 ； 社群網路 ； 訊息傳播最大化 ； 機器學習 ； 貪婪演算法

並列摘要

Strategies to choose nodes on a social network to maximize the total influence has been studied for decades. Studies have shown that the greedy algorithm is a competitive strategy and it has been proved to cover at least 63% of the optimal spread. Here we propose a learning-based framework for influence maximization aiming at outperforming the greedy algorithm in terms of both coverage and efficiency. The proposed reinforcement learning framework combining with a classification model not only alleviates the requirement of the labelled training data, but also allows the influence maximization strategy to be developed gradually and eventually outperforms a basic greedy approach.

並列關鍵字

Reinforcement-Learning ； Social network ； Influence Maximization ； Machine learning ； Greedy Algorithm

參考文獻

[4] W. Chen, Y. Wang, and S. Yang, “Efficient influence maximization in social networks," in ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2009.

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

[8] R. Bellman. A Markovian Decision Process. Journal of Mathematics and Mechanics 6, 1957.

[9] S.-C. Lin , S.-D. Lin , and M.-S. Chen, “A Learning-based Framework to Handle Multi-round Multi-party Influence Maximization on Social Networks” , in ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2015

[1] D. Kempe, J. Kleinberg , and E. Tardos ,”Maximizing the spread of influence through a social network” in ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2003