分群

分群演算法。

屬性 labels_ 為圖形的每個節點指定一個標籤 (群集索引)。

魯汶

魯汶演算法旨在最大化模組化。有數種模組化變異可用

模組化	公式
紐曼 (`'newman'`)	\(Q = \frac{1}{w} \sum_{i,j}\left(A_{ij} - \gamma \frac{d_id_j}{w}\right)\delta_{c_i,c_j}\)
杜格 (`'dugue'`)	\(Q = \frac{1}{w} \sum_{i,j}\left(A_{ij} - \gamma \frac{d^+_id^-_j}{w}\right)\delta_{c_i,c_j}\)
普茲 (`'potts'`)	\(Q = \sum_{i,j}\left(\frac{A_{ij}}{w} - \gamma \frac{1}{n^2}\right)\delta_{c_i,c_j}\)

其中

\(A\) 是鄰接矩陣，
\(c_i\) 是節點 \(i\) 的叢集。
\(d_i\) 是節點 \(i\) 的程度。
\(d^+_i, d^-_i\) 是節點 \(i\) 的出度和入度 (針對有向圖)。
\(w = 1^TA1\) 是度數的和。
\(\delta\) 是克羅內克符號。
\(\gamma \ge 0\) 是解析度參數。

請注意，對於無向圖，Newman 和 Dugué 的變異形式相當。

對於二分圖，考慮的鄰接矩陣 \(A\) 取決於模組化。對於 Newman 和 Potts 變異形式，圖表被認為是無向的，這樣

\(A = \begin{pmatrix} 0 & B\\B^T & 0\end{pmatrix}\)

對於 Dugué 變異形式，圖表被視為有向的，如下所示

\(A = \begin{pmatrix} 0 & B\\0 & 0\end{pmatrix}\)

這是預設選項，且對應於 Barber 的模組化（請參閱以下的參考文獻）。

當圖表加權時，節點的度數會被其權重取代（邊權數的和）。

class sknetwork.clustering.Louvain(resolution: float = 1, modularity: str = 'dugue', tol_optimization: float = 0.001, tol_aggregation: float = 0.001, n_aggregations: int = -1, shuffle_nodes: bool = False, sort_clusters: bool = True, return_probs: bool = True, return_aggregate: bool = True, random_state: RandomState | int | None = None, verbose: bool = False)[source]

Louvain 演算法透過最大化模組化為圖表進行叢集。

對於二分圖，演算法預設最大化 Barber 的模組化。

參數:

解析度 – 解析度參數。
模組化 (字串) – 要最大化的模組化類型。可以是 'Dugue'、'Newman' 或 'Potts'（預設值 = 'dugue'）。
tol_optimization – 在本地搜尋中進入新的最佳化階段所需的模組化最小增幅。
tol_aggregation – 在進入新的聚集階段所需的模組化最小增幅。
n_aggregations – 最大聚集數。負值表示沒有限制。
shuffle_nodes – 在最佳化之前啟用節點改組調整。
sort_clusters – 如果為 True，則依照叢集大小遞減順序來對標籤進行排序。
return_probs – 如果為 True，則傳回叢集的機率分布（軟式叢集）。
return_aggregate – 如果為 True，則傳回叢集間的圖表鄰接矩陣。
random_state – 隨機數字產生器或隨機種子。如果為 None，則使用 numpy.random。
verbose – 詳細模式。

變數:

標籤 (np.ndarray, shape (n_labels,)) – 各個節點的標籤。
機率（稀疏的.csr_matrix，形狀（n_列，n_標籤））– 標籤的機率分佈。
標籤_欄（標籤_行，）– 二分圖的列和行的標籤。
機率_欄（機率_行，）– 二分圖的列和行的標籤機率分佈。
群集（稀疏的.csr_matrix）– 群集之間的總合鄰接矩陣或二分圖矩陣。

範例

>>> from sknetwork.clustering import Louvain
>>> from sknetwork.data import karate_club
>>> louvain = Louvain()
>>> adjacency = karate_club()
>>> labels = louvain.fit_predict(adjacency)
>>> len(set(labels))
4

