拓扑

与图拓扑相关的函数。

连通性

sknetwork.topology.get_connected_components(input_matrix: csr_matrix, connection: str = 'weak', force_bipartite: bool = False) → ndarray[source]

提取图的连通分量。

参数:

  • input_matrix – 输入矩阵（图的邻接矩阵或二部邻接矩阵）。

  • connection – 必须是 'weak'（默认）或 'strong'。用于有向图的连接类型。

  • force_bipartite (bool) – 如果 True，则将输入矩阵视为二部图的二部邻接矩阵。

返回值:

每个节点的连通分量。对于二部图，行和列被连接在一起（行在前）。

返回类型:

labels

示例

>>> from sknetwork.topology import get_connected_components
>>> from sknetwork.data import house
>>> get_connected_components(house())
array([0, 0, 0, 0, 0], dtype=int32)
sknetwork.topology.is_connected(input_matrix: csr_matrix, connection: str = 'weak', force_bipartite: bool = False) → bool[source]

检查图是否连通。

参数:

  • input_matrix – 输入矩阵（图的邻接矩阵或二部邻接矩阵）。

  • connection – 必须是 'weak'（默认）或 'strong'。用于有向图的连接类型。

  • force_bipartite (bool) – 如果 True，则将输入矩阵视为二部图的二部邻接矩阵。

示例

>>> from sknetwork.topology import is_connected
>>> from sknetwork.data import house
>>> is_connected(house())
True
sknetwork.topology.get_largest_connected_component(input_matrix: csr_matrix, connection: str = 'weak', force_bipartite: bool = False, return_index: bool = False) → csr_matrix | Tuple[csr_matrix, ndarray][source]

提取图中最大的连通分量。二部图被视为无向图。

参数:

  • input_matrix – 图的邻接矩阵或二部邻接矩阵。

  • connection – 必须是 'weak'（默认）或 'strong'。用于有向图的连接类型。

  • force_bipartite (bool) – 如果 True，则将输入矩阵视为二部图的二部邻接矩阵。

  • return_index (bool) – 是否返回原始图中最大连通分量节点的索引。

返回值:

  • output_matrix (sparse.csr_matrix) – 最大连通分量的邻接矩阵或二部邻接矩阵。

  • index (array) – 原始图中节点的索引。对于二部图，行和列被连接在一起（行在前）。

示例

>>> from sknetwork.topology import get_largest_connected_component
>>> from sknetwork.data import house
>>> get_largest_connected_component(house()).shape
(5, 5)

结构

sknetwork.topology.is_bipartite(adjacency: csr_matrix, return_biadjacency: bool = False) → bool | Tuple[bool, csr_matrix | None, ndarray | None, ndarray | None][source]

检查图是否为二部图。

参数:

  • adjacency – 图的邻接矩阵（对称）。

  • return_biadjacency – 如果 True，则返回图的二部邻接矩阵（如果为二部图）。

返回值:

  • is_bipartite (bool) – 一个布尔值，表示图是否为二部图。

  • biadjacency (sparse.csr_matrix) – 如果为二部图，则为图的二部邻接矩阵（可选）。

  • rows (np.ndarray) – 原始图中行的索引（可选）。

  • cols (np.ndarray) – 原始图中列的索引（可选）。

示例

>>> from sknetwork.topology import is_bipartite
>>> from sknetwork.data import cyclic_graph
>>> is_bipartite(cyclic_graph(4))
True
>>> is_bipartite(cyclic_graph(3))
False

循环

sknetwork.topology.is_acyclic(adjacency: csr_matrix, directed: bool | None = None) → bool[source]

检查图是否没有循环。

参数:

  • adjacency – 图的邻接矩阵。

  • directed – 是否将图视为有向图（如果未指定，则推断）。

返回值:

is_acyclic – 一个布尔值，如果图没有循环则值为 True，否则为 False。

返回类型:

bool

示例

>>> from sknetwork.topology import is_acyclic
>>> from sknetwork.data import star, grid
>>> is_acyclic(star())
True
>>> is_acyclic(grid())
False
sknetwork.topology.get_cycles(adjacency: csr_matrix, directed: bool | None = None) → List[List[int]][source]

获取图中所有可能的循环。

参数:

  • adjacency – 图的邻接矩阵。

  • directed – 是否将图视为有向图（如果未指定，则推断）。

返回值:

