图模块

class pynetim.graph.IMGraph

Bases: pybind11_object

__init__(edges: list[tuple[int, int]], weights: float | list[float] = 1.0, directed: bool = True, renumber: bool = True) → None

从边列表构建图。

传入的边列表必须是从 0 开始连续编号节点，若不是请设置 renumber=True。或者在构建图之前使用 renumber_edges 函数重新编号节点。

Parameters:

edges – 边列表，每个元素为 (u, v) 元组。
weights – 边权重。若为列表则指定每条边的权重；若为浮点数则统一权重。默认为 1.0。
directed – 是否为有向图，默认为 True。
renumber – 是否重新编号节点。若为 True，将节点重新编号为从 0 开始的连续整数。默认为 True。

Returns:

图对象。

Return type:

IMGraph

add_edge(u: int, v: int, w: float = 1.0) → None

添加带权边。

Parameters:

u – 源节点。
v – 目标节点。
w – 边权重，默认为 1.0。

add_edges(edges: list[tuple[int, int]], weights: list[float] = []) → None

批量添加边。

Parameters:

edges – 边列表，每个元素为 (u, v) 元组。
weights – 边权重列表。

batch_degree(nodes: list[int]) → list[int]

批量返回指定节点的度数。

Parameters:: nodes – 节点 ID 列表。
Returns:: 度数列表。
Return type:: List[int]

batch_get_edge_weight(edges: list[tuple[int, int]], default_value: float = 0.0, raise_on_missing: bool = False) → list[float]

批量返回指定边的权重。

Parameters:

edges – 边列表，每个元素为 (u, v) 元组。
default_value – 边不存在时的默认返回值，默认为 0.0。当 raise_on_missing=True 时忽略。
raise_on_missing – 边不存在时是否抛出异常，默认为 False。

Returns:

权重列表。

Return type:

List[float]

Raises:

RuntimeError – 当 raise_on_missing=True 且边不存在时。

batch_in_degree(nodes: list[int]) → list[int]

批量返回指定节点的入度。

Parameters:: nodes – 节点 ID 列表。
Returns:: 入度列表。
Return type:: List[int]

batch_out_degree(nodes: list[int]) → list[int]

批量返回指定节点的出度。

Parameters:: nodes – 节点 ID 列表。
Returns:: 出度列表。
Return type:: List[int]

batch_out_neighbors(nodes: list[int]) → list[list[int]]

批量返回指定节点的出边邻居。

Parameters:: nodes – 节点 ID 列表。
Returns:: 每个节点的出边邻居节点 ID 列表。
Return type:: List[List[int]]

batch_out_neighbors_with_weights(nodes: list[int]) → list[list[tuple[int, float]]]

批量返回指定节点的出边邻居及权重。

Parameters:: nodes – 节点 ID 列表。
Returns:: 每个节点的 (邻居, 权重) 元组列表。
Return type:: List[List[Tuple[int, float]]]

degree(u: int) → int

返回节点的度数。

Parameters:: u – 节点 ID。
Returns:: 度数。
Return type:: int

property directed: 是否为有向图。

property edges: 边列表及权重。

get_adj_list() → list[list[Edge]]

返回完整邻接表。

Returns:: Edge 对象列表的列表。
Return type:: List[List[Edge]]

get_adj_list_py() → list[list[tuple[int, float]]]

返回 Python 友好格式的邻接表。

Returns:: (邻居, 权重) 元组列表的列表。
Return type:: List[List[Tuple[int, float]]]

get_adj_matrix() → list[list[float]]

返回稠密邻接矩阵。

Returns:: 邻接矩阵。
Return type:: List[List[float]]

get_adj_matrix_sparse() → list[tuple[int, int, float]]

返回稀疏邻接矩阵。

Returns:: (u, v, 权重) 元组列表。
Return type:: List[Tuple[int, int, float]]

get_all_degrees() → list[int]

返回所有节点的度数列表。

Returns:: 度数列表。
Return type:: List[int]

get_all_in_degrees() → list[int]

返回所有节点的入度列表。

Returns:: 入度列表。
Return type:: List[int]

get_all_out_degrees() → list[int]

返回所有节点的出度列表。

Returns:: 出度列表。
Return type:: List[int]

get_edge_weight(u: int, v: int) → float

获取边的权重。若边不存在则抛出异常。

Parameters:

u – 源节点。
v – 目标节点。

Returns:

边权重。

Return type:

float

Raises:

RuntimeError – 边不存在。

has_edge(u: int, v: int) → bool

检查边是否存在。

