嵌入

图嵌入算法。

属性 embedding_ 为图的每个节点分配一个向量。

class sknetwork.embedding.Spectral(n_components: int = 2, decomposition: str = 'rw', regularization: float = -1, normalized: bool = True)[source]

基于拉普拉斯矩阵 \(L = D - A\) 或随机游走转移矩阵 \(P = D^{-1}A\)(默认)的谱分解的图谱嵌入,其中 \(D\) 是度数的对角矩阵。

特征向量按特征值的递增顺序(对于拉普拉斯矩阵 \(L\))或递减顺序(对于随机游走转移矩阵 \(P\))考虑,跳过第一个。

参数:
  • n_components (int (default = 2)) – 嵌入空间的维数。

  • decomposition (str (laplacian or rw, default = rw)) – 用于谱分解的矩阵。

  • regularization (float (default = -1)) – 正则化因子 \(\alpha\),使得邻接矩阵为 \(A + \alpha \frac{11^T}{n}\)。如果为负,则仅当图断开连接时才应用正则化;正则化因子 \(\alpha\) 然后设置为参数的绝对值。

  • normalized (bool (default = True)) – 如果为 True,则对嵌入进行归一化,以便每个向量在嵌入空间中的范数为 1,即每个向量都位于单位球面上。

变量:
  • embedding (array, shape = (n, n_components)) – 节点的嵌入。

  • embedding_row (array, shape = (n_row, n_components)) – 行的嵌入,用于二部图。

  • embedding_col (array, shape = (n_col, n_components)) – 列的嵌入,用于二部图。

  • eigenvalues (array, shape = (n_components)) – 特征值。

  • eigenvectors (array, shape = (n, n_components)) – 特征向量。

示例

>>> from sknetwork.embedding import Spectral
>>> from sknetwork.data import karate_club
>>> spectral = Spectral(n_components=3)
>>> adjacency = karate_club()
>>> embedding = spectral.fit_transform(adjacency)
>>> embedding.shape
(34, 3)

参考文献

Belkin, M. & Niyogi, P. (2003). Laplacian Eigenmaps for Dimensionality Reduction and Data Representation, Neural computation.

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

计算图嵌入。

如果输入矩阵 \(B\) 不是方阵(例如,二部图的二部邻接矩阵)或不是对称的(例如,有向图的邻接矩阵),则使用邻接矩阵

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

并返回输入矩阵 \(B\) 的行和列的嵌入。

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

  • force_bipartite (bool (default = False)) – 如果为 True,则强制将输入矩阵视为二部邻接矩阵。

返回值:

self

返回类型:

fit_transform(*args, **kwargs) ndarray

拟合数据并返回嵌入。与 fit 方法相同的参数。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

get_params()

获取参数作为字典。

返回值:

params – 算法的参数。

返回类型:

dict

predict(columns: bool = False) ndarray

返回节点的嵌入。

参数:

columns (bool) – 如果为 True,则返回对列的预测。

返回值:

embedding_ – 节点的嵌入。

返回类型:

np.ndarray

set_params(params: dict) Algorithm

设置算法的参数。

参数:

params (dict) – 算法的参数。

返回值:

self

返回类型:

算法

transform() ndarray

返回嵌入。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

SVD

class sknetwork.embedding.SVD(n_components=2, regularization: None | float = None, factor_singular: float = 0.0, normalized: bool = False, solver: str | SVDSolver = 'lanczos')[source]

通过图的邻接矩阵或双邻接矩阵的奇异值分解来进行图嵌入。

