算法模块

基础类

class pynetim.algorithms.base_algorithm.BaseAlgorithm(graph, diffusion_model=None)[source]

Bases: object

影响力最大化算法基类。

为各种影响力最大化算法实现提供基础框架，包含图结构和扩散模型，以及需要子类实现的核心方法。

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

diffusion_model: 扩散模型类。

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import BaseAlgorithm
>>>
>>> class MyAlgorithm(BaseAlgorithm):
...     def run(self, k):
...         return set(range(k))
...
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = MyAlgorithm(graph, diffusion_model='IC')
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None)[source]

初始化算法基类。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 None。

Raises:

ValueError – 当 diffusion_model 不是 ‘IC’ 或 ‘LT’ 时抛出。

get_seeds()[source]

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

启发式算法

class pynetim.algorithms.heuristic.BetweennessCentralityAlgorithm(graph, diffusion_model=None, normalized=True, sample_size=None)[source]

Bases: BaseAlgorithm

介数中心性启发式算法。

选择在网络中作为最短路径”桥梁”的节点。介数中心性高的节点控制着网络中的信息流动，是关键的传播节点。

时间复杂度: O(n * m) 或 O(n^2) 对于稀疏图

Parameters:

graph (IMGraph)
diffusion_model (str)
normalized (bool)
sample_size (int)

graph: 输入图对象。

seeds: 种子节点集合。

References

Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 35-41.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import BetweennessCentralityAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = BetweennessCentralityAlgorithm(graph)
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None, normalized=True, sample_size=None)[source]

初始化介数中心性算法。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型（此算法不使用该参数）。
normalized (bool) – 是否归一化介数值，默认 True。
sample_size (int) – 采样节点数，用于加速大规模图计算，默认 None（使用全部节点）。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

class pynetim.algorithms.heuristic.ClosenessCentralityAlgorithm(graph, diffusion_model=None)[source]

Bases: BaseAlgorithm

接近中心性启发式算法。

选择距离网络中其他节点最近的节点。接近中心性高的节点可以快速将信息传播到整个网络。

时间复杂度: O(n * m)

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

References

Sabidussi, G. (1966). The centrality index of a graph. Psychometrika, 31(4), 581-603.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import ClosenessCentralityAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = ClosenessCentralityAlgorithm(graph)
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None)[source]

初始化算法基类。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 None。

Raises:

ValueError – 当 diffusion_model 不是 ‘IC’ 或 ‘LT’ 时抛出。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

class pynetim.algorithms.heuristic.DegreeCentralityAlgorithm(graph, diffusion_model=None)[source]

Bases: BaseAlgorithm

度中心性启发式算法。

选择出度最大的节点作为种子节点，是最简单快速的启发式方法。适合作为基准算法进行比较。

时间复杂度: O(n log n)

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import DegreeCentralityAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = DegreeCentralityAlgorithm(graph)
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None)[source]

初始化算法基类。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 None。

Raises:

ValueError – 当 diffusion_model 不是 ‘IC’ 或 ‘LT’ 时抛出。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

class pynetim.algorithms.heuristic.DegreeDiscountAlgorithm(graph, diffusion_model='IC')[source]

Bases: BaseAlgorithm

度折扣启发式算法。

是 SingleDiscountAlgorithm 的改进版本，考虑了邻居节点之间的影响关系，使用更复杂的折扣公式来更好地评估节点的边际影响力。

该算法速度快且效果较好，适合大规模图的种子选择。

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

References

Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks. KDD, 199-208.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import DegreeDiscountAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = DegreeDiscountAlgorithm(graph, diffusion_model='IC')
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model='IC')[source]

初始化算法基类。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 None。

Raises:

ValueError – 当 diffusion_model 不是 ‘IC’ 或 ‘LT’ 时抛出。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

class pynetim.algorithms.heuristic.EigenvectorCentralityAlgorithm(graph, diffusion_model=None, max_iter=100, tol=1e-06)[source]

Bases: BaseAlgorithm

特征向量中心性启发式算法。

节点的重要性取决于其邻居的重要性。一个节点如果连接了许多重要的节点，那么它自己也更重要。

时间复杂度: O(n * max_iter)

Parameters:

graph (IMGraph)
diffusion_model (str)
max_iter (int)
tol (float)

graph: 输入图对象。

seeds: 种子节点集合。

References

Bonacich, P. (1972). Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology, 2(1), 113-120.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import EigenvectorCentralityAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = EigenvectorCentralityAlgorithm(graph)
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None, max_iter=100, tol=1e-06)[source]

