laplacian#
- scipy.sparse.csgraph.laplacian(csgraph, normed=False, return_diag=False, use_out_degree=False, *, copy=True, form='array', dtype=None, symmetrized=False)[原始碼]#
傳回有向圖的拉普拉斯算符。
- 參數:
- csgrapharray_like 或稀疏陣列或矩陣，2 維度
壓縮稀疏圖，形狀為 (N, N)。
- normedbool，選用
若為 True，則計算對稱正規化的拉普拉斯算符。預設值：False。
- return_diagbool，選用
若為 True，則同時傳回與頂點度數相關的陣列。預設值：False。
- use_out_degreebool，選用
若為 True，則使用出度而非入度。此區別僅在圖形為非對稱時才有意義。預設值：False。
- copy: bool，選用
若為 False，則盡可能就地更改 csgraph，避免記憶體用量加倍。預設值：True，為了向後相容性。
- form: ‘array’、或 ‘function’、或 ‘lo’
決定輸出拉普拉斯算符的格式
‘array’ 是 numpy 陣列；
‘function’ 是指向評估拉普拉斯向量或拉普拉斯矩陣乘積的指標；
‘lo’ 會產生 LinearOperator 的格式。
選擇 ‘function’ 或 ‘lo’ 始終避免記憶體用量加倍，忽略
copy值。預設值：‘array’，為了向後相容性。- dtype: None 或其中一種數值 numpy dtype，選用
輸出的 dtype。若
dtype=None，則輸出的 dtype 會符合輸入 csgraph 的 dtype，除了normed=True和類似整數的 csgraph 的情況，其中輸出 dtype 為 ‘float’，允許精確正規化，但會大幅增加記憶體用量。預設值：None，為了向後相容性。- symmetrized: bool，選用
若為 True，則輸出拉普拉斯算符為對稱/厄米特算符。對稱化是透過
csgraph + csgraph.T.conj完成，而不除以 2，以便在建構拉普拉斯算符之前盡可能保留整數 dtype。除非稀疏模式是對稱的，或 form 為 ‘function’ 或 ‘lo’，否則對稱化會增加稀疏矩陣的記憶體佔用空間。預設值：False，為了向後相容性。
- 傳回值:
- lapndarray、或稀疏陣列或矩陣、或 LinearOperator
csgraph 的 N x N 拉普拉斯算符。若輸入為密集矩陣，則它會是 NumPy 陣列（密集），否則為稀疏陣列，或若 form 等於 ‘function’ 或 ‘lo’，則為函式或 LinearOperator 的格式。
- diagndarray，選用
拉普拉斯矩陣的長度為 N 的主對角線。對於正規化拉普拉斯算符，這是頂點度數的平方根陣列，或若度數為零則為 1。
註解
圖形的拉普拉斯矩陣有時稱為「克希荷夫矩陣」或僅稱為「拉普拉斯算符」，在光譜圖論的許多部分都很有用。特別是，拉普拉斯算符的特徵分解可以深入了解圖形的許多屬性，例如，通常用於光譜資料嵌入和叢集。
若
copy=True且form="array"（預設值），則建構的拉普拉斯算符會使記憶體用量加倍。除非form="array"或矩陣為coo格式的稀疏矩陣，或密集陣列，否則選擇copy=False無效，但具有normed=True的整數輸入除外，這會強制輸出浮點數。若
form="array"（預設值），則稀疏輸入會重新格式化為coo。若輸入鄰接矩陣不是對稱的，則拉普拉斯算符也是非對稱的，除非使用
symmetrized=True。為了正規化（其中
normed=True），輸入鄰接矩陣的對角線項目會被忽略並替換為零。正規化使用輸入鄰接矩陣的列總和的倒數平方根，因此若列總和包含負值或具有非零虛部的複數值，則可能會失敗。正規化是對稱的，若輸入 csgraph 是對稱的，則正規化拉普拉斯算符也會是對稱的。
參考文獻
[1]範例
>>> 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.])
僅實作對稱正規化，若且唯若其圖形是對稱的且具有所有非負度數（如上述範例中所示），才會產生對稱拉普拉斯矩陣。
輸出拉普拉斯矩陣預設為密集陣列或稀疏陣列或矩陣，從輸入圖形矩陣推斷其類別、形狀、格式和 dtype
>>> 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_array, random_array >>> from scipy.sparse.linalg import lobpcg
使用稀疏鄰接矩陣
G建立具有N=35個頂點的有向線性圖形>>> N = 35 >>> G = diags_array(np.ones(N - 1), offsets=1, format="csr")
修正隨機種子
rng，並將隨機稀疏雜訊新增至圖形G>>> rng = np.random.default_rng() >>> G += 1e-2 * random_array((N, N), density=0.1, rng=rng)
設定特徵向量的初始近似值
>>> X = rng.random((N, 2))
常數向量 1 始終是非正規化拉普拉斯算符的平凡特徵向量，需要濾除
>>> Y = np.ones((N, 1))
交替 (1) 圖形權重的符號允許在單一迴圈中判斷光譜最大割和最小割的標籤。由於圖形為無向圖，因此在建構拉普拉斯算符時必須使用選項
symmetrized=True。此處的負權重無法在 (2) 中使用選項normed=True，因為對稱正規化會評估平方根。 (2) 中的選項form="lo"是矩陣無關的，亦即，保證固定的記憶體佔用空間和對圖形的唯讀存取權。呼叫特徵值求解器lobpcg(3) 會計算 Fiedler 向量，該向量會將標籤判斷為 (5) 中其元件的符號。由於特徵向量中的符號不是確定性的且可能會翻轉，因此我們在 (4) 中將第一個元件的符號固定為始終 +1。>>> 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]
正如對（稍微有雜訊的）線性圖形所預期的那樣，最大割會剝離圖形的所有邊緣，將所有奇數頂點著色為一種顏色，將所有偶數頂點著色為另一種顏色，而平衡最小割會在中間分割圖形，方法是刪除單一邊緣。兩個判斷的分割都是最佳的。