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)[Quelle]#

Gibt den Laplace-Operator eines gerichteten Graphen zurück.

Parameter:

csgrapharray_like oder Sparse-Array oder Matrix, 2 Dimensionen

komprimierter Sparse-Graph mit der Form (N, N).

normedbool, optional

Wenn True, wird der symmetrisch normalisierte Laplace-Operator berechnet. Standard: False.

return_diagbool, optional

Wenn True, wird zusätzlich ein Array zurückgegeben, das mit den Knotengraden zusammenhängt. Standard: False.

use_out_degreebool, optional

Wenn True, wird der Ausgangsgrad anstelle des Eingangsgrads verwendet. Dieser Unterschied ist nur wichtig, wenn der Graph asymmetrisch ist. Standard: False.

copy: bool, optional

Wenn False, wird csgraph nach Möglichkeit direkt geändert, wodurch eine Verdopplung des Speicherbedarfs vermieden wird. Standard: True, aus Gründen der Abwärtskompatibilität.

form: „array“, oder „function“, oder „lo“

Bestimmt das Format des ausgegebenen Laplace-Operators

„array“ ist ein NumPy-Array;
„function“ ist ein Zeiger zur Auswertung des Produkts Laplace-Vektor oder Laplace-Matrix;
„lo“ ergibt das Format des LinearOperator.

Die Wahl von „function“ oder „lo“ vermeidet immer eine Verdopplung des Speicherbedarfs, unabhängig vom Wert von copy. Standard: „array“, aus Gründen der Abwärtskompatibilität.

dtype: None oder einer der numerischen NumPy-Datentypen, optional

Der Datentyp der Ausgabe. Wenn dtype=None, entspricht der Datentyp der Ausgabe dem Datentyp des Eingabe-csgraph, mit Ausnahme des Falls normed=True und eines ganzzahligen csgraph, wobei der Ausgabedatentyp „float“ ist, um eine genaue Normalisierung zu ermöglichen, aber den Speicherbedarf dramatisch erhöht. Standard: None, aus Gründen der Abwärtskompatibilität.

symmetrized: bool, optional

Wenn True, ist der ausgegebene Laplace-Operator symmetrisch/hermitisch. Die Symmetrisierung erfolgt durch csgraph + csgraph.T.conj ohne Division durch 2, um Ganzzahl-Datentypen vor der Konstruktion des Laplace-Operators, falls möglich, zu erhalten. Die Symmetrisierung erhöht den Speicherbedarf von Sparse-Matrizen, es sei denn, das Sparsity-Muster ist symmetrisch oder form ist „function“ oder „lo“. Standard: False, aus Gründen der Abwärtskompatibilität.

Rückgabe:

lapndarray, oder Sparse-Array oder Matrix, oder LinearOperator: Die N x N Laplace-Matrix von csgraph. Sie wird ein NumPy-Array (dicht) sein, wenn die Eingabe dicht war, oder ein Sparse-Array andernfalls, oder das Format einer Funktion oder eines LinearOperator, wenn form „function“ oder „lo“ entspricht.
diagndarray, optional: Die Hauptdiagonale der Laplace-Matrix der Länge N. Für den normalisierten Laplace-Operator ist dies das Array der Quadratwurzeln der Knotengrade oder 1, wenn der Grad Null ist.

Hinweise

Die Laplace-Matrix eines Graphen wird manchmal als „Kirchhoff-Matrix“ oder einfach als „Laplace-Operator“ bezeichnet und ist in vielen Teilen der spektralen Graphentheorie nützlich. Insbesondere kann die Eigen-Zerlegung des Laplace-Operators Einblicke in viele Eigenschaften des Graphen geben, z. B. wird er häufig für die spektrale Daten-Einbettung und Clustering verwendet.

Der konstruierte Laplace-Operator verdoppelt den Speicherbedarf, wenn copy=True und form="array" ist, was dem Standard entspricht. Die Wahl von copy=False hat keine Auswirkung, es sei denn, form="array" oder die Matrix ist im coo-Format spärlich oder ein dichtes Array, außer bei ganzzahligen Eingaben mit normed=True, die eine Float-Ausgabe erzwingen.

Die Sparse-Eingabe wird in coo neu formatiert, wenn form="array", was dem Standard entspricht.

Wenn die eingegebene Adjazenzmatrix nicht symmetrisch ist, ist der Laplace-Operator ebenfalls nicht symmetrisch, es sei denn, symmetrized=True wird verwendet.

Diagonaleinträge der eingegebenen Adjazenzmatrix werden ignoriert und durch Nullen für die Normalisierungszwecke ersetzt, wo normed=True ist. Die Normalisierung verwendet die inversen Quadratwurzeln der Zeilensummen der eingegebenen Adjazenzmatrix und kann daher fehlschlagen, wenn die Zeilensummen negative oder komplexe Werte mit einem nicht-null imaginären Teil enthalten.