初始化特征向量中心性算法。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型（此算法不使用该参数）。
max_iter (int) – 最大迭代次数，默认 100。
tol (float) – 收敛阈值，默认 1e-6。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

class pynetim.algorithms.heuristic.KShellDecompositionAlgorithm(graph, diffusion_model=None)[source]

Bases: BaseAlgorithm

K-shell 分解启发式算法。

通过迭代移除度数最小的节点，将网络分层。位于核心层（高 k-shell 值）的节点被认为具有更大的影响力。

时间复杂度: O(m)，m 为边数

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

References

Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., & Makse, H. A. (2010). Identification of influential spreaders in complex networks. Nature physics, 6(11), 888-893.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import KShellDecompositionAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = KShellDecompositionAlgorithm(graph)
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None)[source]

初始化算法基类。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 None。

Raises:

ValueError – 当 diffusion_model 不是 ‘IC’ 或 ‘LT’ 时抛出。

static compute_k_shell_values(graph)[source]

计算图中所有节点的 K-shell 值。

使用 Batagelj-Zaversnik 算法，时间复杂度 O(m)。

Parameters:: graph (IMGraph) – IMGraph 图对象。
Returns:: 节点到 K-shell 值的映射。
Return type:: Dict[int, int]

References

Batagelj, V., & Zaversnik, M. (2003). An O(m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049.

Note

此方法是 pynetim.graph.compute_k_shell_values 的便捷包装。

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import KShellDecompositionAlgorithm
>>> graph = IMGraph(edges, directed=True)
>>> k_shell = KShellDecompositionAlgorithm.compute_k_shell_values(graph)

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

class pynetim.algorithms.heuristic.PageRankAlgorithm(graph, diffusion_model=None, damping=0.85, max_iter=100, tol=1e-06)[source]

Bases: BaseAlgorithm

PageRank 启发式算法。

基于 Google 的 PageRank 算法，通过模拟随机游走来评估节点的重要性。节点的重要性取决于指向它的节点的重要性。

时间复杂度: O(n * max_iter)

Parameters:

graph (IMGraph)
diffusion_model (str)
damping (float)
max_iter (int)
tol (float)

graph: 输入图对象。

seeds: 种子节点集合。

References

Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer networks and ISDN systems, 30(1-7), 107-117.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import PageRankAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = PageRankAlgorithm(graph)
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None, damping=0.85, max_iter=100, tol=1e-06)[source]

初始化 PageRank 算法。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型（此算法不使用该参数）。
damping (float) – 阻尼系数，表示继续随机游走的概率，默认 0.85。
max_iter (int) – 最大迭代次数，默认 100。
tol (float) – 收敛阈值，默认 1e-6。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

class pynetim.algorithms.heuristic.SingleDiscountAlgorithm(graph, diffusion_model=None)[source]

Bases: BaseAlgorithm

简单度折扣启发式算法。

通过逐步选择具有最高度数的节点作为种子，并对其邻居节点的度数进行折扣，以避免选择过多相互连接的节点。

该算法速度快，适合大规模图的快速种子选择。

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

References

Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks. KDD, 199-208.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import SingleDiscountAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = SingleDiscountAlgorithm(graph)
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None)[source]

初始化算法基类。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 None。

Raises:

ValueError – 当 diffusion_model 不是 ‘IC’ 或 ‘LT’ 时抛出。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

class pynetim.algorithms.heuristic.VoteRankAlgorithm(graph, diffusion_model=None)[source]

Bases: BaseAlgorithm

VoteRank 启发式算法。

通过投票机制选择分散的影响力节点。每个节点为其邻居投票，得票最高的节点被选为种子，然后其邻居的投票能力被削弱。这样可以避免选择过于聚集的种子节点。

时间复杂度: O(n * k)

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

References

Zhang, J. X., Chen, D. B., Dong, Q., & Zhao, Z. D. (2016). Identifying a set of influential spreaders in complex networks by VoteRank. Physica A: Statistical Mechanics and its Applications, 461, 171-182.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import VoteRankAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = VoteRankAlgorithm(graph)
>>> seeds = algo.run(k=10)

__init__(graph, diffusion_model=None)[source]

初始化算法基类。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 None。

Raises:

ValueError – 当 diffusion_model 不是 ‘IC’ 或 ‘LT’ 时抛出。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)[source]

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。

模拟类算法

class pynetim.algorithms.simulation.CELFAlgorithm(graph, diffusion_model='IC')[source]

Bases: BaseAlgorithm

CELF 算法。