参数:
  • n_components (int) – 嵌入的维度。

  • regularization (None or float (default = None)) – 正则化因子 \(\alpha\),使得矩阵为 \(A + \alpha \frac{11^T}{n}\)

  • factor_singular (float (default = 0.)) –

    对右奇异向量上的奇异值应用的幂因子 \(\alpha\)。行和列的嵌入分别是 \(U \Sigma^{1-\alpha}\)\(V \Sigma^\alpha\),其中

    • \(U\) 是左奇异向量矩阵,形状为 (n_row, n_components)

    • \(V\) 是右奇异向量矩阵,形状为 (n_col, n_components)

    • \(\Sigma\) 是奇异值的对角矩阵,形状为 (n_components, n_components)

  • normalized (bool (default = False)) – 如果为 True,则将嵌入归一化,使得每个向量在嵌入空间中的范数为 1,即每个向量位于单位球面上。

  • solver ('lanczos' (Lanczos 算法,默认) 或 SVDSolver (自定义求解器)) – 要使用的求解器。

变量:
  • embedding (array, shape = (n, n_components)) – 节点的嵌入。

  • embedding_row (array, shape = (n_row, n_components)) – 行的嵌入,用于二部图。

  • embedding_col (array, shape = (n_col, n_components)) – 列的嵌入,用于二部图。

  • singular_values (np.ndarray, shape = (n_components)) – 奇异值。

  • singular_vectors_left (np.ndarray, shape = (n_row, n_components)) – 左奇异向量。

  • singular_vectors_right (np.ndarray, shape = (n_col, n_components)) – 右奇异向量。

示例

>>> from sknetwork.embedding import SVD
>>> from sknetwork.data import karate_club
>>> svd = SVD()
>>> adjacency = karate_club()
>>> embedding = svd.fit_transform(adjacency)
>>> embedding.shape
(34, 2)

参考文献

Abdi, H. (2007). 奇异值分解 (SVD) 和广义奇异值分解。 测量和统计百科全书。

fit(input_matrix: csr_matrix | ndarray) GSVD

计算图的嵌入。

参数:

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

返回值:

self

返回类型:

GSVD

fit_transform(*args, **kwargs) ndarray

拟合数据并返回嵌入。与 fit 方法相同的参数。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

get_params()

获取参数作为字典。

返回值:

params – 算法的参数。

返回类型:

dict

predict(adjacency_vectors: csr_matrix | ndarray) ndarray

预测由其邻接向量定义的新行的嵌入。

参数:

adjacency_vectors – 节点的邻接向量。形状为 (n_col,) (单个向量) 或 (n_vectors, n_col) 的数组

返回值:

embedding_vectors – 节点的嵌入。

返回类型:

np.ndarray

set_params(params: dict) Algorithm

设置算法的参数。

参数:

params (dict) – 算法的参数。

返回值:

self

返回类型:

算法

transform() ndarray

返回嵌入。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

GSVD

class sknetwork.embedding.GSVD(n_components=2, regularization: None | float = None, factor_row: float = 0.5, factor_col: float = 0.5, factor_singular: float = 0.0, normalized: bool = True, solver: str | SVDSolver = 'lanczos')[source]

通过邻接矩阵或双邻接矩阵 \(A\) 的广义奇异值分解来进行图嵌入。这等效于矩阵 \(D_1^{- \alpha_1}AD_2^{- \alpha_2}\) 的奇异值分解,其中 \(D_1, D_2\) 是行权重和列权重的对角矩阵,分别,并且 \(\alpha_1, \alpha_2\) 是参数。

参数:
  • n_components (int) – 嵌入的维度。

  • regularization (None or float (default = None)) – 正则化因子 \(\alpha\),使得矩阵为 \(A + \alpha \frac{11^T}{n}\)

  • factor_row (float (default = 0.5)) – 对行权重的对角矩阵应用的幂因子 \(\alpha_1\)

  • factor_col (float (default = 0.5)) – 对列权重的对角矩阵应用的幂因子 \(\alpha_2\)

  • factor_singular (float (default = 0.)) –

    对右奇异向量上的奇异值应用的参数 \(\alpha\)。行和列的嵌入分别是 \(D_1^{- \alpha_1}U \Sigma^{1-\alpha}\)\(D_2^{- \alpha_2}V \Sigma^\alpha\),其中

    • \(U\) 是左奇异向量矩阵,形状为 (n_row, n_components)

    • \(V\) 是右奇异向量矩阵,形状为 (n_col, n_components)

    • \(\Sigma\) 是奇异值的对角矩阵,形状为 (n_components, n_components)

  • normalized (bool (default = True)) – 如果为 True,则对嵌入进行归一化,以便每个向量在嵌入空间中的范数为 1,即每个向量都位于单位球面上。

  • solver ('lanczos' (Lanczos 算法,默认) 或 SVDSolver (自定义求解器)) – 要使用的求解器。