Die Normalisierung ist symmetrisch, wodurch der normalisierte Laplace-Operator ebenfalls symmetrisch wird, wenn der eingegebene csgraph symmetrisch war.

Referenzen

[1]

Laplace-Matrix. https://en.wikipedia.org/wiki/Laplacian_matrix

Beispiele

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

Unsere erste Illustration ist der symmetrische Graph

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

und seine symmetrische Laplace-Matrix

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

Der nicht-symmetrische Graph

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

hat unterschiedliche Zeilen- und Spaltensummen, was zu zwei Varianten des Laplace-Operators führt, unter Verwendung eines Eingangsgrads, was dem Standard entspricht

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

oder alternativ eines Ausgangsgrads

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

Beim Erstellen eines symmetrischen Laplace-Operators kann man die beiden addieren als

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

oder die Option symmetrized=True verwenden

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

was der Symmetrisierung des ursprünglichen Graphen entspricht

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

Das Ziel der Normalisierung ist es, die Nicht-Null-Diagonaleinträge der Laplace-Matrix alle auf eins zu setzen und entsprechend auch die Off-Diagonal-Einträge zu skalieren. Die Normalisierung kann manuell erfolgen, z. B.

>>> 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. ]])

Oder mit der Option 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. ]])

die nun anstelle der Diagonale die Skalierungskoeffizienten zurückgibt

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

Null-Skalierungskoeffizienten werden durch Einsen ersetzt, wo die Skalierung somit keine Auswirkung hat, z. B.

>>> 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.])

Nur die symmetrische Normalisierung ist implementiert, was zu einer symmetrischen Laplace-Matrix führt, wenn und nur wenn ihr Graph symmetrisch ist und alle nicht-negativen Grade hat, wie in den obigen Beispielen.

Die Ausgabe-Laplace-Matrix ist standardmäßig ein dichtes Array oder ein Sparse-Array oder eine Sparse-Matrix, die ihre Klasse, Form, Format und ihren Datentyp aus der Eingabe-Graphenmatrix ableitet

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

kann aber alternativ matrixfrei als LinearOperator generiert werden

>>> 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.]])

oder als Lambda-Funktion

>>> 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.]])

Die Laplace-Matrix wird für das spektrale Daten-Clustering und die Einbettung sowie für die spektrale Graphenpartitionierung verwendet. Unser letztes Beispiel illustriert Letzteres für einen verrauschten gerichteten linearen Graphen.

>>> from scipy.sparse import diags_array, random_array
>>> from scipy.sparse.linalg import lobpcg

Erstellen Sie einen gerichteten linearen Graphen mit N=35 Knoten unter Verwendung einer Sparse-Adjazenzmatrix G

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

Setzen Sie einen zufälligen Seed rng und fügen Sie dem Graphen G ein zufälliges Sparse-Rauschen hinzu

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

Setzen Sie anfängliche Annäherungen für die Eigenvektoren

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

Der konstante Vektor Einsen ist immer ein trivialer Eigenvektor des nicht-normalisierten Laplace-Operators, der herausgefiltert werden muss

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

Alternierende (1) Vorzeichen der Graphgewichte ermöglicht die Bestimmung von Labels für spektrale Max- und Min-Cuts in einer einzigen Schleife. Da der Graph ungerichtet ist, muss die Option symmetrized=True bei der Konstruktion des Laplace-Operators verwendet werden. Die Option normed=True kann in (2) für die negativen Gewichte hier nicht verwendet werden, da die symmetrische Normalisierung Quadratwurzeln evaluiert. Die Option form="lo" in (2) ist matrixfrei, d.h. sie garantiert einen festen Speicherbedarf und schreibgeschützten Zugriff auf den Graphen. Der Aufruf des Eigenwertlösers lobpcg (3) berechnet den Fiedler-Vektor, der die Labels als Vorzeichen seiner Komponenten in (5) bestimmt. Da das Vorzeichen in einem Eigenvektor nicht deterministisch ist und umkippen kann, fixieren wir das Vorzeichen der ersten Komponente in (4) immer auf +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]

Wie für einen (leicht verrauschten) linearen Graphen zu erwarten ist, schneidet der Max-Cut alle Kanten des Graphen ab, indem er alle ungeraden Knoten einer Farbe und alle geraden Knoten einer anderen zuordnet, während der balancierte Min-Cut den Graphen in der Mitte partitioniert, indem er eine einzelne Kante löscht. Beide bestimmten Partitionen sind optimal.