  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 naturally, 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 this 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 revenue as much as possible.
Collaborate Game Model describes in detail how to quantify revenue and the
logic behind it. We do not know how many followers would be generated from 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, 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.
