This repository contains the implementation of a reinforcement learning-based approach to the Influence Maximization (IM) problem on dynamic contact networks. The core method uses a Double Deep Q-Network (DDQL) combined with a recurrent graph embedding architecture (Structure2Vec / S2V-DQN) and a Rehearsal replay buffer for continual learning across evolving graph snapshots.
The implementation follows the methodology described in:
S. Haleh S. Dizaji et al., "Influence Maximization in Dynamic Networks Using Reinforcement Learning," 2024.
- Background
- Why Deep Reinforcement Learning for Influence Maximization
- Why DDQL Instead of Standard DQN
- Methodology
- Dataset
- Results
- Repository Structure
- Setup and Reproduction
- References
Influence Maximization (IM) is a fundamental problem in network analysis. Given a social network and a budget of k seed nodes, the goal is to select those k nodes that maximize the expected spread of influence through the network. In practical terms, selecting the right "influencers" can determine the success of a viral marketing campaign, the reach of a public health message, or the effectiveness of information dissemination.
The IM problem is NP-hard even on static graphs. Traditional approaches like greedy algorithms with Monte Carlo simulations provide theoretical approximation guarantees but are computationally expensive, often requiring thousands of simulation rounds per candidate node at each step of the selection process.
Real-world social networks are not static. Connections between individuals appear and disappear over time -- people meet, interact, and part. This temporal evolution makes IM dramatically harder because:
- A seed set that is optimal at one time may be suboptimal moments later as the network topology changes.
- Classical greedy methods must be re-run from scratch whenever the graph structure changes, which is prohibitively expensive for networks that evolve continuously.
- The algorithm must generalize across different graph topologies rather than memorize a solution for a single fixed graph.
This project addresses these challenges by framing IM as a sequential decision-making problem solved with deep reinforcement learning.
Reinforcement Learning (RL) provides a natural framework for IM because the seed selection process is inherently sequential: at each step, an agent selects one node to add to the seed set, observes the resulting change in network state, and receives a reward proportional to the marginal influence gain. This maps directly to the Markov Decision Process (MDP) formulation that RL algorithms are designed to solve.
The IM problem is formulated as an MDP with the following components:
- State: A representation of the current graph topology and the set of already-selected seed nodes, encoded as a pair of tensors (node features and adjacency information) using the Structure2Vec (S2V) recurrent graph embedding.
- Action: Selecting the next node to add to the seed set from the remaining candidates.
- Reward: The marginal influence gain from adding the selected node, estimated via Independent Cascade (IC) Monte Carlo simulations.
- Transition: After selecting a node, the state is updated to reflect the new seed set configuration.
- Amortized computation: Once trained, the RL agent can select seed nodes in a single forward pass through the neural network, avoiding the expensive re-computation required by greedy methods at every step.
- Generalization: The S2V graph embedding enables the agent to learn structural patterns that transfer across different graph topologies, making it effective on previously unseen snapshots.
- Adaptability: Through the Rehearsal buffer mechanism, the agent retains knowledge from earlier graph snapshots while adapting to new ones, preventing catastrophic forgetting as the network evolves.
The choice of Double Deep Q-Learning (DDQL) over standard Deep Q-Networks (DQN) is a deliberate architectural decision that directly addresses a well-known failure mode in value-based reinforcement learning.
Standard DQN uses the same network to both select and evaluate actions. The Q-value update rule takes the form:
Q(s, a) <- r + gamma * max_a' Q(s', a'; theta)
Because the max operator always selects the highest estimated Q-value, and neural network estimates contain noise, DQN systematically overestimates action values. Over many training steps, these overestimation errors compound, leading to:
- Unstable training dynamics with oscillating or diverging loss.
- Suboptimal policies where the agent selects actions based on inflated value estimates rather than true expected returns.
- Particularly poor performance in stochastic environments where reward signals are inherently noisy -- exactly the case with Monte Carlo-estimated influence spread.
DDQL (introduced by van Hasselt et al., 2016) decouples action selection from action evaluation by maintaining two networks:
- Policy network (theta): Used to select the best action in the next state.
- Target network (theta_target): Used to evaluate the Q-value of that selected action.
The update rule becomes:
Q(s, a) <- r + gamma * Q(s', argmax_a' Q(s', a'; theta); theta_target)
By using the policy network to choose the action but the target network to estimate its value, DDQL breaks the positive feedback loop that causes overestimation. The target network parameters are updated slowly via soft updates (Polyak averaging with parameter tau), providing a stable evaluation baseline.
In the IM setting, rewards are estimated through stochastic IC simulations with a limited number of Monte Carlo runs (3 runs per step in this implementation). This introduces significant variance in the reward signal. Standard DQN would amplify this variance through overestimation, making it difficult for the agent to learn which nodes are genuinely influential versus which simply received lucky simulation outcomes.
DDQL provides the stability needed to learn meaningful seed selection policies despite this inherent stochasticity.
The agent uses a recurrent graph embedding architecture based on Structure2Vec (S2V). At each decision step:
-
Node Feature Construction: Each node receives a 2-dimensional feature vector encoding:
- Whether the node is already in the seed set (binary indicator).
- The node's normalized degree in the current snapshot.
-
Recurrent Embedding (K=4 iterations): The graph embedding is computed by iterating a message-passing procedure K=4 times. At each iteration, each node's embedding is updated based on its own features and the aggregated embeddings of its neighbors, enabling the network to capture multi-hop structural information.
-
Q-Value Estimation: The learned embeddings are used to compute a Q-value for each candidate node, representing the estimated future influence gain from selecting that node.
The entire architecture contains 12,545 trainable parameters, making it lightweight enough to train on CPU in approximately 23 minutes.
A critical challenge in dynamic networks is catastrophic forgetting: as the agent trains on new graph snapshots, it may lose the structural knowledge learned from earlier snapshots. The Rehearsal buffer addresses this by:
- Maintaining a fixed-capacity experience buffer (4,000 transitions) that stores experiences from all previously encountered snapshots.
- During training on each new snapshot, minibatches are drawn from this mixed buffer, ensuring the agent simultaneously learns from current and past experiences.
- This approach preserves the agent's ability to generalize across different network topologies rather than overfitting to the most recent snapshot.
The agent is trained across the first 30 snapshots of the dynamic network, with 30 episodes per snapshot. Key hyperparameters:
| Parameter | Value | Description |
|---|---|---|
| SEED_BUDGET | 10 | Number of seed nodes to select |
| EMBED_DIM | 64 | Dimension of node embeddings |
| K_ITER | 4 | Graph embedding recurrence depth |
| IC_PROB | 0.1 | Independent Cascade propagation probability |
| GAMMA | 0.99 | Discount factor |
| LR | 5e-4 | Learning rate (Adam optimizer) |
| TAU | 0.005 | Target network soft update rate |
| EPS_START | 1.0 | Initial exploration rate |
| EPS_END | 0.05 | Final exploration rate |
| EPS_DECAY | 300 | Epsilon decay steps |
| BATCH_SIZE | 32 | Training batch size |
| BUF_CAPACITY | 4,000 | Rehearsal buffer capacity |
| TRAIN_SNAPS | 30 | Number of snapshots used for training |
The project uses the Highschool 2013 contact network dataset from the SocioPatterns collaboration. This dataset records face-to-face interactions between students and teachers in a French high school over two days.
| Property | Value |
|---|---|
| Raw interaction records | 188,508 |
| Recording interval | Every 20 seconds |
| Time span | 1385982020 to 1386345580 (Unix timestamps) |
| Unique participants | 327 |
The raw contact records are binned into 400-second snapshots (20 consecutive ticks per snapshot), following the procedure described in the reference paper. Node IDs are remapped to a contiguous space [0, 326] so they can be used as array indices for the neural network.
| Property | Value |
|---|---|
| Total snapshots | 369 |
| Mean edges per snapshot | 114.3 |
| Min edges per snapshot | 13 |
| Max edges per snapshot | 572 |
| Mean active nodes per snapshot | 116.3 |
| Max active nodes per snapshot | 248 |
| Mean density per snapshot | 0.002 |
The network exhibits significant temporal variability: snapshot sizes range from 13 to 572 edges, reflecting the natural rhythms of a school day (class time, breaks, lunch).
After training on 30 snapshots, the agent is evaluated on the last training snapshot (snapshot ID 29) using a greedy policy (epsilon = 0). The agent selects 10 seed nodes, and the resulting influence spread is measured using 50 Monte Carlo IC simulations (higher than the 3 used during training for more accurate evaluation).
Two baselines are compared:
- Degree Heuristic: Selects the top-k nodes by degree centrality -- a strong, commonly used baseline in IM research.
- Random: Selects k nodes uniformly at random.
| Method | Expected Spread (nodes) |
|---|---|
| DDQL-Rehearsal (ours) | 16.68 |
| Degree Heuristic | 15.36 |
| Random | 11.26 |
The DDQL-Rehearsal agent achieves a 8.6% improvement over the Degree Heuristic baseline and a 48.1% improvement over Random selection. While the absolute difference over the degree heuristic may appear modest, it is important to consider:
- The degree heuristic is already a strong baseline that performs well on many real-world networks.
- The evaluation is performed on a relatively sparse snapshot (the network has low average density of 0.002).
- The RL agent achieves this result in a single forward pass per node, while a comparable greedy algorithm with Monte Carlo estimation would require orders of magnitude more computation.
Training completes in approximately 1,364 seconds (~23 minutes) on CPU. The training curves show:
- Average reward stabilizes after approximately 10-15 snapshots.
- Loss exhibits expected fluctuations due to the stochastic nature of IC reward estimation and the continual shift in graph topology across snapshots.
- The epsilon-greedy exploration rate converges to its minimum value (0.05) early in training, after which the agent primarily exploits its learned policy.
Influence_Maximization_in_Dynamic_Networks/
|
|-- data/
| |-- High-School_data_2013.csv # Raw contact network dataset
|
|-- notebooks/
| |-- ddql_rehearsal_influence_maximization.ipynb # Main implementation notebook
|
|-- saved_models/ # Pre-trained agent weights (.pt files)
|
|-- figures/ # Generated visualizations
|
|-- requirements.txt # Python dependencies
|-- .gitignore # Git ignore rules
|-- README.md # This file
The notebook in notebooks/ is configured to run with the project root as its base directory. When running the notebook, ensure the BASE path variable points to the project root (the parent directory of notebooks/). The notebook uses the following path configuration:
BASE = Path("..") # Project root (parent of notebooks/)
MODEL_DIR = BASE / "saved_models"
FIGURE_DIR = BASE / "figures"
RAW_FILE = BASE / "data" / "High-School_data_2013.csv"If running the notebook from the project root instead, change BASE = Path("..") to BASE = Path(".").
- Python 3.9+
- CUDA-capable GPU (optional, CPU training takes ~23 minutes)
# Clone the repository
git clone <repository-url>
cd Influence_Maximization_in_Dynamic_Networks
# Create a virtual environment (recommended)
python -m venv venv
source venv/bin/activate # Linux/macOS
# or
venv\Scripts\activate # Windows
# Install dependencies
pip install -r requirements.txtcd notebooks
jupyter notebook ddql_rehearsal_influence_maximization.ipynbExecute all cells sequentially. The notebook is organized in the following phases:
- Phase 1 -- Environment Setup: Imports, device configuration, reproducibility seeds, and project paths.
- Phase 2 -- Data Acquisition and Temporal Preprocessing: Loads the raw CSV, bins contacts into 400-second snapshots, remaps node IDs.
- Phase 3 -- Exploratory Data Analysis: Per-snapshot statistics and network visualizations.
- Phase 4 -- Independent Cascade Simulation: IC propagation model used for reward computation.
- Phase 5 -- Neural Architecture (S2V-DQN): Defines the recurrent graph embedding and Q-network.
- Phase 6 -- Continual Reinforcement Learning: DDQL agent with Rehearsal buffer.
- Phase 7 -- Training Pipeline: Trains the agent across 30 snapshots.
- Phase 8 -- Greedy Inference and Evaluation: Evaluates the trained agent against baselines.
- Phase 9 -- Comparison Visualization: Bar chart comparing influence spread across methods.
After full execution, the notebook produces:
- Trained model weights in
saved_models/ - Visualization figures in
figures/ - Console output showing per-snapshot training metrics and final comparison results
- S. Haleh S. Dizaji et al., "Influence Maximization in Dynamic Networks Using Reinforcement Learning," 2024.
- van Hasselt, H., Guez, A., and Silver, D., "Deep Reinforcement Learning with Double Q-learning," AAAI, 2016.
- Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., and Song, L., "Learning Combinatorial Optimization Algorithms over Graphs," NeurIPS, 2017.
- Kempe, D., Kleinberg, J., and Tardos, E., "Maximizing the Spread of Influence through a Social Network," KDD, 2003.
- SocioPatterns Collaboration, "Highschool 2013 Contact Network," http://www.sociopatterns.org/