CELF (Cost-Effective Lazy Forward) 是贪婪算法的优化版本，利用边际增益的子模特性减少计算量，通过优先队列维护节点的边际增益，避免重复计算已失效的边际增益。

该算法精度高，比贪婪算法快 2-7 倍，适合中等规模图。

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

diffusion_model: 扩散模型类。

References

Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007). Cost-effective outbreak detection in networks. KDD, 420-429.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import CELFAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = CELFAlgorithm(graph, diffusion_model='IC')
>>> seeds = algo.run(k=10, mc_rounds=1000, use_multithread=True, num_threads=4)

__init__(graph, diffusion_model='IC')[source]

初始化 CELF 算法。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 ‘IC’。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k, mc_rounds=1000, use_multithread=False, num_threads=4, show_progress=True, random_seed=None)[source]

运行 CELF 算法选择种子节点。

Parameters:

k (int) – 需要选择的种子节点数量。
mc_rounds (int) – 蒙特卡洛模拟次数，默认 1000。
use_multithread (bool) – 是否启用多线程，默认 False。
num_threads (int) – 多线程数，默认 4。当 use_multithread=True 时必须大于 0。
show_progress (bool) – 是否显示进度条，默认 True。
random_seed (int | None) – 随机数种子，默认 None（每次结果不同）。

Returns:

选中的种子节点集合。

Return type:

Set[int]

Raises:

ValueError – 当 use_multithread=True 但 num_threads <= 0 时抛出。

Note

利用子模特性，CELF 比贪婪算法快 2-7 倍，同时保证相同的近似比。

class pynetim.algorithms.simulation.CELFPlusAlgorithm(graph, diffusion_model='IC')[source]

Bases: BaseAlgorithm

CELF++ 算法。

CELF++ 是 CELF 算法的改进版本，进一步利用子模特性减少计算量。在更新节点边际增益时，同时考虑当前最佳候选节点，如果该节点增益仍然最大，则直接选择它，避免额外的重新计算。

该算法精度高，比 CELF 更快，适合中等规模图。

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

diffusion_model: 扩散模型类。

References

Goyal, A., Lu, W., & Lakshmanan, L. V. (2011). CELF++: Optimizing the greedy algorithm for influence maximization in social networks. WWW, 47-48.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import CELFPlusAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = CELFPlusAlgorithm(graph, diffusion_model='IC')
>>> seeds = algo.run(k=10, mc_rounds=1000, use_multithread=True, num_threads=4)

__init__(graph, diffusion_model='IC')[source]

初始化 CELF++ 算法。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 ‘IC’。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k, mc_rounds=1000, use_multithread=False, num_threads=4, show_progress=True, random_seed=None)[source]

运行 CELF++ 算法选择种子节点。

Parameters:

k (int) – 需要选择的种子节点数量。
mc_rounds (int) – 蒙特卡洛模拟次数，默认 1000。
use_multithread (bool) – 是否启用多线程，默认 False。
num_threads (int) – 多线程数，默认 4。当 use_multithread=True 时必须大于 0。
show_progress (bool) – 是否显示进度条，默认 True。
random_seed (int | None) – 随机数种子，默认 None（每次结果不同）。

Returns:

选中的种子节点集合。

Return type:

Set[int]

Raises:

ValueError – 当 use_multithread=True 但 num_threads <= 0 时抛出。

Note

CELF++ 比 CELF 更快，同时保证相同的近似比。

class pynetim.algorithms.simulation.GreedyAlgorithm(graph, diffusion_model='IC')[source]

Bases: BaseAlgorithm

贪婪算法。

通过迭代地选择具有最大边际影响力的节点作为种子节点，直到选够 k 个种子节点。每次选择都需要计算所有候选节点的边际增益。

该算法精度高，但速度较慢，适合小规模图或需要高精度的场景。

Parameters:

graph (IMGraph)
diffusion_model (str)

graph: 输入图对象。

seeds: 种子节点集合。

diffusion_model: 扩散模型类。

References

Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the spread of influence through a social network. KDD, 137-146.

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import GreedyAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = GreedyAlgorithm(graph, diffusion_model='IC')
>>> seeds = algo.run(k=10, mc_rounds=1000, use_multithread=True, num_threads=4)

__init__(graph, diffusion_model='IC')[source]

初始化贪婪算法。

Parameters:

graph (IMGraph) – 输入图对象。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 ‘IC’。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k, mc_rounds=1000, use_multithread=False, num_threads=4, show_progress=True, random_seed=None)[source]

运行贪婪算法选择种子节点。

Parameters:

k (int) – 需要选择的种子节点数量。
mc_rounds (int) – 蒙特卡洛模拟次数，默认 1000。
use_multithread (bool) – 是否启用多线程，默认 False。
num_threads (int) – 多线程数，默认 4。当 use_multithread=True 时必须大于 0。
show_progress (bool) – 是否显示进度条，默认 True。
random_seed (int | None) – 随机数种子，默认 None（每次结果不同）。

Returns:

选中的种子节点集合。

Return type:

Set[int]

Raises:

ValueError – 当 use_multithread=True 但 num_threads <= 0 时抛出。

Note

时间复杂度为 O(k * n * mc_rounds)，其中 n 为节点数。对于大规模图，建议使用 CELFAlgorithm 或 IMMAlgorithm。

RIS 类算法

class pynetim.algorithms.ris.BaseRISAlgorithm

Bases: pybind11_object

__init__(graph: IMGraph, model: str, random_seed: int | None = None, verbose: bool = False) → None

初始化基础RIS算法。

Parameters:

graph – 图对象。
model – 扩散模型，支持 ‘IC’ 或 ‘LT’。
random_seed – 随机种子，默认为 None（每次随机）。
verbose – 是否显示关键过程日志，默认为 False。

get_seeds() → set[int]

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: set[int]

run(k: int, num_rr_sets: int) → set[int]

执行RIS算法选择种子节点。

Parameters:

k – 需要选择的种子节点数量。
num_rr_sets – RR集合采样数量，越大越准确。

Returns:

选中的种子节点集合。

Return type:

set[int]

class pynetim.algorithms.ris.IMMAlgorithm

Bases: BaseRISAlgorithm

__init__(graph: IMGraph, model: str, epsilon: float = 0.5, l: int = 1, random_seed: int | None = None, verbose: bool = False) → None

初始化IMM算法。

Parameters:

graph – 图对象。
model – 扩散模型，支持 ‘IC’ 或 ‘LT’。
epsilon – 近似参数ε，默认为 0.5。
l – 失败概率参数，默认为 1。
random_seed – 随机种子，默认为 None（每次随机）。
verbose – 是否显示关键过程日志，默认为 False。

get_seeds() → set[int]

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: set[int]

run(k: int) → set[int]

执行IMM算法选择种子节点。

IMM会自动估计最优采样数量，无需手动指定。

Parameters:: k – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: set[int]

class pynetim.algorithms.ris.OPIMAlgorithm

Bases: BaseRISAlgorithm

__init__(graph: IMGraph, model: str, random_seed: int | None = None, verbose: bool = False) → None

初始化OPIM算法。

OPIM (Online Processing for Influence Maximization) 使用两组独立的RR集合： - R1用于贪心选择种子节点 - R2用于验证选中种子的影响力

参考文献:: Jing Tang, Xueyan Tang, Xiaokui Xiao, Junsong Yuan, “Online Processing Algorithms for Influence Maximization,” in Proc. ACM SIGMOD, 2018.

Parameters:

graph – 图对象。
model – 扩散模型，支持 ‘IC’ 或 ‘LT’。
random_seed – 随机种子，默认为 None（每次随机）。
verbose – 是否显示关键过程日志，默认为 False。

get_approximation() → float

获取最后一次运行的近似保证值。

Returns:: 近似保证值 α。
Return type:: float

get_influence() → float

获取最后一次运行的影响力估计值（通过R2验证集）。

Returns:: 影响力估计值。
Return type:: float

get_seeds() → set[int]

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: set[int]

run(k: int, num_rr_sets: int, delta: float = -1.0) → set[int]

执行OPIM算法选择种子节点。

OPIM使用固定数量的RR集合，训练集和验证集使用相同大小。

Parameters:

k – 需要选择的种子节点数量。
num_rr_sets – 训练集和验证集各使用的RR集合数量。
delta – 失败概率参数，默认为 1/n。

Returns:

选中的种子节点集合。

Return type:

set[int]

class pynetim.algorithms.ris.OPIMCAlgorithm

Bases: OPIMAlgorithm

__init__(graph: IMGraph, model: str, random_seed: int | None = None, verbose: bool = False) → None

初始化OPIM-C算法。

OPIM-C是OPIM的自适应版本，迭代增加RR集合数量，直到达到(1-1/e-ε)近似保证。

参考文献:: Jing Tang, Xueyan Tang, Xiaokui Xiao, Junsong Yuan, “Online Processing Algorithms for Influence Maximization,” in Proc. ACM SIGMOD, 2018.

Parameters:

