pynetim 0.5.1

A Python library for Network Influence Maximization

PyNetIM

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

---

简介

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

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

---

安装

pip install pynetim

系统要求：

• Python 3.8+（推荐 3.10+）
• C++20 编译器（GCC 10+, Clang 10+, MSVC 19.28+）

---

快速开始

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}")

---

核心功能

图结构

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 模型	疫情传播（含恢复）

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

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 提供两种自定义模型基类：

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

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 提供完整的评估指标模块，用于评估影响力最大化算法的性能：

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)

时间测量

支持多种时间测量方式：

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
├── evaluation/               # 评估指标
│   ├── ranking_metrics       # 排名指标
│   ├── influence_metrics     # 影响力指标
│   ├── seed_quality_metrics  # 种子质量指标
│   └── network_metrics       # 网络指标
├── timing/                   # 时间测量
│   ├── measure_time          # 装饰器
│   └── AlgorithmTimer        # 计时器类
├── utils/                    # 工具函数
└── py/                       # Python 实现（维护模式）

---

开发指南

运行测试

# 运行所有测试
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 了解版本历史。

---

许可证

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

---

致谢

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

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