scipy.sparse.csgraph.

laplacian#

scipy.sparse.csgraph.laplacian(csgraph, normed=False, return_diag=False, use_out_degree=False, *, copy=True, form='array', dtype=None, symmetrized=False)[源代码][源代码]#

返回有向图的拉普拉斯矩阵。

参数:
csgraph类数组或稀疏矩阵，2 维

压缩稀疏图，形状为 (N, N)。

标准化bool, 可选

如果为 True，则计算对称归一化拉普拉斯算子。默认值：False。

return_diagbool, 可选

如果为 True，则还会返回一个与顶点度数相关的数组。默认值：False。

use_out_degreebool, 可选

如果为 True，则使用出度而不是入度。这种区别仅在图是非对称时才重要。默认值：False。

copy: bool, 可选

如果为 False，则在可能的情况下就地更改 csgraph，以避免内存使用量翻倍。默认值：True，为了向后兼容。

表单: ‘数组’, 或 ‘函数’, 或 ‘lo’

确定输出拉普拉斯算子的格式：

  • ‘array’ 是一个 numpy 数组；

  • ‘function’ 是指向计算拉普拉斯向量或拉普拉斯矩阵乘积的指针；

  • ‘lo’ 结果为 LinearOperator 的格式。

选择 ‘function’ 或 ‘lo’ 总是避免内存使用翻倍，忽略 copy 值。默认：’array’，为了向后兼容。

dtype: None 或 numpy 数值类型之一，可选

输出的数据类型。如果 dtype=None，输出的数据类型与输入的 csgraph 的数据类型匹配，除非在 normed=True 且 csgraph 为整数类型的情况下，输出的数据类型为 ‘float’，以允许准确的标准化，但会显著增加内存使用。默认值：None，为了向后兼容。

symmetrized: bool, 可选

如果为 True，则输出的拉普拉斯算子是对称/厄米特的。对称化通过 csgraph + csgraph.T.conj 进行，不除以 2 以尽可能保留整数数据类型，在构造拉普拉斯算子之前。对称化将增加稀疏矩阵的内存占用，除非稀疏模式是对称的，或者 form 是 ‘function’ 或 ‘lo’。默认值：False，为了向后兼容。

返回:
lap : ndarray, 或稀疏矩阵, 或 LinearOperatorndarray，或稀疏矩阵，或

csgraph 的 N x N 拉普拉斯矩阵。如果输入是密集的，它将是一个 NumPy 数组（密集），否则将是一个稀疏矩阵，或者如果 form 分别等于 ‘function’ 或 ‘lo’，则它将是一个函数或 LinearOperator 的格式。

diagndarray，可选

拉普拉斯矩阵的长度为 N 的主对角线。对于归一化拉普拉斯矩阵，这是顶点度数的平方根数组，如果度数为零则为 1。

注释

图的拉普拉斯矩阵有时被称为“基尔霍夫矩阵”或简称为“拉普拉斯矩阵”，在谱图理论的许多部分中都很有用。特别是，拉普拉斯矩阵的特征分解可以深入了解图的许多属性，例如，通常用于谱数据嵌入和聚类。

如果 copy=True 且 form="array" ，构造的拉普拉斯矩阵会加倍内存使用，这是默认设置。选择 copy=False 在 form="array" 或矩阵在 coo 格式下稀疏，或稠密数组的情况下无效，除非输入为整数且 normed=True 强制输出为浮点数。

如果 form="array"，稀疏输入将被重新格式化为 coo，这是默认设置。

如果输入的邻接矩阵不是对称的，除非使用 symmetrized=True ，否则拉普拉斯矩阵也将是非对称的。

输入邻接矩阵的对角线项在 normed=True 的情况下会被忽略并替换为零，以进行归一化处理。归一化使用输入邻接矩阵行和的平方根倒数，因此如果行和包含负值或具有非零虚部的复数值，则可能会失败。

归一化是对称的，如果输入的 csgraph 是对称的，那么归一化的拉普拉斯矩阵也是对称的。

参考文献

示例

>>> import numpy as np
>>> from scipy.sparse import csgraph

我们的第一个示例是对称图

>>> G = np.arange(4) * np.arange(4)[:, np.newaxis]
>>> G
array([[0, 0, 0, 0],
       [0, 1, 2, 3],
       [0, 2, 4, 6],
       [0, 3, 6, 9]])

及其对称拉普拉斯矩阵

>>> csgraph.laplacian(G)
array([[ 0,  0,  0,  0],
       [ 0,  5, -2, -3],
       [ 0, -2,  8, -6],
       [ 0, -3, -6,  9]])

非对称图

>>> G = np.arange(9).reshape(3, 3)
>>> G
array([[0, 1, 2],
       [3, 4, 5],
       [6, 7, 8]])

具有不同的行和列和，从而产生两种类型的拉普拉斯矩阵，使用入度，这是默认的

>>> L_in_degree = csgraph.laplacian(G)
>>> L_in_degree
array([[ 9, -1, -2],
       [-3,  8, -5],
       [-6, -7,  7]])

或者是一个出度

>>> L_out_degree = csgraph.laplacian(G, use_out_degree=True)
>>> L_out_degree
array([[ 3, -1, -2],
       [-3,  8, -5],
       [-6, -7, 13]])

构造一个对称的拉普拉斯矩阵，可以将两者相加。

>>> L_in_degree + L_out_degree.T
array([[ 12,  -4,  -8],
        [ -4,  16, -12],
        [ -8, -12,  20]])

或使用 symmetrized=True 选项

