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

Jianxiong Guo, Weili Wu

TL;DR

This paper introduces a novel "k-hop Collaborate Game Model" for maximizing revenue in online social networks by strategically inviting users to initiate activities. They propose an adaptive strategy to select initiators, proving the problem is NP-hard and offering an efficient algorithm that outperforms heuristics on real-world datasets.

What Problem Does This Paper Address?

Online social networks (OSNs) are dynamic environments where user activities can spread through social connections. Traditional "influence maximization" problems focus on maximizing the number of users adopting a product or idea. However, this paper addresses a more nuanced scenario: revenue maximization where the revenue generated by an activity (like a multiplayer game) depends on the number of participants within a limited "k-hop" radius of the initiator. The challenge is that the outcome of inviting a user is uncertain (they might not accept, or their friends might not join), requiring an adaptive strategy. The authors tackle the problem of selecting a limited number of initial users (initiators) to maximize the total expected revenue, considering the cascading effect of invitations within a k-hop influence limit.

Methods

The core contribution is the k-hop Collaborate Game Model. This model defines revenue based on participants within a k-hop radius of an initiator, with diminishing returns for participants further away. The problem of selecting initiators to maximize this revenue is termed Revenue Maximization under k-hop Collaborate Game (RMKCG).

Since the outcome of invitations is uncertain, the paper focuses on an adaptive strategy (A-RMKCG). This means decisions about who to invite next are made sequentially, based on the observed outcomes of previous invitations. The authors leverage concepts from adaptive optimization, specifically adaptive monotonicity and submodularity.

Key methodological contributions include:

  • Formalizing the A-RMKCG problem: Defining the objective function and the adaptive decision-making process.
  • Proving NP-hardness: Demonstrating that the problem is computationally challenging.
  • Developing an Adaptive-Invitation Algorithm: A greedy approach that iteratively selects the user with the highest conditional expected marginal revenue.
  • Efficient Marginal Gain Computation: Addressing the computational bottleneck of calculating marginal gains by proposing a novel, efficient method (Algorithm 2) that avoids full Monte-Carlo simulations for every step.
  • Theoretical Analysis: Proving adaptive monotonicity and, importantly, demonstrating that the problem is not generally adaptive submodular, but is under specific conditions (k=1 or edge probabilities are 1). This leads to a (1-1/e) approximation guarantee for these special cases.

Datasets

The paper evaluates its algorithms on three real-world social network datasets:

  • Dataset-1: A co-authorship network (0.4K users, 1.01K edges).
  • Dataset-2: A Wiki network (1.0K users, 3.15K edges).
  • Dataset-3: A Facebook social friendship network (3.0K users, 65.2K edges).

These datasets are sourced from networkrepository.com.

Key Insights and Ideas

  • Revenue is k-hop dependent: The model's novelty lies in linking revenue to participants within a specific, limited social distance from an initiator, moving beyond simple user-count maximization.
  • Adaptive strategy is crucial: Because outcomes are uncertain, a reactive, sequential decision-making process is necessary, making it a stochastic optimization problem.
  • Non-submodularity is a challenge: The problem is generally not adaptive submodular, which prevents the direct application of standard greedy approximation guarantees. This is a significant theoretical hurdle.
  • Efficient computation is key to scalability: The proposed method for computing marginal gains dramatically reduces runtime, making the adaptive strategy practical for large networks.
  • Heuristics can be surprisingly effective: While not strictly submodular, the problem exhibits submodular-like behavior in practice, especially with smaller k or higher edge probabilities, allowing for good performance from greedy-like strategies.

Key Results

  • NP-Hardness: The A-RMKCG problem is proven to be NP-hard.
  • Adaptive Monotonicity: The objective function is proven to be adaptive monotone.
  • Non-Adaptive Submodularity: The objective function is shown to be not adaptive submodular in general.
  • Approximation Guarantee: For specific cases (k=1 or all edge probabilities are 1), the Adaptive-Invitation algorithm achieves a (1-1/e) approximation ratio.
  • Algorithm Efficiency: The proposed Algorithm 2 for computing marginal gains is significantly faster (up to 1000x) than Monte-Carlo simulations, making the adaptive approach scalable.
  • Performance: Experiments on real-world datasets show that the Adaptive-Invitation algorithm consistently outperforms heuristic methods (MaxDegree, Random, MaxProb, MaxDegreeProb) in terms of total revenue. The standard deviation of the Adaptive-Invitation algorithm decreases with larger budgets and higher k-hop limits, indicating more stable and predictable revenue.

Limitations and Future Work

  • Non-Submodularity: The paper acknowledges that the problem is not generally adaptive submodular, limiting the theoretical approximation guarantees for the most general cases.
  • Approximation for General Case: While a (1-1/e) approximation is shown for special cases, the paper aims to find theoretical bounds for the general non-submodular case.
  • Model Generalization: The authors suggest future work in finding more generalized models and integrating data mining techniques to optimize parameter settings.
  • Computational Complexity: While Algorithm 2 improves efficiency, the paper notes that for highly accurate marginal gain computation in complex scenarios, Monte-Carlo simulations might still be necessary, albeit with a significant time cost.

Summary updated

Abstract

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.
BibTeX
@article{guo2020k,
  author = {Jianxiong Guo and Weili Wu},
  title = {{A k-Hop Collaborate Game Model: Adaptive Strategy to Maximize Total Revenue}},
  journal = {IEEE Trans. Comput. Soc. Syst.},
  year = {2020},
  url = {https://openreview.net/forum?id=h5EbFli8Mz},
}
Figure