Influence Maximization Experiments - Linear Threshold Model

This repository implements and compares three metaheuristic algorithms — Tabu Search, Simulated Annealing, and Genetic Algorithm — with a simple degree-based Greedy baseline, for the Influence Maximization problem under the Linear Threshold (LT) model.

All algorithms use random node thresholds and weighted edges.

Project Structure

influence-maximization/
├── algorithms/                  # Algorithm implementations
│   ├── __init__.py
│   ├── tabu_search.py           # Tabu Search
│   ├── simulated_annealing.py   # Simulated Annealing
│   └── genetic_algorithm.py     # Genetic Algorithm
├── network.txt                  # Small test network dataset (with weights)
├── run_experiments.py           # Main script: run comparative experiments
├── requirements.txt             # Dependencies
├── .gitignore
└── README.md                    # This file

Dataset Description

• Filename: network.txt
• Format: Edge list with weights, space-separated (three columns per line)

Example: 1 2 0.5 → directed edge from node 1 to node 2 with weight 0.5

• Purpose: Used for quick validation and comparison of algorithms under LT model (typically tested with seed set sizes k = 3 to 10)

To test on larger networks (e.g., NetHEPT, Epinions, etc.), simply replace network.txt with your own file and update the path in run_experiments.py if needed.

Features

• Unified interface: each algorithm returns (best_seed_set: set[int], influence_spread: int)
• LT propagation: cumulative weighted influence from activated neighbors
• Comparative experiments: average spread and runtime over multiple runs
• Baseline: simple degree-greedy method for quick comparison

Requirements

Python 3.8 or higher

Installation

# Recommended: use a virtual environment
python -m venv venv
source venv/bin/activate          # Linux / macOS
# Windows: venv\Scripts\activate

Install dependencies: pip install -r requirements.txt

How to Run

Make sure network.txt is in the project root directory

Run the main experiment script:

python run_experiments.py

What the Script Does

• Loads the graph from network.txt
• For each k in [3, 4, 5, 6, 8, 10]:
  • Randomly assigns thresholds (0.01–0.99) to nodes
  • Runs Greedy, Tabu Search, SA, and GA (3 repeats each)
  • Prints per-run results
• Finally displays a summary table:

k    |     Greedy       |   Tabu Search    |        SA        |        GA
     | spread   time(s) | spread   time(s) | spread   time(s) | spread   time(s)
--------------------------------------------------------------------------------
3    |  12.0     0.01   |  15.3     2.45   |  14.7     1.89   |  16.0     4.21

Customization

Each algorithm is implemented as a standalone Python module under algorithms/, so you can directly import and reuse them in your own projects.

You can easily tune parameters inside run_experiments.py:

• Change K_VALUES, REPEATS
• Adjust algorithm-specific parameters in the ALGORITHMS list (iterations, population size, cooling rate, etc.)

Future Extensions

• Monte-Carlo averaging over multiple threshold realizations
• Additional baselines (CELF, Degree DiscountIC, etc.)
• Support for larger real-world datasets
• Visualization of spread vs. k curves

Author

Shuntao Wang