变量:
  • embedding (array, shape = (n, n_components)) – 节点的嵌入。

  • embedding_row (array, shape = (n_row, n_components)) – 行的嵌入,用于二部图。

  • embedding_col (array, shape = (n_col, n_components)) – 列的嵌入,用于二部图。

  • singular_values (np.ndarray, shape = (n_components)) – 奇异值。

  • singular_vectors_left (np.ndarray, shape = (n_row, n_components)) – 左奇异向量。

  • singular_vectors_right (np.ndarray, shape = (n_col, n_components)) – 右奇异向量。

  • weights_col (np.ndarray, shape = (n2)) – 应用于列的权重。

示例

>>> from sknetwork.embedding import GSVD
>>> from sknetwork.data import karate_club
>>> gsvd = GSVD()
>>> adjacency = karate_club()
>>> embedding = gsvd.fit_transform(adjacency)
>>> embedding.shape
(34, 2)

参考文献

Abdi, H. (2007). 奇异值分解 (SVD) 和广义奇异值分解。 测量和统计百科全书,907-912。

fit(input_matrix: csr_matrix | ndarray) GSVD[source]

计算图的嵌入。

参数:

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

返回值:

self

返回类型:

GSVD

fit_transform(*args, **kwargs) ndarray

拟合数据并返回嵌入。与 fit 方法相同的参数。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

get_params()

获取参数作为字典。

返回值:

params – 算法的参数。

返回类型:

dict

predict(adjacency_vectors: csr_matrix | ndarray) ndarray[source]

预测由其邻接向量定义的新行的嵌入。

参数:

adjacency_vectors – 节点的邻接向量。形状为 (n_col,) (单个向量) 或 (n_vectors, n_col) 的数组

返回值:

embedding_vectors – 节点的嵌入。

返回类型:

np.ndarray

set_params(params: dict) Algorithm

设置算法的参数。

参数:

params (dict) – 算法的参数。

返回值:

self

返回类型:

算法

transform() ndarray

返回嵌入。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

PCA

class sknetwork.embedding.PCA(n_components=2, normalized: bool = False, solver: str | SVDSolver = 'lanczos')[source]

通过对邻接矩阵或双邻接矩阵进行主成分分析来进行图嵌入。

参数:
  • n_components (int) – 嵌入的维度。

  • normalized (bool (default = False)) – 如果为 True,则将嵌入归一化,使得每个向量在嵌入空间中的范数为 1,即每个向量位于单位球面上。

  • solver ('lanczos' (Lanczos 算法,默认) 或 SVDSolver (自定义求解器)) – 要使用的求解器。

变量:
  • embedding (array, shape = (n, n_components)) – 节点的嵌入。

  • embedding_row (array, shape = (n_row, n_components)) – 行的嵌入,用于二部图。

  • embedding_col (array, shape = (n_col, n_components)) – 列的嵌入,用于二部图。

  • singular_values (np.ndarray, shape = (n_components)) – 奇异值。

  • singular_vectors_left (np.ndarray, shape = (n_row, n_components)) – 左奇异向量。

  • singular_vectors_right (np.ndarray, shape = (n_col, n_components)) – 右奇异向量。

示例

>>> from sknetwork.embedding import PCA
>>> from sknetwork.data import karate_club
>>> pca = PCA()
>>> adjacency = karate_club()
>>> embedding = pca.fit_transform(adjacency)
>>> embedding.shape
(34, 2)

参考文献

Jolliffe, I.T. (2002). Principal Component Analysis Series: Springer Series in Statistics.

fit(adjacency: csr_matrix | ndarray) PCA[source]

