scipy.sparse.csgraph.

лапласиан#

scipy.sparse.csgraph.лапласиан(csgraph, normed=False, return_diag=False, use_out_degree=False, *, copy=True, форма='array', dtype=None, симметризованный=False)[источник]#

Вернуть лапласиан ориентированного графа.

Параметры:

csgrapharray_like или разреженный массив или матрица, 2 измерения

сжатый разреженный граф с формой (N, N).

normedbool, необязательно

Если True, то вычисляется симметрично нормированный лапласиан. По умолчанию: False.

return_diagbool, необязательно

Если True, то также возвращает массив, связанный со степенями вершин. По умолчанию: False.

use_out_degreebool, необязательно

Если True, то используйте исходящую степень вместо входящей. Это различие имеет значение только если граф асимметричен. По умолчанию: False.

copy: bool, optional

Если False, то изменить csgraph на месте, если возможно, избегая удвоения использования памяти. По умолчанию: True, для обратной совместимости.

форма: ‘array’, или ‘function’, или ‘lo’

Определяет формат выходного лапласиана:

'array' - это массив numpy;
‘function’ — это указатель на вычисление произведения Лапласиан-вектор или Лапласиан-матрица;
‘lo’ приводит к формату LinearOperator.

Выбор 'function' или 'lo' всегда позволяет избежать удвоения использования памяти, игнорируя copy значение. По умолчанию: 'array', для обратной совместимости.

dtype: None или один из числовых типов данных numpy, optional

Тип данных (dtype) вывода. Если dtype=None, тип данных вывода соответствует типу данных входного csgraph, за исключением случая normed=True и целочисленный csgraph, где выходной тип данных 'float' позволяет точную нормализацию, но значительно увеличивает использование памяти. По умолчанию: None, для обратной совместимости.

symmetrized: bool, optional

Если True, то выходной лапласиан симметричный/эрмитов. Симметризация выполняется с помощью csgraph + csgraph.T.conj без деления на 2 для сохранения целочисленных типов данных, если возможно, до построения лапласиана. Симметризация увеличит объем памяти, занимаемый разреженными матрицами, если только структура разреженности не симметрична или форма это 'function' или 'lo'. По умолчанию: False, для обратной совместимости.

Возвращает:

lapndarray, или разреженный массив или матрица, или LinearOperator: Лапласиан N x N для csgraph. Это будет массив NumPy (плотный), если входные данные были плотными, или разреженный массив в противном случае, или формат функции или LinearOperator if форма равно 'function' или 'lo', соответственно.
диагndarray, необязательно: Длина-N главная диагональ матрицы Лапласа. Для нормированной матрицы Лапласа это массив квадратных корней степеней вершин или 1, если степень равна нулю.

Примечания

Матрица Лапласа графа иногда называется «матрицей Кирхгофа» или просто «лапласианом» и полезна во многих разделах спектральной теории графов. В частности, собственное разложение лапласиана может дать представление о многих свойствах графа, например, часто используется для спектрального вложения и кластеризации данных.

Построенный лапласиан удваивает использование памяти, если copy=True и form="array" что является значением по умолчанию. Выбор copy=False не имеет эффекта, если только form="array" или матрица является разреженной в coo формат или плотный массив, за исключением целочисленного ввода с normed=True который принудительно выводит float.

Разреженный вход преобразуется в coo if form="array", что является значением по умолчанию.

Если входная матрица смежности не симметрична, лапласиан также несимметричен, если только symmetrized=True используется.

Диагональные элементы входной матрицы смежности игнорируются и заменяются нулями для целей нормализации, где normed=True. Нормализация использует обратные квадратные корни сумм строк входной матрицы смежности и поэтому может не сработать, если суммы строк содержат отрицательные или комплексные значения с ненулевой мнимой частью.

Нормализация симметрична, что делает нормализованный лапласиан также симметричным, если входной csgraph был симметричным.

Ссылки

[1]

Матрица Лапласа. https://en.wikipedia.org/wiki/Laplacian_matrix

Примеры

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

или как лямбда-функция:

>>> L = csgraph.laplacian(G, form="function")
>>> L
. 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

Создать направленный линейный граф с N=35 вершины с использованием разреженной матрицы смежности G:

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

Постоянный вектор из единиц всегда является тривиальным собственным вектором ненормализованного лапласиана, который нужно отфильтровать:

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

Чередование (1) знака весов графа позволяет определять метки для спектральных максимальных и минимальных разрезов в одном цикле. Поскольку граф неориентированный, опция symmetrized=True должен использоваться при построении лапласиана. Опция normed=True не может использоваться в (2) для отрицательных весов здесь, так как симметричная нормализация вычисляет квадратные корни. Опция form="lo" в (2) не использует матрицы, т.е. гарантирует фиксированный объем памяти и доступ только для чтения к графу. Вызов решателя собственных значений lobpcg (3) вычисляет вектор Фидлера, который определяет метки как знаки его компонентов в (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]

Как и ожидалось для (слегка зашумлённого) линейного графа, максимальный разрез удаляет все рёбра графа, окрашивая все нечётные вершины в один цвет, а все чётные вершины в другой, в то время как сбалансированный минимальный разрез разделяет граф посередине, удаляя одно ребро. Оба определённых разбиения оптимальны.