透過您的圖書館登入
IP:54.196.105.235
  • 學位論文

利用學習方法解決社群網絡的競爭影響力最大化

Learning-based Approaches to Tackle Competitive Influence Maximization on Social Networks

指導教授 : 王志宇 陳宜欣

摘要


企業以及社群使用者為了各種目的大量的使用社群網絡。使用者利用貼文,推特,部落格分享他們的生活或想法,也用於尋找他人推薦的景點,推薦的手機等等。相反的,企業利用社群網絡來推廣他們的產品,或是即將舉辦的活動等等。在使用者與企業如此大量使用社群網絡的情況之下,吸引了研究人員針對社群網絡進行研究並提出他們的看法。在社群網絡中最主要的研究主題是“影響力最大化”,而這個主題已經有許多相關的研究發表. 影響最大化(IM)難題是要找出在社交網絡中有關鍵影響力的使用者,這些使用者在社群中推播訊息並且吸引大量的使用者購買此產品。影響最大化(IM)難題又可以延生出更符合實際情況的難題,競爭影響最大化(CIM)難題,是由多方在社群網絡上推銷類似的產品,而都是為了追求整體的最大利潤。競爭影響最大化(CIM)難題已經利用延伸後的傳統IM模型,賽局理論與強化學習(RL)模型解決。然而,現有的模型是應用在假設相對單純的場景,其中使用者之間的關係與影響不會隨著時間改變,並且只在意使用者最後分到多少市場,並沒有針對推廣活動給予期限或其他限制。現有的研究沒有辦法解決社群網絡在時間上的限制與時序問題。除此之外,只要社交網絡有變化,現在CIM難題的RL模型就需要重新訓練,導致需要花大量的計算資源與計算時間在重新訓練社群網絡。除了RL模型在計算時間上的問題,因為RL模型透過狀態(state)以及動作(action)來累積知識,而在網絡變大時導致狀態與動作空間會增加到一個可觀的大小。此外,現有的RL模型假設模型可以看見完整的網絡拓墣,以便於模型訓練以及找到最佳策略。當社群網絡資料不是完全已知與可見之下,而我們需要透過搜索整個網絡去找出關鍵有影響力的使用者,是非常不切實際的方法. 為了解決以上提到的問題,我們提出了一個建立於強化學習的通用框架,稱為種子組合與種子選擇(SCSS),以解決受時間限制的競爭影響最大化對於社群網絡的影響。SCSS框架使用新的巢狀Q學習(NSQ)演算法來找到最佳策略,包括何時選擇有影響力的使用者以及如何選擇(考慮時間方面以及其他各方面的預算以及截止日期,同時也要考慮到競爭者的已知和未知的策略)。除此之外,我們利用RL中的遷移學習來解決競爭影響力最大化,從中促進RL模型延長在社群網絡新目標上的訓練時間。考慮到網絡的競爭與時間,我們提出的遷移學習在不同網絡上學習過去的知識,並將知識應用在新的目標網絡上找到最佳策略。而我們提出了一種基於深度強化學習(DRL)的模型,以克服網絡變大時RL模型狀態與動作空間(state-action space)增大。我們提出的模型利用社群網絡的社群結構來找到最佳的訊息傳播策略。最後,我們提供了一種基於DRL設計的模型,以解決未知社群網絡上競爭影響力最大化的問題。我們提出基於DRL設計的模型需要學習的策略,包括何時搜索網絡以及何時從所搜索的網絡中選擇有關鍵影響力的使用者。另外,為了提高DRL模型在未知社群網絡的訓練效率,我們在深度強化學習中採用了遷移學習,以解決未知社群網絡上競爭影響最大化難題.

並列摘要


Companies, as well as users, widely use social networks for various purposes. Users share their daily life activities or opinions through posts, tweets, blogs, asks for recommendations to visit places, buy mobile phones, and so on. In comparison, companies leverage social networks to promote their products, upcoming events, and more. Such massive adoption by users and companies has attracted researchers to conduct research and share new social network analysis insights. One of the prominent research topics on the social network analysis domain is the ``Influence Maximization'' that has attracted ample research publications. The influence maximization (IM) problem is to identify the key influential users in a social network who can propagate the information in the social network with the hope that a large number of users will buy the product. Competitive Influence Maximization (CIM) is a more realistic and natural extension of the IM problem where multiple parties propagate similar products in the social network to maximize their respective profit. The CIM problem has been addressed by extending traditional IM-based models, leveraging game theory, and reinforcement learning-based (RL) models. However, existing models assume relatively simple scenarios that the user's relations and their influences remain constant with time and parties are only concerned with eventual market share with no deadline or restrictions imposed on their campaign. Existing studies do not address the time-constrained and temporal aspects of the social network. Besides, existing RL models for the CIM problem require to train from scratch even with a slight change in the social network, which results in substantial computational resources and training time to train the model from scratch on a network. In addition to RL models' training time concerns, RL models accumulate knowledge through (state, action) pairs resulting in a sizeable state-action space growth when the networks get large. Moreover, existing RL models assume that the complete network topology is visible for models to train and find the optimal strategy. That is impractical when the social network data is not entirely known/visible and requires exploring the network to find key influential users for information propagation. To address the aforementioned issues, we propose a general reinforcement learning-based framework, termed as Seed-Combination and Seed-Selection (SCSS), to tackle the time-constrained competitive influence maximization on a social network in this dissertation. SCSS framework employs the novel nested Q-learning (NSQ) algorithm to find an optimal policy, consisting of when to select influential users and how to select, given the temporal aspects and parties budget and deadline constraints while competing against the competitor's known or unknown strategies. Further, we leverage the transfer learning methods in RL to tackle the competitive influence maximization to boost RL models' training time on new target social networks. Our proposed transfer learning methods leverage the previous knowledge learned on a different network to find an optimal policy on the new target network considering the competition and temporal aspects of the network. Besides, we propose a deep reinforcement learning (DRL) based model to overcome the state-action space growth of RL models when the network gets large. Our proposed model employs the community structure of the social network to find the best strategy for information propagation. Finally, we propose a DRL-based model to tackle competitive influence maximization on unknown social networks. Our proposed DRL-based model needs to learn a policy consisting of when to explore the network and when to select key influential users from the explored network. In addition, to boost the training efficiency of DRL models for unknown social networks, we employ transfer learning in deep reinforcement learning to address the competitive influence maximization problem on unknown social networks.

參考文獻


[1] E. Abbe and C. Sandon. Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic bp, and the informationcomputation gap. arXiv preprint arXiv:1512.09080, 2015.
[2] K. Ali, C.­Y. Wang, and Y.­S. Chen. Boosting reinforcement learning in competitive influence maximization with transfer learning. In 2018 IEEE/WIC/ACM International Conference on Web Intelligence (WI), pages 395–400. IEEE, 2018.
[3] K. Ali, C.­Y. Wang, and Y.­S. Chen. A novel nested q­learning method to tackle time­constrained competitive influence maximization. IEEE Access, 7:6337–6352, 2019.
[4] K. Ali, C.­Y. Wang, M.­Y. Yeh, and Y.­S. Chen. Addressing competitive influence maximization on unknown social network with deep reinforcement learning. In 2020 IEEE/ACM International Conference on on Advances in Social Networks Analysis and Mining (ASONAM), pages 196–203. IEEE, 2020.
[5] A. Barreto, D. Borsa, J. Quan, T. Schaul, D. Silver, M. Hessel, D. Mankowitz, A. Zidek, and R. Munos. Transfer in deep reinforcement learning using successor features and generalised policy improvement. In Proc. of PMLR ICML, pages 501–510, 2018.

延伸閱讀