A k-hop Collaborate Game Model: Adaptive Strategy to Maximize Total Revenue
share
In Online Social Networks (OSNs), interpersonal communication and information sharing are happening all the time, and it is real-time. When a user initiates an activity in OSNs, immediately, he/she will have a certain influence in his/her friendship circle automatically. Then, some users in the initiator's friendship circle will be attracted to participate in this activity. Based on such a fact, we design a k-hop Collaborate Game Model, which means that an activity initiated by a user can only influence those users whose distance are within k-hop from the initiator in OSNs. Besides, we introduce the problem of Revenue Maximization under k-hop Collaborate Game (RMKCG), which identifies a limited number of initiators in order to obtain benefits as much as possible. Collaborate Game Model describes in detail how to quantify benefit and the logic behind it. We do not know how many followers would be generated for an activity in advance, thus, we need to adopt an adaptive strategy, where the decision who is the next potential initiator depends on the results of past decisions. 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, we prove it is adaptive submodular and an adaptive greedy strategy can obtain a (1-1/e)-approximation by adaptive submodularity theory. Due to the complexity of our model, it is hard to compute the marginal gain for each candidate user, then, we propose a convenient and efficient computational method. The effectiveness and correctness of our algorithms are validated by heavy simulation on real-world social networks eventually.
READ FULL TEXT