Parameters:

u – 源节点。
v – 目标节点。

Returns:

边存在返回 True，否则返回 False。

Return type:

bool

in_degree(u: int) → int

返回节点的入度。

Parameters:: u – 节点 ID。
Returns:: 入度。
Return type:: int

in_neighbors(u: int) → list[int]

返回节点的入边邻居。

Parameters:: u – 节点 ID。
Returns:: 入边邻居节点 ID 列表。
Return type:: List[int]

property internal_to_original: 内部节点 ID 到原始 ID 的映射。

property num_edges: 边数量。

property num_nodes: 节点数量。

property original_to_internal: 原始节点 ID 到内部 ID 的映射。

out_degree(u: int) → int

返回节点的出度。

Parameters:: u – 节点 ID。
Returns:: 出度。
Return type:: int

out_neighbors(u: int) → list[int]

返回节点的出边邻居。

Parameters:: u – 节点 ID。
Returns:: 出边邻居节点 ID 列表。
Return type:: List[int]

out_neighbors_arrays(u: int) → tuple[list[int], list[float]]

返回节点的出边邻居（数组格式）。

Parameters:: u – 节点 ID。
Returns:: 两个并行数组 (targets, weights)，O(1) 访问每个元素。
Return type:: Tuple[List[int], List[float]]

out_neighbors_with_weights(u: int) → list[tuple[int, float]]

返回节点的出边邻居及权重。

Parameters:: u – 节点 ID。
Returns:: (邻居, 权重) 元组列表。
Return type:: List[Tuple[int, float]]

remove_edge(u: int, v: int) → None

删除边。

Parameters:

u – 源节点。
v – 目标节点。

remove_edges(edges: list[tuple[int, int]]) → None

批量删除边。

Parameters:: edges – 边列表，每个元素为 (u, v) 元组。

update_edge_weight(u: int, v: int, w: float) → None

更新已有边的权重。

Parameters:

u – 源节点。
v – 目标节点。
w – 新的边权重。

pynetim.graph.compute_k_shell_values(graph)[source]

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

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

K-shell 分解是一种识别网络核心层次结构的方法： - K-shell 值高的节点位于网络核心 - K-shell 值低的节点位于网络边缘

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.

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.graph import compute_k_shell_values
>>>
>>> graph = IMGraph(edges, directed=True)
>>> k_shell = compute_k_shell_values(graph)
>>> print(k_shell)  # {0: 1, 1: 2, 2: 1, ...}

pynetim.graph.generate_ba_graph(n, m, directed=True, random_seed=None)[source]

生成 Barabási-Albert 无标度网络。

通过优先连接机制生成具有幂律度分布的网络。

Parameters

nint: 最终节点数量。
mint: 每个新节点连接的边数，必须小于 n。
directedbool, optional: 是否有向图，默认 True。
random_seedint, optional: 随机种子，用于可重复性。

Returns

IMGraph: 生成的无标度网络。

References

Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512.

Examples

>>> from pynetim.graph import generate_ba_graph
>>> g = generate_ba_graph(n=100, m=3, random_seed=42)
>>> print(f"节点数: {g.num_nodes}, 边数: {g.num_edges}")

Parameters:

n (int)
m (int)
directed (bool)
random_seed (int | None)

Return type:

IMGraph

pynetim.graph.generate_er_graph(n, p, directed=True, random_seed=None)[source]

生成 Erdős-Rényi 随机图 (G(n, p) 模型)。

每对节点之间以概率 p 连接一条边。

Parameters

nint: 节点数量。
pfloat: 边连接概率，取值范围 [0, 1]。
directedbool, optional: 是否有向图，默认 True。
random_seedint, optional: 随机种子，用于可重复性。

Returns

IMGraph: 生成的随机图。

References

Erdős, P., & Rényi, A. (1959). On random graphs I. Publicationes Mathematicae, 6, 290-297.

Examples

>>> from pynetim.graph import generate_er_graph
>>> g = generate_er_graph(n=100, p=0.1, random_seed=42)
>>> print(f"节点数: {g.num_nodes}, 边数: {g.num_edges}")

Parameters:

n (int)
p (float)
directed (bool)
random_seed (int | None)

Return type:

IMGraph

pynetim.graph.generate_ws_graph(n, k, beta, directed=True, random_seed=None)[source]

生成 Watts-Strogatz 小世界网络。

从环形规则网络开始，以概率 beta 重连边。

Parameters

