拓撲

與圖拓撲相關的函式。

連通性

sknetwork.topology.get_connected_components(input_matrix: csr_matrix, connection: str = 'weak', force_bipartite: bool = False) → ndarray[原始程式碼]

擷取圖的連通元件。

參數:

  • input_matrix – 輸入矩陣（圖的鄰接矩陣或二元鄰接矩陣）。

  • connection – 必須是 'weak'（預設值）或 'strong'。有向圖連線類型的使用。

  • force_bipartite (布林值) – 如果 True，則將輸入矩陣視為二分圖的二元鄰接矩陣。

傳回:

各個節點的連通元件。對於二分圖，列和欄會串聯（列排前面）。

回覆類型:

標籤

範例

>>> 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 (布林值) – 如果 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]

擷取圖形中最大的連通元件。二分圖視為非定向圖。

參數:

  • 輸入矩陣 – 圖形的鄰接矩陣或雙鄰接矩陣。

  • connection – 必須是 'weak'（預設值）或 'strong'。有向圖連線類型的使用。

  • force_bipartite (布林值) – 如果 True，則將輸入矩陣視為二分圖的二元鄰接矩陣。

  • 傳回索引 (布林) – 是否傳回原始圖形中最大連結成分的節點索引。

傳回:

  • 輸出矩陣 (sparse.csr_matrix) – 最大連結成分的鄰接矩陣或雙鄰接矩陣。

  • 索引 (陣列) – 原始圖形中節點的索引。對於二部圖，會串接行和列（優先為行）。

範例

>>> 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][來源]

檢查圖形是否為二部圖。

參數:

  • adjacency – 圖形的鄰接矩陣（對稱）。

  • return_biadjacency – 如果 True，如果為二部圖，則傳回圖形的雙鄰接矩陣。

傳回:

  • is_bipartite (布林) – 表示圖形是否為二部圖的布林值。

  • 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 核分解。

參數:

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)

計算圖表的三角形總數。該圖表是非導向圖形。

參數:

  • 鄰接矩陣(scipy.sparse._csr.csr_matrix) – 圖表的鄰接矩陣。

  • 並列(bool) – 如果 True，在列出三角形時使用並列範圍。

傳回:

三角形總數 – 三角形總數。

回覆類型:

int

範例

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> count_triangles(adjacency)
45
類別 sknetwork.topology.get_clustering_coefficient(鄰接矩陣: csr_matrix, 並列: bool = False)

取得圖表的群聚係數。

參數:

  • 鄰接矩陣(scipy.sparse._csr.csr_matrix) – 圖表的鄰接矩陣。

  • 並列(bool) – 如果 True，在列出三角形時使用並列範圍。

傳回:

係數 – 群聚係數。

回覆類型:

浮點數

範例

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

團

類別 sknetwork.topology.count_cliques(鄰接矩陣: csr_matrix, 團大小: int = 3)

計算特定大小的團數量。

參數:

  • 鄰接矩陣(scipy.sparse._csr.csr_matrix) – 圖表的鄰接矩陣。

  • 團大小(int) – 團大小 (預設 = 3，對應至三角形。

傳回:

團數量 – 團數量。

回覆類型:

int

範例

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

參考文獻

Danisch, M., Balalau, O., & Sozio, M. (2018, 4 月). 列出稀疏現實世界圖表中的 k 個團。 收錄於《2018 年萬維網會議論文集》(第 589-598 頁)。

同構

類別 sknetwork.topology.color_weisfeiler_lehman(鄰接陣列: csr_矩陣 | ndarray, 最大迭代次數: 整數 = -1)[原始碼]

使用 Weisfeiler-Lehman 演算法為節點著色

參數:

  • 鄰接陣列 (sparse.csr_matrix) – 圖形的鄰接陣列

  • 最大迭代次數 (整數) – 最大迭代次數。負值表示沒有限制（直到收斂）。

傳回:

標籤 – 每個節點的標籤

回覆類型:

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(鄰接陣列1: csr_矩陣, 鄰接陣列2: csr_矩陣, 最大迭代次數: 整數 = -1) → 布林[原始碼]

Weisfeiler-Lehman 同構測試。如果測試為 False，則圖形無法同構。

參數:

  • 鄰接陣列1 – 第一個鄰接陣列

  • 鄰接陣列2 – 第二個鄰接陣列

  • 最大迭代次數 (整數) – 最大迭代次數。負值表示沒有限制（直到收斂）。

傳回:

test_result

回覆類型:

bool

範例

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

參考文獻