參考文獻

Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008)。快速展開大型網路中的社群。統計力學期刊：理論與實驗，2008 年。
Dugué, N.，＆ Perez, A. (2015)。導向魯汶：最大化導向網路的模組性（博士論文，奧爾良大學）。
Barber, M. J. (2007)。二分圖中的模組性與社群偵測，物理評論 E，76(6)。

訓練(輸入_矩陣: csr_矩陣 | ndarray, 強制_二分圖: 布林值 = 錯誤) → 魯汶[來源]

擬合演算法到資料。

參數:

輸入_矩陣 – 圖的鄰接矩陣或二分圖矩陣。
強制_二分圖 – 如果為 True，則強制輸入矩陣被視為二分圖矩陣，即使為正方形。

傳回:

self

傳回類型:

魯汶

訓練_預測(*args, **kwargs) → ndarray

將演算法擬合到資料並傳回標籤。與 fit 方法相同的參數。

傳回:: 標籤 – 標籤。
傳回類型:: np.ndarray

模型預測機率分佈(*指標, **關鍵字) → 陣列

將演算法模型套用至資料，並傳回標籤機率分佈。(模型方法有相同的參數。

傳回:: 機率 – 每一標籤的機率。
傳回類型:: np.ndarray

模型轉換(*指標, **關鍵字) → 陣列

將演算法模型套用至資料，並傳回所屬群組矩陣。(模型方法有相同的參數。

傳回:: 所屬群組 – 所屬群組矩陣（群集分佈）。
傳回類型:: np.ndarray

取得參數()

取得參數作為字典。

傳回:: 參數 – 演算法參數。
傳回類型:: 字典

預測(欄=假) → 陣列

傳回演算法預測的標籤。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 標籤 – 標籤。
傳回類型:: np.ndarray

預測機率分佈(欄=假) → 陣列

傳回演算法預測的標籤機率分佈。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 機率 – 標籤機率分佈。
傳回類型:: np.ndarray

列印日誌(*指標): 以文字填滿日誌。

set_params(params: dict) → Algorithm

設定演算法參數。

參數:: params (dict) – 演算法參數。
傳回:: self
傳回類型:: 演算法

transform(columns=False) → csr_matrix

以稀疏格式傳回標籤的機率分佈。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 機率 – 標籤機率分佈。
傳回類型:: sparse.csr_matrix

Leiden

class sknetwork.clustering.Leiden(resolution: float = 1, modularity: str = 'dugue', tol_optimization: float = 0.001, tol_aggregation: float = 0.001, n_aggregations: int = -1, shuffle_nodes: bool = False, sort_clusters: bool = True, return_probs: bool = True, return_aggregate: bool = True, random_state: RandomState | int | None = None, verbose: bool = False)[source]

Leiden 演算法，用來透過模組化的最大化對圖形進行分類。與 Louvain 演算法相比，此演算法會在每一個彙總前細化分割。

對於二分圖，演算法預設最大化 Barber 的模組化。

參數:

解析度 – 解析度參數。
模組化 (字串) – 要最大化的模組化類型。可以是 'Dugue'、'Newman' 或 'Potts'（預設值 = 'dugue'）。
tol_optimization – 在本地搜尋中進入新的最佳化階段所需的模組化最小增幅。
tol_aggregation – 在進入新的聚集階段所需的模組化最小增幅。
n_aggregations – 最大聚集數。負值表示沒有限制。
shuffle_nodes – 在最佳化之前啟用節點改組調整。
sort_clusters – 如果為 True，則依照叢集大小遞減順序來對標籤進行排序。
return_probs – 如果為 True，則傳回叢集的機率分布（軟式叢集）。
return_aggregate – 如果為 True，則傳回叢集間的圖表鄰接矩陣。
random_state – 隨機數字產生器或隨機種子。如果為 None，則使用 numpy.random。
verbose – 詳細模式。

變數:

標籤 (np.ndarray, shape (n_labels,)) – 各個節點的標籤。
機率（稀疏的.csr_matrix，形狀（n_列，n_標籤））– 標籤的機率分佈。
標籤_欄（標籤_行，）– 二分圖的列和行的標籤。
機率_欄（機率_行，）– 二分圖的列和行的標籤機率分佈。
群集（稀疏的.csr_matrix）– 群集之間的總合鄰接矩陣或二分圖矩陣。

範例

>>> from sknetwork.clustering import Leiden
>>> from sknetwork.data import karate_club
>>> leiden = Leiden()
>>> adjacency = karate_club()
>>> labels = leiden.fit_predict(adjacency)
>>> len(set(labels))
4

參考文獻

Traag, V. A., Waltman, L.，和 Van Eck, N. J. (2019)。從 Louvain 到 Leiden：擔保連結良好的社群，科學報告。

fit(input_matrix: csr_matrix | ndarray, force_bipartite: bool = False) → Leiden[來源]

擬合演算法到資料。

參數:

輸入_矩陣 – 圖的鄰接矩陣或二分圖矩陣。
強制_二分圖 – 如果為 True，則強制輸入矩陣被視為二分圖矩陣，即使為正方形。

傳回:

self

傳回類型:

萊頓

fit_predict(*args, **kwargs) → ndarray

將演算法擬合到資料並傳回標籤。與 fit 方法相同的參數。

傳回:: 標籤 – 標籤。
傳回類型:: np.ndarray

fit_predict_proba(*args, **kwargs) → ndarray

將演算法模型套用至資料，並傳回標籤機率分佈。(模型方法有相同的參數。

傳回:: 機率 – 每一標籤的機率。
傳回類型:: np.ndarray

fit_transform(*args, **kwargs) → ndarray

將演算法模型套用至資料，並傳回所屬群組矩陣。(模型方法有相同的參數。

傳回:: 所屬群組 – 所屬群組矩陣（群集分佈）。
傳回類型:: np.ndarray

get_params()

取得參數作為字典。

傳回:: 參數 – 演算法參數。
傳回類型:: 字典

predict(columns=False) → ndarray

傳回演算法預測的標籤。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 標籤 – 標籤。
傳回類型:: np.ndarray

predict_proba(columns=False) → ndarray

傳回演算法預測的標籤機率分佈。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 機率 – 標籤機率分佈。
傳回類型:: np.ndarray

print_log(*args): 以文字填滿日誌。

set_params(params: dict) → Algorithm

設定演算法參數。

參數:: params (dict) – 演算法參數。
傳回:: self
傳回類型:: 演算法

transform(columns=False) → csr_matrix

以稀疏格式傳回標籤的機率分佈。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 機率 – 標籤機率分佈。
傳回類型:: sparse.csr_matrix

k 中心法

級別 sknetwork.clustering.KCenters(群集數目: 整數, 有向: 布林值 = 假, 中心位置: 字串 = 「列」, 初始化次數: 整數 = 5, 最大反覆次數: 整數 = 20)[原始碼]

K 中心群集演算法。每個群集的中心透過 PageRank 演算法取得。

參數:

群集數目 (整數) – 群集數目。
有向 (布林值, 預設假) – 若為 真，圖表被視為有向圖。
中心位置 (字串, 預設「列」) – 強制中心對應於二部鄰接矩陣列或欄的節點。可以是 列、欄 或 兩者。僅考慮二部圖形。
初始化次數 (整數, 預設 5) – 使用不同中心重複執行 K 中心演算法的次數。產生最佳模組性的執行會選為最終結果。
最大反覆次數 (整數, 預設 20) – K 中心演算法在單次執行中的最大反覆次數。

變數:

標籤 (numpy 陣列, 形狀 (節點數,)) – 每個節點的標籤。
標籤_欄（標籤_行，）– 二分圖的列和行的標籤。
中心 (numpy 陣列, 形狀 (節點數,)) – 群集中心。
中心欄 (中心列,) – 二部圖形中列和欄的群集中心。

範例

>>> from sknetwork.clustering import KCenters
>>> from sknetwork.data import karate_club
>>> kcenters = KCenters(n_clusters=2)
>>> adjacency = karate_club()
>>> labels = kcenters.fit_predict(adjacency)
>>> len(set(labels))
2

fit(input_matrix: csr_matrix | ndarray, force_bipartite: bool = False) → KCenters[來源碼]

以 k 中心計算圖形的聚類。

參數:

輸入_矩陣 – 圖的鄰接矩陣或二分圖矩陣。
強制_二分圖 – 如果為 True，則強制輸入矩陣被視為二分圖矩陣，即使為正方形。

傳回:

self

傳回類型:

KCenters

fit_predict(*args, **kwargs) → ndarray

將演算法擬合到資料並傳回標籤。與 fit 方法相同的參數。

傳回:: 標籤 – 標籤。
傳回類型:: np.ndarray

fit_predict_proba(*args, **kwargs) → ndarray

將演算法模型套用至資料，並傳回標籤機率分佈。(模型方法有相同的參數。

傳回:: 機率 – 每一標籤的機率。
傳回類型:: np.ndarray

fit_transform(*args, **kwargs) → ndarray

將演算法模型套用至資料，並傳回所屬群組矩陣。(模型方法有相同的參數。

傳回:: 所屬群組 – 所屬群組矩陣（群集分佈）。
傳回類型:: np.ndarray

get_params()

取得參數作為字典。

傳回:: 參數 – 演算法參數。
傳回類型:: 字典

predict(columns=False) → ndarray

傳回演算法預測的標籤。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 標籤 – 標籤。
傳回類型:: np.ndarray

預測機率(欄位=假) → ndarray

傳回演算法預測的標籤機率分佈。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 機率 – 標籤機率分佈。
傳回類型:: np.ndarray

設定參數(參數: dict) → 演算法

設定演算法參數。

參數:: params (dict) – 演算法參數。
傳回:: self
傳回類型:: 演算法

轉換(欄位=假) → csr_matrix

以稀疏格式傳回標籤的機率分佈。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 機率 – 標籤機率分佈。
傳回類型:: sparse.csr_matrix

傳播

類別 sknetwork.clustering.傳播群集(n_iter: int = 5, 節點順序: str = 'decreasing', 加權: bool = True, 排序群集: bool = True, 傳回機率: bool = True, 傳回總和: bool = True)[source]

透過標籤傳播進行群集。

參數:

n_iter (int) - 迭代次數上限（無窮大設為 -1）。
node_order (str) -
- ‘random’：以隨機順序更新節點標籤。
- ’increasing’：按權重遞增順序更新節點標籤。
- ’decreasing’：按權重遞減順序更新節點標籤。
- 否則，按索引順序更新節點標籤。
weighted (bool) - 如果 True，則每個鄰接點的投票與邊權重成正比。否則，所有投票的權重均為 1。
sort_clusters (bool) - 如果 True，則按群集規模遞減順序排列標籤。
return_probs (bool) - 如果 True，則會傳回群集機率分佈（軟群集）。
return_aggregate (bool) - 如果 True，則會傳回群集之間的匯總鄰接矩陣或雙鄰接矩陣。

變數:

標籤 (np.ndarray, shape (n_labels,)) – 各個節點的標籤。
機率（稀疏的.csr_matrix，形狀（n_列，n_標籤））– 標籤的機率分佈。
標籤_欄（標籤_行，）– 二分圖的列和行的標籤。
機率_欄（機率_行，）– 二分圖的列和行的標籤機率分佈。
群集（稀疏的.csr_matrix）– 群集之間的總合鄰接矩陣或二分圖矩陣。

範例

>>> from sknetwork.clustering import PropagationClustering
>>> from sknetwork.data import karate_club
>>> propagation = PropagationClustering()
>>> graph = karate_club(metadata=True)
>>> adjacency = graph.adjacency
>>> labels = propagation.fit_predict(adjacency)
>>> len(set(labels))
2

參考文獻

Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3), 036106.

fit(input_matrix: csr_matrix | ndarray) → PropagationClustering[source]

透過標籤傳播進行群集。

參數:: input_matrix (sparse.csr_matrix, np.ndarray) - 圖形的鄰接矩陣或雙鄰接矩陣。
傳回:: self
傳回類型:: PropagationClustering

fit_predict(*args, **kwargs) → ndarray

將演算法擬合到資料並傳回標籤。與 fit 方法相同的參數。

傳回:: 標籤 – 標籤。
傳回類型:: np.ndarray

fit_predict_proba(*args, **kwargs) → ndarray

將演算法模型套用至資料，並傳回標籤機率分佈。(模型方法有相同的參數。

傳回:: 機率 – 每一標籤的機率。
傳回類型:: np.ndarray

fit_transform(*args, **kwargs) → ndarray

將演算法模型套用至資料，並傳回所屬群組矩陣。(模型方法有相同的參數。

傳回:: 所屬群組 – 所屬群組矩陣（群集分佈）。
傳回類型:: np.ndarray

get_params()

取得參數作為字典。

傳回:: 參數 – 演算法參數。
傳回類型:: 字典

predict(columns=False) → ndarray

傳回演算法預測的標籤。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 標籤 – 標籤。
傳回類型:: np.ndarray

predict_proba(columns=False) → ndarray

傳回演算法預測的標籤機率分佈。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 機率 – 標籤機率分佈。
傳回類型:: np.ndarray

set_params(params: dict) → Algorithm

設定演算法參數。

參數:: params (dict) – 演算法參數。
傳回:: self
傳回類型:: 演算法

transform(columns=False) → csr_matrix

以稀疏格式傳回標籤的機率分佈。

參數:: 欄 (布林值) – 若為真，傳回欄的預測。
傳回:: 機率 – 標籤機率分佈。
傳回類型:: sparse.csr_matrix

後處理

sknetwork.clustering.reindex_labels(labels: ndarray) → ndarray[來源]

依據大小遞減順序重新編排叢集。

參數:: 標籤 – 每個節點的標籤。
傳回:: new_labels – 每個節點的新標籤。
傳回類型:: np.ndarray

範例

>>> from sknetwork.clustering import reindex_labels
>>> labels = np.array([0, 1, 1])
>>> reindex_labels(labels)
array([1, 0, 0])

sknetwork.clustering.aggregate_graph(input_matrix: csr_matrix, labels: ndarray | None = None, labels_row: ndarray | None = None, labels_col: ndarray | None = None) → csr_matrix[原始碼]

根據標籤彙整圖。帶有相同標籤的所有節點變成一個單一節點。負標籤會被忽略 (對應節點會被捨棄)。

參數:

input_matrix (稀疏矩陣) – 圖的鄰接矩陣或二鄰接矩陣。
labels (np.ndarray) – 節點的標籤。
labels_row (np.ndarray) – 列的標籤 (用於二部圖)。等同於標籤。
labels_col (np.ndarray) – 行的標籤 (用於二部圖)。

度量

sknetwork.clustering.get_modularity(input_matrix: csr_matrix | ndarray, labels: ndarray, labels_col: ndarray | None = None, weights: str = 'degree', resolution: float = 1, return_all: bool = False) → float | Tuple[float, float, float][source]

分群的模組性。

分群的模組性為

\(Q = \dfrac{1}{w} \sum_{i,j}\left(A_{ij} - \gamma \dfrac{w_iw_j}{w}\right)\delta_{c_i,c_j}\)，代表圖形，

\(Q = \dfrac{1}{w} \sum_{i,j}\left(A_{ij} - \gamma \dfrac{d^+_id^-_j}{w}\right)\delta_{c_i,c_j}\)，代表有向圖形，

其中

\(c_i\) 是節點 \(i\) 的叢集。
\(w_i\)為節點 \(i\) 的權重，
\(w^+_i, w^-_i\) 為節點 \(i\) 的出節權重、入節權重（針對有向圖形），
\(w = 1^TA1\) 為總權重，
\(\delta\) 是克羅內克符號。
\(\gamma \ge 0\) 是解析度參數。

參數:

輸入_矩陣 – 圖的鄰接矩陣或二分圖矩陣。
labels – 節點標籤。
labels_col – 欄位節點標籤（針對二分圖形）。
weights – 節點的加權（'degree'（預設）或 'uniform'）。
解析度 – 解析度參數（預設值 = 1）。
傳回所有 – 如果 True，傳回模塊性、擬合、多樣性。

傳回:

模塊性（浮點數）
擬合（浮點數，可選）
多樣性（浮點數，可選）

範例

>>> from sknetwork.clustering import get_modularity
>>> from sknetwork.data import house
>>> adjacency = house()
>>> labels = np.array([0, 0, 1, 1, 0])
>>> np.round(get_modularity(adjacency, labels), 2)
0.11