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

Abstract

在影響力最大化的研究上近幾十年間已有大量以策略導向進行選擇的方式之研究。在其中已證明貪婪演算法(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.