Metadata-Version: 2.4
Name: pynetim
Version: 0.5.3
Summary: A Python library for Network Influence Maximization
Author-email: Kaijing Zhang <zhkaij@foxmail.com>
License: MIT
Project-URL: Homepage, https://github.com/zzzkhj/PyNetIM
Project-URL: Repository, https://github.com/zzzkhj/PyNetIM
Project-URL: Issues, https://github.com/zzzkhj/PyNetIM/issues
Classifier: Programming Language :: Python :: 3
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: networkx>=2.6
Requires-Dist: numpy>=1.20
Requires-Dist: tqdm>=4.60
Provides-Extra: deep-learning
Requires-Dist: torch>=1.10; extra == "deep-learning"
Requires-Dist: torch-geometric>=2.0; extra == "deep-learning"
Requires-Dist: torch-scatter>=2.0; extra == "deep-learning"
Provides-Extra: all
Requires-Dist: pynetim[deep-learning]; extra == "all"
Dynamic: license-file

# PyNetIM

[![PyPI version](https://badge.fury.io/py/pynetim.svg)](https://pypi.org/project/pynetim/)
[![Python Version](https://img.shields.io/badge/python-3.8+-blue.svg)](https://www.python.org/downloads/)
[![License](https://img.shields.io/badge/license-MIT-green.svg)](LICENSE)

[PyNetIM](https://zzzkhj.github.io/PyNetIM/) 是一个用于**社交网络影响力最大化（Influence Maximization, IM）问题**的 Python 库，集成了多种经典算法与扩散模型，提供 **C++ 高性能后端**，适用于算法研究、性能对比与科研实验。

***

## 简介

PyNetIM 提供完整的影响力最大化解决方案：

- **多种传播模型** - IC、LT、SI、SIR
- **多种 IM 算法** - 启发式、模拟类、RIS 类、深度学习
- **深度学习算法** - ToupleGDD、S2V-DQN、BiGDN
- **评估指标** - 排名指标、影响力指标、种子质量指标、网络指标
- **时间测量** - 装饰器、AlgorithmTimer、多次运行统计
- **高性能 C++ 后端** - 比纯 Python 快 20-30 倍
- **自定义模型支持** - 支持用户自定义传播模型
- **简洁 API** - 一行代码完成复杂任务

***

## 安装

```bash
pip install pynetim
```

**系统要求：**

- Python 3.8+（推荐 3.10+）
- C++17 编译器（GCC 8+, Clang 7+, MSVC 19.14+）

***

## 快速开始

```python
from pynetim import IMGraph, IndependentCascadeModel, IMMAlgorithm

# 1. 创建图
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]
graph = IMGraph(edges, weights=0.3)

# 2. 使用 IMM 算法选择种子节点
imm = IMMAlgorithm(graph, model='IC', epsilon=0.5)
seeds = imm.run(k=2)
print(f"种子节点: {seeds}")

# 3. 评估影响力
model = IndependentCascadeModel(graph, set(seeds))
avg_influence = model.run_monte_carlo_diffusion(1000, num_threads=4)
print(f"平均影响力: {avg_influence:.2f}")
```

***

## 核心功能

### 图结构

```python
from pynetim import IMGraph

# 从边列表创建
graph = IMGraph(edges, weights=0.3)

# 统一权重
graph = IMGraph(edges, weights=0.1)

# 逐边权重
graph = IMGraph(edges, weights=[0.1, 0.2, 0.3, ...])

# 查询邻居（仅节点ID）
for neighbor in graph.out_neighbors(node):
    print(f"邻居: {neighbor}")

# 查询邻居（带权重）
for neighbor, weight in graph.out_neighbors_with_weights(node):
    print(f"邻居: {neighbor}, 权重: {weight}")
```

### 传播模型

| 模型                                  | 说明     | 使用场景      |
| ----------------------------------- | ------ | --------- |
| `IndependentCascadeModel`           | 独立级联模型 | 社交网络传播    |
| `LinearThresholdModel`              | 线性阈值模型 | 观点传播      |
| `SusceptibleInfectedModel`          | SI 模型  | 疫情传播      |
| `SusceptibleInfectedRecoveredModel` | SIR 模型 | 疫情传播（含恢复） |

```python
from pynetim import IndependentCascadeModel, SusceptibleInfectedModel, SusceptibleInfectedRecoveredModel

# IC 模型
model = IndependentCascadeModel(graph, seeds={0, 1})
count = model.run_single_simulation()

# SI 模型（需要显式提供 beta 和 max_steps）
si_model = SusceptibleInfectedModel(graph, seeds={0, 1}, beta=0.1, max_steps=100)
count = si_model.run_single_simulation()

# SIR 模型（需要显式提供 beta 和 gamma）
sir_model = SusceptibleInfectedRecoveredModel(graph, seeds={0, 1}, beta=0.1, gamma=0.05)
count = sir_model.run_single_simulation()

# 蒙特卡洛模拟（多线程）
avg = model.run_monte_carlo_diffusion(1000, num_threads=4)

# 记录激活节点
model = IndependentCascadeModel(graph, seeds, record_activated=True)
count = model.run_single_simulation()
activated = model.get_activated_nodes()
```

### 影响力最大化算法

| 算法                               | 类型     | 特点          | 参考文献                     |
| -------------------------------- | ------ | ----------- | ------------------------ |
| `DegreeCentralityAlgorithm`      | 启发式    | 度中心性，最快     | -                        |
| `PageRankAlgorithm`              | 启发式    | 经典 PageRank | Brin & Page 1998         |
| `VoteRankAlgorithm`              | 启发式    | 投票机制，避免聚集   | Zhang et al. 2016        |
| `KShellDecompositionAlgorithm`   | 启发式    | K-shell 分解  | Kitsak et al. 2010       |
| `BetweennessCentralityAlgorithm` | 启发式    | 介数中心性       | Freeman 1977             |
| `ClosenessCentralityAlgorithm`   | 启发式    | 接近中心性       | Sabidussi 1966           |
| `EigenvectorCentralityAlgorithm` | 启发式    | 特征向量中心性     | Bonacich 1972            |
| `SingleDiscountAlgorithm`        | 启发式    | 速度快         | -                        |
| `DegreeDiscountAlgorithm`        | 启发式    | 速度快，效果好     | -                        |
| `GreedyAlgorithm`                | 模拟类    | 精度高，速度慢     | Kemper et al., 2003      |
| `CELFAlgorithm`                  | 模拟类    | 精度高，比贪婪快    | Leskovec et al., 2007    |
| `CELFPlusAlgorithm`              | 模拟类    | CELF 优化版    | Goyal et al., WWW 2011   |
| `BaseRISAlgorithm`               | RIS 类  | 基础反向影响采样    | Borgs et al., 2014       |
| `IMMAlgorithm`                   | RIS 类  | 大规模图首选      | Tang et al., SIGMOD 2015 |
| `TIMAlgorithm`                   | RIS 类  | 两阶段影响力估计    | Tang et al., 2014        |
| `TIMPlusAlgorithm`               | RIS 类  | TIM 优化版     | Tang et al., 2014        |
| `OPIMAlgorithm`                  | OPIM 类 | 可证明近似保证     | Tang et al., SIGMOD 2018 |
| `OPIMCAlgorithm`                 | OPIM 类 | 自适应采样版本     | Tang et al., SIGMOD 2018 |

```python
from pynetim import DegreeDiscountAlgorithm, GreedyAlgorithm, IMMAlgorithm, OPIMCAlgorithm
from pynetim.algorithms import PageRankAlgorithm, VoteRankAlgorithm

# 启发式算法（快）
algo = DegreeDiscountAlgorithm(graph)
seeds = algo.run(k=10)

# PageRank 算法
algo = PageRankAlgorithm(graph, damping=0.85)
seeds = algo.run(k=10)

# VoteRank 算法（避免种子聚集）
algo = VoteRankAlgorithm(graph)
seeds = algo.run(k=10)

# 模拟类算法（精确）
algo = GreedyAlgorithm(graph, model='IC', num_trials=1000)
seeds = algo.run(k=10)

# RIS 算法（大规模图）
algo = IMMAlgorithm(graph, model='IC', epsilon=0.5)
seeds = algo.run(k=10)

# OPIM-C 算法（自适应采样，可证明近似保证）
algo = OPIMCAlgorithm(graph, model='IC', random_seed=42, verbose=True)
seeds = algo.run(k=10, epsilon=0.3)
```

### 深度学习算法

PyNetIM 集成了基于深度强化学习的影响力最大化算法：

| 算法 | 类型 | 特点 | 参考文献 |
| --- | --- | --- | --- |
| `ToupleGDDAlgorithm` | 深度学习 | 三重门控图神经网络 + DQN | IEEE TCSS 2024 |
| `S2VDQNAlgorithm` | 深度学习 | Structure2Vec + DQN | NeurIPS 2017 |
| `BiGDNAlgorithm` | 深度学习 | 端到端图神经网络 + DQN（教师模型） | Expert Syst. Appl. 2025 |
| `BiGDNSAlgorithm` | 深度学习 | BiGDN 学生模型，支持知识蒸馏 | - |

**预训练权重**：库内置了论文作者公开的预训练权重，设置 `pretrained=True` 即可自动加载。用户也可通过 `weights_path` 参数指定自己的权重文件。

```python
from pynetim import IMGraph
from pynetim.algorithms import (
    ToupleGDDAlgorithm, S2VDQNAlgorithm,
    BiGDNAlgorithm, BiGDNSAlgorithm
)

# 创建图
graph = IMGraph(edges, weights=0.3)

# ToupleGDD（默认 use_topk=True，一次性选择）
algo = ToupleGDDAlgorithm(graph, pretrained=True)
seeds = algo.run(k=10)

# S2V-DQN（默认 use_topk=False，迭代选择）
algo = S2VDQNAlgorithm(graph, pretrained=True)
seeds = algo.run(k=10)

# BiGDN
algo = BiGDNAlgorithm(graph, pretrained=True)
seeds = algo.run(k=10)

# BiGDNS（学生模型）
algo = BiGDNSAlgorithm(graph, pretrained=True)
seeds = algo.run(k=10)
```

#### 训练深度学习模型

```python
from pynetim.algorithms import (
    ToupleGDDTrainer, S2VDQNTrainer,
    BiGDNTrainer, BiGDNNodeEncoderTrainer
)

# ToupleGDD 训练
trainer = ToupleGDDTrainer(device='auto')
trainer.train(graphs=[graph], budget=10, num_epochs=100, save_path='model.ckpt')

# S2V-DQN 训练
trainer = S2VDQNTrainer(device='auto')
trainer.train(graphs=[graph], budget=10, num_epochs=100, save_path='model.ckpt')

# BiGDN 训练（需要先预训练 NodeEncoder）
ne_trainer = BiGDNNodeEncoderTrainer(num_features=64, device='auto')
ne_trainer.train(graphs=train_graphs, num_epochs=100, save_path='encoder.pth')

trainer = BiGDNTrainer(num_features=64, device='auto', encoder_path='encoder.pth')
trainer.train(graphs=[graph], budget=10, num_epochs=100, save_path='model.pth')

# BiGDNS 训练（需要教师模型权重进行知识蒸馏）
trainer = BiGDNTrainer(num_features=64, device='auto',
                       teacher_path='bigdn_weights.pth', is_student=True)
trainer.train(graphs=[graph], budget=10, num_epochs=100, save_path='bigdns_weights.pth')
```

**注意**：深度学习算法需要安装额外依赖：

```bash
pip install pynetim[deep-learning]
```

### 自定义传播模型

PyNetIM 提供两种自定义模型基类：

| 基类                               | 特点         | 适用场景      |
| -------------------------------- | ---------- | --------- |
| `BaseCallbackDiffusionModel`     | C++ 回调，单线程 | 简单模型      |
| `BaseMultiprocessDiffusionModel` | 多进程并行      | 需要加速的复杂模型 |

```python
from pynetim.diffusion_model import BaseMultiprocessDiffusionModel

class MyICModel(BaseMultiprocessDiffusionModel):
    """自定义 IC 模型。"""
    
    def run_single_trial(self, seeds, rng_seed):
        import random
        random.seed(rng_seed)
        
        activated = set(seeds)
        current = list(seeds)
        
        while current:
            new_active = []
            for node in current:
                for neighbor, weight in self.graph.out_neighbors_with_weights(node):
                    if neighbor not in activated and random.random() < weight:
                        activated.add(neighbor)
                        new_active.append(neighbor)
            current = new_active
        
        return len(activated), activated, [0] * self.graph.num_nodes

# 使用自定义模型
model = MyICModel(graph, {0, 1})
avg = model.run_monte_carlo_diffusion(1000, num_processes=4)
```

### 评估指标

PyNetIM 提供完整的评估指标模块，用于评估影响力最大化算法的性能：

```python
from pynetim.evaluation import (
    kendall_tau,
    monotonicity_score,
    top_k_accuracy,
    average_shortest_distance,
    degree_statistics,
)

# 排名相关性评估
tau, p = kendall_tau(ranking1, ranking2)

# 单调性评估（区分节点重要性的能力）
mono = monotonicity_score(importance_scores)

# Top-K 准确率
acc = top_k_accuracy(predicted_seeds, ground_truth_seeds, k=10)

# 种子节点分布评估
avg_dist = average_shortest_distance(graph, seeds)
stats = degree_statistics(graph, seeds)
```

### 时间测量

支持多种时间测量方式：

```python
from pynetim.timing import measure_time, AlgorithmTimer

# 装饰器方式
@measure_time
def my_algorithm(graph, k):
    return seeds

seeds, runtime = my_algorithm(graph, k=10)

# AlgorithmTimer 类
timer = AlgorithmTimer(algorithm)
seeds, runtime = timer.run(k=10, mc_rounds=1000, random_seed=42)

# 多次运行统计
stats = timer.run_multiple(k=10, num_runs=5)
print(f"Mean: {stats['mean']:.4f}s, Std: {stats['std']:.4f}s")
```

***

## 性能对比

测试环境：Intel Xeon Platinum 8255C @ 2.50GHz, 3.6GB RAM, Ubuntu 24.04 LTS, Python 3.10.20

| 模型                             | 并行度  | 耗时    | 说明        |
| ------------------------------ | ---- | ----- | --------- |
| C++ IC                         | 1 线程 | 0.30s | 基准（最快）    |
| C++ IC                         | 4 线程 | 0.38s | 多线程加速     |
| BaseCallbackDiffusionModel     | 1 线程 | 6.6s  | 单线程可用     |
| BaseCallbackDiffusionModel     | 4 线程 | 6.9s  | ⚠️ GIL 限制 |
| BaseMultiprocessDiffusionModel | 1 进程 | 6.2s  | 单进程       |
| BaseMultiprocessDiffusionModel | 4 进程 | 3.7s  | ✅ 真正并行    |

***

## 项目结构

```
src/pynetim/
├── __init__.py
├── graph/                    # 图结构
│   └── IMGraph
├── diffusion_model/          # 传播模型
│   ├── IndependentCascadeModel
│   ├── LinearThresholdModel
│   ├── SusceptibleInfectedModel
│   ├── SusceptibleInfectedRecoveredModel
│   ├── BaseCallbackDiffusionModel      # C++ 回调版
│   └── BaseMultiprocessDiffusionModel  # 多进程版
├── algorithms/               # IM 算法
│   ├── SingleDiscountAlgorithm
│   ├── DegreeDiscountAlgorithm
│   ├── GreedyAlgorithm
│   ├── CELFAlgorithm
│   ├── heuristic/            # 启发式算法
│   │   ├── DegreeCentralityAlgorithm
│   │   ├── PageRankAlgorithm
│   │   ├── VoteRankAlgorithm
│   │   ├── KShellDecompositionAlgorithm
│   │   ├── BetweennessCentralityAlgorithm
│   │   ├── ClosenessCentralityAlgorithm
│   │   └── EigenvectorCentralityAlgorithm
│   ├── ris/                  # RIS 类算法
│   │   ├── BaseRISAlgorithm
│   │   ├── IMMAlgorithm
│   │   ├── TIMAlgorithm
│   │   ├── TIMPlusAlgorithm
│   │   ├── OPIMAlgorithm
│   │   └── OPIMCAlgorithm
│   └── deep_learning/        # 深度学习算法
│       ├── ToupleGDDAlgorithm
│       ├── S2VDQNAlgorithm
│       ├── BiGDNAlgorithm
│       ├── BiGDNSAlgorithm
│       ├── ToupleGDDTrainer
│       ├── S2VDQNTrainer
│       ├── BiGDNTrainer
│       └── BiGDNNodeEncoderTrainer
├── evaluation/               # 评估指标
│   ├── ranking_metrics       # 排名指标
│   ├── influence_metrics     # 影响力指标
│   ├── seed_quality_metrics  # 种子质量指标
│   └── network_metrics       # 网络指标
├── timing/                   # 时间测量
│   ├── measure_time          # 装饰器
│   └── AlgorithmTimer        # 计时器类
├── utils/                    # 工具函数
└── py/                       # Python 实现（维护模式）
```

***

## 开发指南

### 运行测试

```bash
# 运行所有测试
python -m pytest tests/

# 运行特定测试
python tests/test_diffusion_comparison.py
```

### 贡献代码

1. Fork 本仓库
2. 创建特性分支 (`git checkout -b feature/AmazingFeature`)
3. 提交更改 (`git commit -m 'Add some AmazingFeature'`)
4. 推送到分支 (`git push origin feature/AmazingFeature`)
5. 开启 Pull Request

***

## 更新日志

查看 [CHANGELOG.md](CHANGELOG.md) 了解版本历史。

***

## 许可证

本项目采用 MIT 许可证 - 详见 [LICENSE](LICENSE) 文件。

***

## 致谢

感谢以下对本项目提供帮助的个人和工具：

- **TraeAI** - 提供了强大的 AI 辅助开发环境，显著提升了代码开发效率和问题解决能力
- **GLM-5** - 智谱 AI 大语言模型，在代码开发、调试优化和文档编写过程中提供了重要帮助

