NEDRL-CIM: Bridging Network Embeddings and DRL for Competitive Influence in Evolving Networks

TL;DR

In the real world, social networks are not frozen; they are living, breathing entities where connections form and dissolve constantly. This paper presents NEDRL-CIM (DRL-EMB), the first framework to tackle Competitive Influence Maximization (CIM) on evolving graphs. By combining Deep Reinforcement Learning with automated network embeddings, the authors outperform traditional heuristics and previous DRL models in both influence reach and computational speed.

The Evolution Dilemma: Why Static Models Fail

Most Influence Maximization (IM) research acts like a photographer, taking a single snapshot of a network and deciding on a strategy. However, real marketing happens in a "movie." A "super-influencer" today might have zero connections in tomorrow's graph snapshot.

The authors identify two fatal flaws in prior work:

1. Static Bias: Ignoring how the addition of new users or friendships changes the optimal "seed" nodes.
2. Feature Engineering Bottleneck: Existing DRL methods (like DRL-HCF) use manual features (e.g., node degree, neighborhood size). This is slow and often misses the subtle structural shifts inherent in evolving manifolds.

Methodology: The DRL-EMB Architecture

The core innovation lies in treating the CIM problem as a sequential decision-making task where the environment itself changes at every step.

1. Transient Competitive Linear Threshold (TCLT)

The authors propose TCLT, a propagation model designed for the "moving target" of evolving graphs. Unlike static models, in TCLT:

• Seed nodes selected at time $t$ propagate influence in the current graph $G_t$.
• Newly activated nodes propagate that influence in the next version of the graph $G_{t+1}$.
• This forces the DRL agent to consider not just who is powerful now, but who will be strategically positioned in the future.

2. State Representation via Embedding

Instead of manual recipes for features, the framework uses Node2Vec to generate $d$-dimensional vectors (${\Phi }_t$) for every node in each snapshot. This high-dimensional representation captures the "role" of a node better than a simple degree count.

3. The DRL Loop

The agent uses a Deep Q-Network (DQN) to select actions (meta-strategies like "MaxDegree" or "Weight") based on the current embedded state. By using an $ϵ$-greedy policy and experience replay, it learns which strategies thrive specifically under competition and evolution.

Experimental Results: Faster and Stronger

The authors tested their model against several baselines, including DRL-HCF (which uses hand-crafted features) and heuristics like PageRank and MaxDegree.

Superior Performance

On the BitcoinAlpha dataset, DRL-EMB achieved a reward of 488, nearly doubling the performance of DRL-HCF (250) in certain competitive settings. This proves that embeddings capture essential "evolutionary signals" that human-designed features miss.

Efficiency Gains

One of the most striking results is the Training Time Efficiency. Because DRL-EMB computes embeddings offline before the training loop starts, it avoids the heavy overhead of re-calculating graph statistics in every episode.

• DRL-HCF: >120 hours on BitcoinOTC.
• DRL-EMB: ~80 hours on BitcoinOTC.

Fig: DRL-EMB converges faster and reaches a higher reward ceiling than HCF-based models.

Critical Insight & Future Outlook

NEDRL-CIM shifts the paradigm from "calculating the best node" to "learning the best strategy for a dynamic environment."

Limitations: The current model uses static Node2Vec on separate snapshots. While effective, it doesn't explicitly model the transition between snapshots within the embedding space itself.

Transition to Transfer Learning: The authors conclude by suggesting Transfer Learning. Imagine training a model on Twitter's growth pattern and applying it to a new emerging social network—this "cross-network" intelligence is the next frontier for automated viral marketing.

Takeaway for the Industry

If you are building recommendation engines or viral marketing tools, stop looking at your graph as a constant. The value of a node is localized in time. Using DRL with latent embeddings allows for adaptive strategies that anticipate network growth rather than just reacting to it.