graph – 图对象。
model – 扩散模型，支持 ‘IC’ 或 ‘LT’。
random_seed – 随机种子，默认为 None（每次随机）。
verbose – 是否显示关键过程日志，默认为 False。

get_approximation() → float

获取最后一次运行的近似保证值。

Returns:: 近似保证值 α。
Return type:: float

get_influence() → float

获取最后一次运行的影响力估计值（通过R2验证集）。

Returns:: 影响力估计值。
Return type:: float

get_seeds() → set[int]

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: set[int]

run(k: int, epsilon: float, delta: float = -1.0) → set[int]

执行OPIM-C算法选择种子节点。

OPIM-C会自动迭代增加RR集合数量，直到达到目标近似保证。

Parameters:

k – 需要选择的种子节点数量。
epsilon – 误差阈值，算法返回(1-1/e-ε)-近似解。
delta – 失败概率参数，默认为 1/n。

Returns:

选中的种子节点集合。

Return type:

set[int]

class pynetim.algorithms.ris.TIMAlgorithm

Bases: BaseRISAlgorithm

__init__(graph: IMGraph, model: str, epsilon: float = 0.5, l: int = 1, random_seed: int | None = None, verbose: bool = False) → None

初始化TIM算法。

Parameters:

graph – 图对象。
model – 扩散模型，支持 ‘IC’ 或 ‘LT’。
epsilon – 近似参数ε，默认为 0.5。
l – 失败概率参数，默认为 1。
random_seed – 随机种子，默认为 None（每次随机）。
verbose – 是否显示关键过程日志，默认为 False。

get_seeds() → set[int]

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: set[int]

run(k: int) → set[int]

执行TIM算法选择种子节点。

Parameters:: k – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: set[int]

class pynetim.algorithms.ris.TIMPlusAlgorithm

Bases: BaseRISAlgorithm

__init__(graph: IMGraph, model: str, epsilon: float = 0.5, l: int = 1, random_seed: int | None = None, verbose: bool = False) → None

初始化TIM+算法。

TIM+改进了TIM的采样策略，通常比TIM更快。

Parameters:

graph – 图对象。
model – 扩散模型，支持 ‘IC’ 或 ‘LT’。
epsilon – 近似参数ε，默认为 0.5。
l – 失败概率参数，默认为 1。
random_seed – 随机种子，默认为 None（每次随机）。
verbose – 是否显示关键过程日志，默认为 False。

get_seeds() → set[int]

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: set[int]

run(k: int) → set[int]

执行TIM+算法选择种子节点。

Parameters:: k – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: set[int]

深度学习算法

深度学习影响力最大化算法模块。

此模块包含纯深度学习算法（非强化学习）。深度强化学习算法已移动到 reinforcement_learning.deep 模块。

class pynetim.algorithms.deep_learning.BaseDLAlgorithm(graph, pretrained=True, weights_path=None, device='auto', diffusion_model=None)[source]

Bases: BaseAlgorithm

深度学习影响力最大化算法基类。

为深度学习算法提供基础框架，包含设备管理、权重加载等功能。

Parameters:

graph (IMGraph)
pretrained (bool)
weights_path (Optional[str])
device (str)
diffusion_model (str)

device: 计算设备 (CPU/GPU)。

model: 神经网络模型。

Example

>>> from pynetim import IMGraph
>>> from pynetim.algorithms import ToupleGDDAlgorithm
>>>
>>> graph = IMGraph(edges, weights=0.3)
>>> algo = ToupleGDDAlgorithm(graph, pretrained=True)
>>> seeds = algo.run(k=10)

__init__(graph, pretrained=True, weights_path=None, device='auto', diffusion_model=None)[source]

初始化深度学习算法基类。

Parameters:

graph (IMGraph) – 输入图对象。
pretrained (bool) – 是否使用预训练权重，默认为 True。
weights_path (Optional[str]) – 本地权重路径，优先级高于 pretrained。
device (str) – 计算设备，支持 ‘auto’、’cpu’、’cuda’，默认为 ‘auto’。
diffusion_model (str) – 扩散模型名称，支持 ‘IC’ 或 ‘LT’，默认为 None。

get_seeds()

获取最后一次运行选出的种子集合。

Returns:: 种子节点集合。
Return type:: Set[int]

run(k)

执行算法选择种子节点。

子类必须实现此方法来定义具体的算法逻辑。

Parameters:: k (int) – 需要选择的种子节点数量。
Returns:: 选中的种子节点集合。
Return type:: Set[int]
Raises:: NotImplementedError – 子类未实现此方法时抛出。