>>> csgraph.laplacian(G, symmetrized=True)
array([[ 12,  -4,  -8],
       [ -4,  16, -12],
       [ -8, -12,  20]])

这相当于对称化原始图

>>> csgraph.laplacian(G + G.T)
array([[ 12,  -4,  -8],
       [ -4,  16, -12],
       [ -8, -12,  20]])

归一化的目标是使拉普拉斯矩阵的非零对角线元素全部为单位值，同时相应地缩放非对角线元素。归一化可以手动完成，例如，

>>> G = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
>>> L, d = csgraph.laplacian(G, return_diag=True)
>>> L
array([[ 2, -1, -1],
       [-1,  2, -1],
       [-1, -1,  2]])
>>> d
array([2, 2, 2])
>>> scaling = np.sqrt(d)
>>> scaling
array([1.41421356, 1.41421356, 1.41421356])
>>> (1/scaling)*L*(1/scaling)
array([[ 1. , -0.5, -0.5],
       [-0.5,  1. , -0.5],
       [-0.5, -0.5,  1. ]])

或者使用 normed=True 选项

>>> L, d = csgraph.laplacian(G, return_diag=True, normed=True)
>>> L
array([[ 1. , -0.5, -0.5],
       [-0.5,  1. , -0.5],
       [-0.5, -0.5,  1. ]])

现在，它不再返回对角线，而是返回缩放系数

>>> d
array([1.41421356, 1.41421356, 1.41421356])

零缩放系数被替换为1，因此缩放没有效果，例如，

>>> G = np.array([[0, 0, 0], [0, 0, 1], [0, 1, 0]])
>>> G
array([[0, 0, 0],
       [0, 0, 1],
       [0, 1, 0]])
>>> L, d = csgraph.laplacian(G, return_diag=True, normed=True)
>>> L
array([[ 0., -0., -0.],
       [-0.,  1., -1.],
       [-0., -1.,  1.]])
>>> d
array([1., 1., 1.])

仅实现了对称归一化，当且仅当其图是对称的且具有所有非负度时，才会生成对称拉普拉斯矩阵，如上例所示。

输出拉普拉斯矩阵默认情况下是一个密集数组或一个稀疏矩阵，根据输入图矩阵推断其形状、格式和数据类型：

>>> G = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]]).astype(np.float32)
>>> G
array([[0., 1., 1.],
       [1., 0., 1.],
       [1., 1., 0.]], dtype=float32)
>>> csgraph.laplacian(G)
array([[ 2., -1., -1.],
       [-1.,  2., -1.],
       [-1., -1.,  2.]], dtype=float32)

但也可以作为 LinearOperator 无矩阵生成：

>>> L = csgraph.laplacian(G, form="lo")
>>> L
<3x3 _CustomLinearOperator with dtype=float32>
>>> L(np.eye(3))
array([[ 2., -1., -1.],
       [-1.,  2., -1.],
       [-1., -1.,  2.]])

或作为 lambda 函数：

>>> L = csgraph.laplacian(G, form="function")
>>> L
<function _laplace.<locals>.<lambda> at 0x0000012AE6F5A598>
>>> L(np.eye(3))
array([[ 2., -1., -1.],
       [-1.,  2., -1.],
       [-1., -1.,  2.]])

拉普拉斯矩阵用于光谱数据聚类和嵌入，以及光谱图划分。我们的最终示例展示了后者在一个有噪声的有向线性图上的应用。

>>> from scipy.sparse import diags, random
>>> from scipy.sparse.linalg import lobpcg

使用稀疏邻接矩阵 G 创建一个有向线性图，其中 N=35 个顶点：

>>> N = 35
>>> G = diags(np.ones(N-1), 1, format="csr")

修复一个随机种子 rng 并在图 G 中添加随机稀疏噪声：

>>> rng = np.random.default_rng()
>>> G += 1e-2 * random(N, N, density=0.1, random_state=rng)

设置特征向量的初始近似值：

>>> X = rng.random((N, 2))

常数向量1总是未归一化拉普拉斯矩阵的一个平凡特征向量，需要被滤除：

>>> Y = np.ones((N, 1))

交替（1）图权重的符号允许在单个循环中确定谱最大和最小割的标签。由于图是无向的，必须在拉普拉斯矩阵的构造中使用选项 symmetrized=True。选项 normed=True 不能在（2）中用于这里的负权重，因为对称归一化会计算平方根。选项 form="lo" 在（2）中是无矩阵的，即，保证固定的内存占用和只读访问图。调用特征值求解器 ``lobpcg``（3）计算确定标签的Fiedler向量，其分量的符号在（5）中确定标签。由于特征向量中的符号不是确定性的，并且可以翻转，我们将第一个分量的符号固定为始终为+1（4）。

>>> for cut in ["max", "min"]:
...     G = -G  # 1.
...     L = csgraph.laplacian(G, symmetrized=True, form="lo")  # 2.
...     _, eves = lobpcg(L, X, Y=Y, largest=False, tol=1e-2)  # 3.
...     eves *= np.sign(eves[0, 0])  # 4.
...     print(cut + "-cut labels:\n", 1 * (eves[:, 0]>0))  # 5.
max-cut labels:
[1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
min-cut labels:
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

正如对一个（略带噪声的）线性图的预期，最大割将所有边都去掉，将所有奇数顶点涂成一种颜色，将所有偶数顶点涂成另一种颜色，而平衡最小割则通过删除一条边将图从中间分割。这两种确定的分割都是最优的。

On this page