动态有竞争社交网络影响力最大化问题研究

The aim of influence maximization is to select limited number of seeds to disseminate a piece of information such that the influence scope, through word-of-mouth effect via directed links in the network, can be maximized, which is proved to be NP-hard. Although there have been many encouraging solutions, the real applications of these works are still limited. The key reason for that are as follows, on one hand, the majority of these works do not take into account the fact that real social network are evolving; on the other hand, there may also exist many competitors who are propagating their own information within the same network. In this project, we will focus on the properties of real social network, especially the evolution and competition, find the influence propagation models within evolutionary and competitive networks, study new solutions for influence maximization within such networks, and propose evolution and competition-aware influence maximization algorithms.

社会（交）网络中影响力最大化问题旨在从目标网络中选择尽可能少的种子节点进行信息传播以实现传播范围的最大化，该问题是NP-难的。近年来国内外学者相继提出了一系列解决方案，然而这些研究成果无法应对目前真实社会网络的两种重要特性:网络的动态变化性以及网络推广和营销的竞争性。在真实网络动态、竞争环境下研究影响力最大化问题对信息化社会中政治、经济诸多方面都有着至关重要的意义，如舆情监控、市场推广、话题传播等。在本课题中，申请人将针对已有方案的上述两个主要局限性，即真实网络动态性和竞争性，采用基于采样的网络拓扑预测方法对影响力期望值进行计算，并基于纳什均衡理论对竞争环境下影响力最大化贪心和启发算法进行研究，揭示面向动态网络及有竞争网络的影响力传播机理，提出面向真实网络影响力最大化问题的核心算法与解决方案，并尝试将相关解决方案进行并行化部署，建立面向真实社会网路动态竞争环境的影响力最大化算法应用原型。

社会（交）网络中影响力最大化问题旨在从目标网络中选择尽可能少的种子节点进行信息传播以实现传播范围的最大化，该问题是NP-难的。近年来国内外学者相继提出了一系列解决方案，然而这些研究成果无法应对目前真实社会网络的两种重要特性:网络的动态变化性以及网络推广和营销的竞争性。在真实网络动态、竞争环境下研究影响力最大化问题对信息化社会中政治、经济诸多方面都有着至关重要的意义，如舆情监控、市场推广、话题传播等。在本课题中，课题组对对面向动态网络的影响力最大化问题开展研究，建立网络发展趋势的预测模型和影响力传播速度的计算模型，首次定义了动态网络环境中影响力最大化问题Proteus-IM问题，提出了面向网络变化的节点影响力期望值估计方法和面向动态网络的影响力最大化算法Pro-Seer。课题组探索了和应用结合更紧密的基于位置的社交网络（Location-based social network, LBSN）中面向关键区域的影响力最大化问题，针对该问题，提出了支持任意凸多边形区域的影响力最大化算法SFM。结合近期深度强化学习在组合优化问题上的突破性应用，课题组首次将深度强化学习方法引入影响力最大化问题上，提出了基于深度Q网络的节点影响力评估模型，并相应的给出了对应的影响力最大化算法DISCO。