计算图的嵌入。

参数:

adjacency – 图的邻接矩阵或双邻接矩阵。

返回值:

self

返回类型:

PCA

fit_transform(*args, **kwargs) ndarray

拟合数据并返回嵌入。与 fit 方法相同的参数。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

get_params()

获取参数作为字典。

返回值:

params – 算法的参数。

返回类型:

dict

predict(adjacency_vectors: csr_matrix | ndarray) ndarray

预测由其邻接向量定义的新行的嵌入。

参数:

adjacency_vectors – 节点的邻接向量。形状为 (n_col,) (单个向量) 或 (n_vectors, n_col) 的数组

返回值:

embedding_vectors – 节点的嵌入。

返回类型:

np.ndarray

set_params(params: dict) Algorithm

设置算法的参数。

参数:

params (dict) – 算法的参数。

返回值:

self

返回类型:

算法

transform() ndarray

返回嵌入。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

随机投影

class sknetwork.embedding.RandomProjection(n_components: int = 2, alpha: float = 0.5, n_iter: int = 3, random_walk: bool = False, regularization: float = -1, normalized: bool = True, random_state: int | None = None)[source]

基于邻接矩阵的随机投影的图嵌入

\((I + \alpha A +... + (\alpha A)^K)G\)

其中 \(A\) 是邻接矩阵,\(G\) 是一个随机高斯矩阵,\(\alpha\) 是一个平滑因子,\(K\) 是一个非负整数。

参数:
  • n_components (int (default = 2)) – 嵌入空间的维度。

  • alpha (float (default = 0.5)) – 平滑参数。

  • n_iter (int (default = 3)) – 邻接矩阵的幂迭代次数。

  • random_walk (bool (default = False)) – 如果为 True,使用随机游走的转移矩阵 \(P = D^{-1}A\),而不是邻接矩阵。

  • regularization (float (default = -1)) – 正则化因子 \(\alpha\),使得矩阵为 \(A + \alpha \frac{11^T}{n}\)。如果为负数,则只有在图断开连接时才应用正则化(然后等于参数的绝对值)。

  • normalized (bool (default = True)) – 如果为 True,则对嵌入进行归一化,以便每个向量在嵌入空间中具有范数 1,即每个向量都位于单位球面上。

  • random_state (int, optional) – 随机数生成器使用的种子。

变量:
  • embedding (array, shape = (n, n_components)) – 节点的嵌入。

  • embedding_row (array, shape = (n_row, n_components)) – 行的嵌入,用于二部图。

  • embedding_col (array, shape = (n_col, n_components)) – 列的嵌入,用于二部图。

示例

>>> from sknetwork.embedding import RandomProjection
>>> from sknetwork.data import karate_club
>>> projection = RandomProjection()
>>> adjacency = karate_club()
>>> embedding = projection.fit_transform(adjacency)
>>> embedding.shape
(34, 2)

参考文献

Zhang, Z., Cui, P., Li, H., Wang, X., & Zhu, W. (2018). Billion-scale network embedding with iterative random projection, ICDM.

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

计算图嵌入。

参数:
  • input_matrix (sparse.csr_matrix, np.ndarray) – 图的邻接矩阵或双邻接矩阵。

  • force_bipartite (bool (default = False)) – 如果为 True,则强制将输入矩阵视为二部邻接矩阵。

返回值:

self

返回类型:

RandomProjection

fit_transform(*args, **kwargs) ndarray

拟合数据并返回嵌入。与 fit 方法相同的参数。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

get_params()

获取参数作为字典。

返回值:

params – 算法的参数。

返回类型:

dict

predict(columns: bool = False) ndarray

返回节点的嵌入。

参数:

columns (bool) – 如果为 True,则返回对列的预测。

返回值:

embedding_ – 节点的嵌入。

返回类型:

np.ndarray

set_params(params: dict) Algorithm

设置算法的参数。

参数:

params (dict) – 算法的参数。

返回值:

self

返回类型:

算法

transform() ndarray