cycles – 循环列表，每个循环表示为节点列表。

返回类型:

list

示例

>>> from sknetwork.topology import get_cycles
>>> from sknetwork.data import cyclic_digraph
>>> graph = cyclic_digraph(4, metadata=True)
>>> get_cycles(graph.adjacency, directed=True)
[[0, 1, 2, 3]]
sknetwork.topology.break_cycles(adjacency: csr_matrix, root: int | List[int], directed: bool | None = None) → csr_matrix[source]

从给定的根节点中打破图的循环。

参数:

  • adjacency – 图的邻接矩阵。

  • root – 要打破循环的根节点或根节点列表。

  • directed – 是否将图视为有向图（如果未指定，则推断）。

返回值:

adjacency – 无环图的邻接矩阵。

返回类型:

sparse.csr_matrix

示例

>>> from sknetwork.topology import break_cycles, is_acyclic
>>> from sknetwork.data import cyclic_digraph
>>> adjacency = cyclic_digraph(4)
>>> dag = break_cycles(adjacency, root=0, directed=True)
>>> is_acyclic(dag, directed=True)
True

核心分解

class sknetwork.topology.get_core_decomposition(adjacency: ndarray | csr_matrix)

获取图的 k-core 分解。

参数:

adjacency (numpy.ndarray | scipy.sparse._csr.csr_matrix) – 图的邻接矩阵。

返回值:

每个节点的核心值。

返回类型:

core_values

示例

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> core_values = get_core_decomposition(adjacency)
>>> len(core_values)
34

三角形

class sknetwork.topology.count_triangles(adjacency: csr_matrix, parallelize: bool = False)

统计图中三角形的数量。图被认为是无向的。

参数:

  • adjacency (scipy.sparse._csr.csr_matrix) – 图的邻接矩阵。

  • parallelize (bool) – 如果 True，在列出三角形时使用并行范围。

返回值:

n_triangles – 三角形的数量。

返回类型:

int

示例

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> count_triangles(adjacency)
45
class sknetwork.topology.get_clustering_coefficient(adjacency: csr_matrix, parallelize: bool = False)

获取图的聚类系数。

参数:

  • adjacency (scipy.sparse._csr.csr_matrix) – 图的邻接矩阵。

  • parallelize (bool) – 如果 True，在列出三角形时使用并行范围。

返回值:

coefficient – 聚类系数。

返回类型:

float

示例

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> np.round(get_clustering_coefficient(adjacency), 2)
0.26

团

class sknetwork.topology.count_cliques(adjacency: csr_matrix, clique_size: int = 3)

统计某个大小的团的数量。

参数:

  • adjacency (scipy.sparse._csr.csr_matrix) – 图的邻接矩阵。

  • clique_size (int) – 团的大小（默认 = 3，对应于三角形。

返回值:

n_cliques – 团的数量。

返回类型:

int

示例

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> count_cliques(adjacency, 3)
45

参考资料

Danisch, M., Balalau, O., & Sozio, M. (2018, April). Listing k-cliques in sparse real-world graphs. In Proceedings of the 2018 World Wide Web Conference (pp. 589-598).

同构

class sknetwork.topology.color_weisfeiler_lehman(adjacency: csr_matrix | ndarray, max_iter: int = -1)[source]

使用 Weisfeiler-Lehman 算法对节点进行着色。

参数:

  • adjacency (sparse.csr_matrix) – 图的邻接矩阵

  • max_iter (int) – 最大迭代次数。负值表示没有限制（直到收敛）。

返回值:

labels – 每个节点的标签。

返回类型:

np.ndarray

示例

>>> from sknetwork.data import house
>>> adjacency = house()
>>> labels = color_weisfeiler_lehman(adjacency)
>>> print(labels)
[0 2 1 1 2]

参考资料

sknetwork.topology.are_isomorphic(adjacency1: csr_matrix, adjacency2: csr_matrix, max_iter: int = -1) → bool[source]

Weisfeiler-Lehman 同构测试。如果测试结果为 False，则图不可能同构。

参数:

  • adjacency1 – 第一个邻接矩阵。

  • adjacency2 – 第二个邻接矩阵。

  • max_iter (int) – 最大迭代次数。负值表示没有限制（直到收敛）。

返回值:

test_result

返回类型:

bool

示例

>>> from sknetwork.data import house, bow_tie
>>> are_isomorphic(house(), bow_tie())
False

参考资料