A k-Hop Collaborate Game Model: Adaptive Strategy to Maximize Total Revenue
A k-Hop Collaborate Game Model: Adaptive Strategy to Maximize Total Revenue
复制标题
DOI：
10.1109/tcss.2020.3001509
复制
发表时间：
2019-10
影响因子：
5
通讯作者：
Jianxiong Guo;Weili Wu
中科院分区：
文献类型：
--
作者：
Jianxiong Guo;Weili Wu
在在线社交网络（OSN）中，人与人之间的交流和信息共享无时无刻不在发生，而且是真实的时间。如果用户在OSN中发起活动（游戏），自然会对自己的友谊圈造成一定的影响，即会吸引该发起者的友谊圈中的部分用户参与该活动。基于这样的事实，我们设计了一个k-hop合作博弈模型，这意味着由用户发起的活动只能影响那些距离该发起者在k-hop内的用户。我们引入了k跳合作博弈（RMKCG）下的收益最大化问题，该问题确定了有限数量的发起者，以获得尽可能多的收益。合作博弈模型详细描述了如何量化收益及其背后的逻辑。我们不知道活动会提前吸引多少追随者，因此，我们需要采取自适应策略，其中决定谁是下一个潜在的发起者取决于过去决策的结果。自适应RMKCG问题可以看作是一个新的随机优化问题，我们证明了它是NP-难的，自适应单调的，但不是自适应子模的。但在某些特殊情况下，它是自适应次模的，因此，我们设计了一个自适应贪婪算法。由于模型的复杂性，很难计算每个候选用户的边际增益，因此提出了一种有效的计算方法来估计边际增益，最后通过大量的真实图仿真验证了算法的有效性和正确性。
In online social networks (OSNs), interpersonal communication and information sharing are happening all the time, and it is real time. If a user initiates an activity (game) in OSNs, she will cause a certain impact on her friendship circle naturally, namely, some users in this initiator’s friendship circle will be attracted to participate in this activity. Based on such a fact, we design a k-hop collaborated game model, which means that an activity initiated by a user can only influence those users whose distance is within k-hop from this initiator. We introduce the problem of revenue maximization under k-hop collaborate game (RMKCG), which identifies a limited number of initiators in order to obtain revenue as much as possible. The collaborated game model describes in detail how to quantify revenue and the logic behind it. We do not know how many followers would be attracted by activity in advance, and thus, we need to adopt an adaptive strategy, where the decision who is the next potential initiator depends on the results of past decisions. The adaptive RMKCG problem can be considered as a new stochastic optimization problem, and we prove it is NP-hard, adaptive monotone, but not adaptive submodular. But in some special cases, it is adaptive submodular, and thus, we design an adaptive greedy algorithm. Due to the complexity of our model, it is hard to compute the marginal gain for each candidate user, and then we propose an efficient computational method to estimate it. The effectiveness and correctness of our algorithms are validated by heavy simulation on real-world graphs finally.