nint: 节点数量。
kint: 每个节点连接的邻居数（必须是偶数）。
betafloat: 重连概率，取值范围 [0, 1]。 - beta=0: 规则网络 - beta=1: 随机网络 - beta~0.1: 小世界网络
directedbool, optional: 是否有向图，默认 True。
random_seedint, optional: 随机种子，用于可重复性。

Returns

IMGraph: 生成的小世界网络。

References

Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440-442.

Examples

>>> from pynetim.graph import generate_ws_graph
>>> g = generate_ws_graph(n=100, k=4, beta=0.1, random_seed=42)
>>> print(f"节点数: {g.num_nodes}, 边数: {g.num_edges}")

Parameters:

n (int)
k (int)
beta (float)
directed (bool)
random_seed (int | None)

Return type:

IMGraph

pynetim.graph.set_const_weights(graph, value)[source]

设置常数边权重。

Parameters:

graph (IMGraph) – 图对象。
value (float) – 常数权重值。

Raises:

ValueError – 权重值不在 (0, 1] 范围内时抛出。

Return type:

None

Examples

>>> from pynetim.graph import generate_er_graph, set_const_weights
>>> g = generate_er_graph(n=100, p=0.1)
>>> set_const_weights(g, value=0.1)

pynetim.graph.set_edge_weights(graph, weight_type, *, const_value=0.01, tv_values=None, uniform_low=0.001, uniform_high=0.1)[source]

设置图的边权重。

Parameters:

graph (IMGraph) – 图对象。
weight_type (Literal['const', 'tv', 'uniform', 'wc']) – 权重类型： - “const”: 常数权重 - “tv”: 从列表中随机选择 - “uniform”: 均匀分布随机 - “wc”: WC 模型，权重 = 1 / 入度
const_value (float) – 常数权重值，仅当 weight_type=”const” 时使用，默认 0.01。
tv_values (List[float]) – 可选权重值列表，仅当 weight_type=”tv” 时使用，默认 [0.001, 0.01, 0.1]。
uniform_low (float) – 均匀分布下界，仅当 weight_type=”uniform” 时使用，默认 0.001。
uniform_high (float) – 均匀分布上界，仅当 weight_type=”uniform” 时使用，默认 0.1。

Raises:

ValueError – 参数无效时抛出。

Return type:

None

Examples

>>> from pynetim.graph import generate_er_graph, set_edge_weights
>>> g = generate_er_graph(n=100, p=0.1)
>>> set_edge_weights(g, "const", const_value=0.1)
>>> set_edge_weights(g, "wc")

pynetim.graph.set_edge_weights_dict(graph, weight_dict)[source]

通过字典设置边权重。

Parameters:

graph (IMGraph) – 图对象。
weight_dict (Dict[Tuple[int, int], float]) – 边权重字典，键为 (u, v) 元组，值为权重。

Raises:

ValueError – 权重值无效或边不存在时抛出。

Return type:

None

Examples

>>> from pynetim.graph import generate_er_graph, set_edge_weights_dict
>>> g = generate_er_graph(n=10, p=0.5, random_seed=42)
>>> weights = {(0, 1): 0.1, (1, 2): 0.2, (2, 3): 0.3}
>>> set_edge_weights_dict(g, weights)

pynetim.graph.set_tv_weights(graph, values)[source]

从列表中随机选择边权重。

Parameters:

graph (IMGraph) – 图对象。
values (List[float]) – 权重值列表。

Raises:

ValueError – 权重值列表为空或权重值不在 (0, 1] 范围内时抛出。

Return type:

None

Examples

>>> from pynetim.graph import generate_er_graph, set_tv_weights
>>> g = generate_er_graph(n=100, p=0.1)
>>> set_tv_weights(g, values=[0.001, 0.01, 0.1])

pynetim.graph.set_uniform_weights(graph, low, high)[source]

设置均匀分布边权重。

Parameters:

graph (IMGraph) – 图对象。
low (float) – 均匀分布下界。
high (float) – 均匀分布上界。

Raises:

ValueError – 参数无效时抛出。

Return type:

None

Examples

>>> from pynetim.graph import generate_er_graph, set_uniform_weights
>>> g = generate_er_graph(n=100, p=0.1)
>>> set_uniform_weights(g, low=0.01, high=0.5)

pynetim.graph.set_wc_weights(graph)[source]

设置 WC 模型边权重。

权重 = 1 / 入度。

Parameters:: graph (IMGraph) – 图对象。
Return type:: None

Examples

>>> from pynetim.graph import generate_er_graph, set_wc_weights
>>> g = generate_er_graph(n=100, p=0.1)
>>> set_wc_weights(g)