返回嵌入。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

Louvain

class sknetwork.embedding.LouvainEmbedding(resolution: float = 1, modularity: str = 'Dugue', tol_optimization: float = 0.001, tol_aggregation: float = 0.001, n_aggregations: int = -1, shuffle_nodes: bool = False, random_state: RandomState | int | None = None, isolated_nodes: str = 'remove')[source]

通过 Louvain 聚类诱导的图嵌入。嵌入的每个分量对应于 Louvain 获得的集群。

参数:
  • resolution (float) – 分辨率参数。

  • modularity (str) – 要最大化的目标函数。可以是 'Dugue''Newman''Potts'

  • tol_optimization – 进入新的优化阶段的最小目标函数增量。

  • tol_aggregation – 进入新的聚合阶段的最小目标函数增量。

  • n_aggregations – 最大聚合次数。负值表示无限制。

  • shuffle_nodes – 在优化之前启用节点洗牌。

  • random_state – 随机数生成器或随机种子。如果为 None,则使用 numpy.random。

  • isolated_nodes (str) – 如何处理孤立的列节点。可以是 'remove'(默认)、'merge''keep'

变量:
  • embedding (array, shape = (n, n_components)) – 节点的嵌入。

  • embedding_row (array, shape = (n_row, n_components)) – 行的嵌入,用于二部图。

  • embedding_col (array, shape = (n_col, n_components)) – 列的嵌入,用于二部图。

  • labels_row (np.ndarray) – 行标签(用于构建列的嵌入)。

  • labels_col (np.ndarray) – 列标签(用于构建行的嵌入)。

示例

>>> from sknetwork.embedding import LouvainEmbedding
>>> from sknetwork.data import house
>>> louvain = LouvainEmbedding()
>>> adjacency = house()
>>> embedding = louvain.fit_transform(adjacency)
>>> embedding.shape
(5, 2)
fit(input_matrix: csr_matrix, force_bipartite: bool = False)[source]

从 Louvain 获得的聚类中嵌入图。

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

  • force_bipartite (bool (default = False)) – 如果为 True,则强制将输入矩阵视为二部邻接矩阵。

返回值:

self

返回类型:

BiLouvainEmbedding

fit_transform(*args, **kwargs) ndarray

拟合数据并返回嵌入。与 fit 方法相同的参数。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

get_params()

获取参数作为字典。

返回值:

params – 算法的参数。

返回类型:

dict

predict(columns: bool = False) ndarray

返回节点的嵌入。

参数:

columns (bool) – 如果为 True,则返回对列的预测。

返回值:

embedding_ – 节点的嵌入。

返回类型:

np.ndarray

set_params(params: dict) Algorithm

设置算法的参数。

参数:

params (dict) – 算法的参数。

返回值:

self

返回类型:

算法

transform() ndarray

返回嵌入。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

Force Atlas

class sknetwork.embedding.ForceAtlas(n_components: int = 2, n_iter: int = 50, approx_radius: float = -1, lin_log: bool = False, gravity_factor: float = 0.01, repulsive_factor: float = 0.1, tolerance: float = 0.1, speed: float = 0.1, speed_max: float = 10)[source]

用于显示图的 Force Atlas 布局。

参数:
  • n_components (int) – 图布局的维度。

  • n_iter (int) – 更新位置的迭代次数。如果为 None,则使用 self.n_iter 的值。

  • approx_radius (float) – 如果提供正值,则仅使用给定节点此距离内的节点来计算斥力。

  • lin_log (bool) – 如果为 True,则使用 lin-log 模式。

  • gravity_factor (float) – 重力缩放常数。

  • repulsive_factor (float) – 斥力缩放常数。

  • tolerance (float) – 在摆动常数中定义的容差。

  • speed (float) – 速度常数。

  • speed_max (float) – 用于对速度施加约束的常数。

变量:

embedding (np.ndarray) – 给定维度的布局。

示例

