聚类

聚类算法。

属性 labels_ 为图的每个节点分配一个标签（簇索引）。

Louvain

Louvain 算法旨在最大化模块度。模块度有几种变体可用

模块度

公式

Newman ('newman')

\(Q = \frac{1}{w} \sum_{i,j}\left(A_{ij} - \gamma \frac{d_id_j}{w}\right)\delta_{c_i,c_j}\)

Dugué ('dugue')

\(Q = \frac{1}{w} \sum_{i,j}\left(A_{ij} - \gamma \frac{d^+_id^-_j}{w}\right)\delta_{c_i,c_j}\)

Potts ('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 的模块度。

参数：

  • resolution – 分辨率参数。

  • modularity (str) – 要最大化的模块度类型。可以是 '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 – 详细模式。

变量：

  • labels (np.ndarray, shape (n_labels,)) – 每个节点的标签。

  • probs (sparse.csr_matrix, shape (n_row, n_labels)) – 标签上的概率分布。

  • labels_col (labels_row,) – 行和列的标签，用于二部图。

  • probs_col (probs_row,) – 行和列的标签上的概率分布（对于二部图）。

  • aggregate (sparse.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

参考

fit(input_matrix: csr_matrix | ndarray, force_bipartite: bool = False) → Louvain[source]

将算法拟合到数据。

参数：

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

  • force_bipartite – 如果为 True，即使输入矩阵为方阵，也强制将其视为二部邻接矩阵。

返回值：

self

返回类型：

Louvain

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回标签。与 fit 方法相同的参数。

返回值：

标签 – 标签。

返回类型：

np.ndarray

fit_predict_proba(*args, **kwargs) → ndarray

将算法拟合到数据并返回标签上的概率分布。与 fit 方法相同的参数。

返回值：

概率 – 每个标签的概率。

返回类型：

np.ndarray

fit_transform(*args, **kwargs) → ndarray

将算法拟合到数据并返回成员矩阵。与 fit 方法相同的参数。

返回值：

成员资格 – 成员矩阵（对集群的分布）。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

参数 – 算法的参数。

返回类型：

dict

predict(columns=False) → ndarray

返回算法预测的标签。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

标签 – 标签。

返回类型：

np.ndarray

predict_proba(columns=False) → ndarray

返回算法预测的标签上的概率分布。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

概率 – 标签上的概率分布。

返回类型：

np.ndarray

print_log(*args)

用文本填充日志。

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

参数 (字典) – 算法的参数。

返回值：

self

返回类型：

算法

transform(columns=False) → csr_matrix

以稀疏格式返回标签上的概率分布。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

概率 – 标签上的概率分布。

返回类型：

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 的模块度。

参数：

  • resolution – 分辨率参数。

  • modularity (str) – 要最大化的模块度类型。可以是 '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 – 详细模式。

变量：

  • labels (np.ndarray, shape (n_labels,)) – 每个节点的标签。

  • probs (sparse.csr_matrix, shape (n_row, n_labels)) – 标签上的概率分布。

  • labels_col (labels_row,) – 行和列的标签，用于二部图。

  • probs_col (probs_row,) – 行和列的标签上的概率分布（对于二部图）。

  • aggregate (sparse.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[source]

将算法拟合到数据。

参数：

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

  • force_bipartite – 如果为 True，即使输入矩阵为方阵，也强制将其视为二部邻接矩阵。

返回值：

self

返回类型：

Leiden

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回标签。与 fit 方法相同的参数。

返回值：

标签 – 标签。

返回类型：

np.ndarray

fit_predict_proba(*args, **kwargs) → ndarray

将算法拟合到数据并返回标签上的概率分布。与 fit 方法相同的参数。

返回值：

概率 – 每个标签的概率。

返回类型：

np.ndarray

fit_transform(*args, **kwargs) → ndarray

将算法拟合到数据并返回成员矩阵。与 fit 方法相同的参数。

返回值：

成员资格 – 成员矩阵（对集群的分布）。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

参数 – 算法的参数。

返回类型：

dict

predict(columns=False) → ndarray

返回算法预测的标签。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

标签 – 标签。

返回类型：

np.ndarray

predict_proba(columns=False) → ndarray

返回算法预测的标签上的概率分布。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

概率 – 标签上的概率分布。

返回类型：

np.ndarray

print_log(*args)

用文本填充日志。

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

参数 (字典) – 算法的参数。

返回值：

self

返回类型：

算法

transform(columns=False) → csr_matrix

以稀疏格式返回标签上的概率分布。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

概率 – 标签上的概率分布。

返回类型：

sparse.csr_matrix

K-中心

class sknetwork.clustering.KCenters(n_clusters: int, directed: bool = False, center_position: str = 'row', n_init: int = 5, max_iter: int = 20)[source]

K-中心聚类算法。每个聚类的中心通过 PageRank 算法获得。

参数：

  • n_clusters (int) – 聚类数量。

  • directed (bool, default False) – 如果为 True，则认为图是有向的。

  • center_position (str, default "row") – 强制中心对应于二部图的矩阵行或列上的节点。可以是 row、col 或 both。仅针对二部图考虑。

  • n_init (int, default 5) – 使用不同中心重新运行 k-中心算法的次数。产生最佳模块化的运行将被选为最终结果。

  • max_iter (int, default 20) – 单次运行 k-中心算法的最大迭代次数。

变量：

  • labels (np.ndarray, shape (n_nodes,)) – 每个节点的标签。

  • labels_col (labels_row,) – 行和列的标签，用于二部图。

  • centers (np.ndarray, shape (n_nodes,)) – 聚类中心。

  • centers_col (centers_row,) – 二部图的行和列的聚类中心。

示例

>>> 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[source]

通过 k-中心计算图的聚类。

参数：

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

  • force_bipartite – 如果为 True，即使输入矩阵为方阵，也强制将其视为二部邻接矩阵。

返回值：

self

返回类型：

KCenters

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回标签。与 fit 方法相同的参数。

返回值：

标签 – 标签。

返回类型：

np.ndarray

fit_predict_proba(*args, **kwargs) → ndarray

将算法拟合到数据并返回标签上的概率分布。与 fit 方法相同的参数。

返回值：

概率 – 每个标签的概率。

返回类型：

np.ndarray

fit_transform(*args, **kwargs) → ndarray

将算法拟合到数据并返回成员矩阵。与 fit 方法相同的参数。

返回值：

成员资格 – 成员矩阵（对集群的分布）。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

参数 – 算法的参数。

返回类型：

dict

predict(columns=False) → ndarray

返回算法预测的标签。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

标签 – 标签。

返回类型：

np.ndarray

predict_proba(columns=False) → ndarray

返回算法预测的标签上的概率分布。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

概率 – 标签上的概率分布。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

参数 (字典) – 算法的参数。

返回值：

self

返回类型：

算法

transform(columns=False) → csr_matrix

以稀疏格式返回标签上的概率分布。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

概率 – 标签上的概率分布。

返回类型：

sparse.csr_matrix

传播

class sknetwork.clustering.PropagationClustering(n_iter: int = 5, node_order: str = 'decreasing', weighted: bool = True, sort_clusters: bool = True, return_probs: bool = True, return_aggregate: 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，则返回聚类之间的聚合邻接矩阵或二部图矩阵。

变量：

  • labels (np.ndarray, shape (n_labels,)) – 每个节点的标签。

  • probs (sparse.csr_matrix, shape (n_row, n_labels)) – 标签上的概率分布。

  • labels_col (labels_row,) – 行和列的标签，用于二部图。

  • probs_col (probs_row,) – 行和列的标签上的概率分布（对于二部图）。

  • aggregate (sparse.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

将算法拟合到数据并返回标签上的概率分布。与 fit 方法相同的参数。

返回值：

概率 – 每个标签的概率。

返回类型：

np.ndarray

fit_transform(*args, **kwargs) → ndarray

将算法拟合到数据并返回成员矩阵。与 fit 方法相同的参数。

返回值：

成员资格 – 成员矩阵（对集群的分布）。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

参数 – 算法的参数。

返回类型：

dict

predict(columns=False) → ndarray

返回算法预测的标签。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

标签 – 标签。

返回类型：

np.ndarray

predict_proba(columns=False) → ndarray

返回算法预测的标签上的概率分布。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

概率 – 标签上的概率分布。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

参数 (字典) – 算法的参数。

返回值：

self

返回类型：

算法

transform(columns=False) → csr_matrix

以稀疏格式返回标签上的概率分布。

参数：

列 (布尔值) – 如果 True，则返回对列的预测。

返回值：

概率 – 标签上的概率分布。

返回类型：

sparse.csr_matrix

后处理

sknetwork.clustering.reindex_labels(labels: ndarray) → ndarray[source]

按大小降序重新索引聚类。

参数：

labels – 每个节点的标签。

返回值：

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[source]

按标签聚合图。具有相同标签的所有节点成为单个节点。忽略负标签（丢弃相应的节点）。

参数：

  • 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\) 是分辨率参数。

参数：

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

  • labels – 节点的标签。

  • labels_col – 列节点的标签（对于二部图）。

  • weights – 节点的加权 ('degree' (默认) 或 'uniform')。

  • resolution – 分辨率参数（默认 = 1）。

  • return_all – 如果 True，则返回模块化、拟合、多样性。

返回值：

  • modularity (float)

  • fit (float, 可选)

  • diversity (float, 可选)

示例

>>> 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