A k-Hop Collaborate Game Model: Adaptive Strategy to Maximize Total Revenue

摘要

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.