>>> from sknetwork.embedding.force_atlas import ForceAtlas
>>> from sknetwork.data import karate_club
>>> force_atlas = ForceAtlas()
>>> adjacency = karate_club()
>>> embedding = force_atlas.fit_transform(adjacency)
>>> embedding.shape
(34, 2)

参考文献

Jacomy M., Venturini T., Heymann S., Bastian M. (2014). ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software. Plos One.

fit(adjacency: csr_matrix | ndarray, pos_init: ndarray | None = None, n_iter: int | None = None) ForceAtlas[source]

计算布局。

参数:
  • adjacency – 图的邻接矩阵,被视为无向图。

  • pos_init – 要开始的位置。如果未提供,则为随机。

  • n_iter (int) – 更新位置的迭代次数。如果为 None,则使用 self.n_iter 的值。

返回值:

self

返回类型:

ForceAtlas

fit_transform(*args, **kwargs) ndarray

拟合数据并返回嵌入。与 fit 方法相同的参数。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

get_params()

获取参数作为字典。

返回值:

params – 算法的参数。

返回类型:

dict

predict(columns: bool = False) ndarray

返回节点的嵌入。

参数:

columns (bool) – 如果为 True,则返回对列的预测。

返回值:

embedding_ – 节点的嵌入。

返回类型:

np.ndarray

set_params(params: dict) Algorithm

设置算法的参数。

参数:

params (dict) – 算法的参数。

返回值:

self

返回类型:

算法

transform() ndarray

返回嵌入。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

Spring

class sknetwork.embedding.Spring(n_components: int = 2, strength: float | None = None, n_iter: int = 50, tol: float = 0.0001, approx_radius: float = -1, position_init: str = 'random')[source]

用于显示小图的弹簧布局。

参数:
  • n_components (int) – 图布局的维度。

  • strength (float) – 移动节点的力的强度。

  • n_iter (int) – 更新位置的迭代次数。

  • tol (float) – 继续更新位置的最小相对变化。

  • approx_radius (float) – 如果提供正值,则仅使用给定节点此距离内的节点来计算斥力。

  • position_init (str) – 如何初始化布局。如果为 'spectral',则使用 2 维的谱嵌入,否则使用随机初始化。

变量:

embedding (np.ndarray) – 布局。

示例

>>> from sknetwork.embedding import Spring
>>> from sknetwork.data import karate_club
>>> spring = Spring()
>>> adjacency = karate_club()
>>> embedding = spring.fit_transform(adjacency)
>>> embedding.shape
(34, 2)

注释

简单实现,旨在显示小图。

参考文献

Fruchterman, T. M. J., Reingold, E. M. (1991). Graph Drawing by Force-Directed Placement. 软件 – 实践与经验。

fit(adjacency: csr_matrix | ndarray, position_init: ndarray | None = None, n_iter: int | None = None) Spring[source]

计算布局。

参数:
  • adjacency – 图的邻接矩阵,被视为无向图。

  • position_init (np.ndarray) – 节点的自定义初始位置。形状必须为 (n, 2)。如果为 None,则使用 self.pos_init 的值。

  • n_iter (int) – 更新位置的迭代次数。如果为 None,则使用 self.n_iter 的值。

返回值:

self

返回类型:

弹簧

fit_transform(*args, **kwargs) ndarray

拟合数据并返回嵌入。与 fit 方法相同的参数。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray

get_params()

获取参数作为字典。

返回值:

params – 算法的参数。

返回类型:

dict

predict(adjacency_vectors: csr_matrix | ndarray) ndarray[source]

预测由其邻接向量定义的新行的嵌入。

参数:

adjacency_vectors – 节点的邻接向量。形状为 (n_col,) (单个向量) 或 (n_vectors, n_col) 的数组

返回值:

embedding_vectors – 节点的嵌入。

返回类型:

np.ndarray

set_params(params: dict) Algorithm

设置算法的参数。

参数:

params (dict) – 算法的参数。

返回值:

self

返回类型:

算法

transform() ndarray

返回嵌入。

返回值:

embedding – 嵌入。

返回类型:

np.ndarray