DRL in the Dark: Mastering Competitive Influence on Unknown Social Networks

TL;DR

Most viral marketing research assumes we have a "God-view" of the social network. In reality, we are often blind. This paper presents a Deep Reinforcement Learning (DRL) framework that learns when to "scout" the network and when to "strike" by selecting influential seeds. By integrating Transfer Learning, the authors achieve a 5x reduction in training time while outperforming traditional heuristics in competitive scenarios.

The "God-View" Fallacy in Social Marketing

In the Competitive Influence Maximization (CIM) problem, multiple parties (like Samsung vs. HTC) compete to activate the most nodes in a graph. However, there is a massive gap between theory and practice: the network topology is rarely known.

Prior works assume we know every "friendship" edge, but collecting this data via surveys or API scraping is expensive and slow. If you don't know the full graph, how do you know who the "influencers" are? You have a budget, and every round you must decide: do I spend my budget to probe the network (discover new edges) or to seed a product (activate a node)?

Methodology: The Probing-Investing Trade-off

The authors formulate the CIM-UN (Competitive Influence Maximization on Unknown Networks) problem. The core innovation lies in the agent's ability to choose from a "Meta-Action" space:

1. Jump-Crawl Probing: Use a hybrid approach to either jump to a random node or crawl along existing edges to reveal hidden neighbors.
2. IM-Based Seeding: Use strategies like MaxDegree or Blocking on the currently visible part of the graph.

Architecture and State Normalization

To make the model work across different networks (e.g., switching from a small C. elegans network to a large Facebook graph), the authors designed scale-invariant state features. By normalizing degrees and node counts into discrete numerical representations (e.g., 0 to 3), the agent learns a general "intuition" about network density rather than getting bogged down in specific node counts.

Fig 1: The proposed DRL framework showing the interaction between the DQN agent and the unknown network environment.

Transfer Learning: Training in Seconds, Deploying in Hours

Training a DRL agent on a massive social network from scratch is computationally brutal (often taking >50 hours). The authors use Transfer Learning (TL) to solve this:

• Source Training: Train the agent on a tiny "Source Network" (Celegan, ~300 nodes).
• Fine-Tuning: Transfer the weights to a "Target Network" (Facebook, ~4000 nodes).

This jump-starts the model with a pre-existing "common sense" about social influence, drastically speeding up convergence.

Experimental Battleground

The researchers tested their agent against several competitors, including Fixed Degree (FD) (highly aggressive seeding) and Alternate Fixed Degree (AFD) (alternating between probing and seeding).

Performance Gains

The results confirm that the DRL agent adapts its strategy based on how much of the network is visible. In many cases, it learned that early probing leads to a "discovery" of hidden hubs that a "blind" heuristic like FD would never find.

Table 1: Competitive rewards (activated nodes) across different initial visibilities (0.1% to 3%). DRL-UN variants consistently lead.

Efficiency Breakthrough

As shown in the following analysis, the Transfer Learning approach (DRL-UN(TL)) slashed training times significantly, making DRL a viable tool even for large-scale marketing applications where time is a constraint.

Fig 2: Comparison of training times. Notice the massive reduction when using Transfer Learning (gray/yellow bars) vs. training from scratch (blue bars).

Conclusion & Insights

The true value of this paper is its pragmatic approach to uncertainty. In the real world, we are always operating with partial information. By framing network discovery as a high-level "Probe" action, the authors move reinforcement learning closer to solving real-world infrastructure and marketing problems.

Limitations: The model still relies on a "Jump-Crawl" heuristic for the low-level probing logic. Future work could involve letting the RL agent choose specific nodes to probe, rather than just choosing the "Probing" action itself, potentially uncovering even more efficient discovery patterns.