Матрица Лапласа

В математической области теории графов матрица Лапласа , также называемая графовым лапласианом , матрицей проводимости , матрицей Кирхгофа или дискретным лапласианом , является матричным представлением графа . Названная в честь Пьера-Симона Лапласа , графовая матрица Лапласа может рассматриваться как матричная форма отрицательного дискретного оператора Лапласа на графе, аппроксимирующем отрицательный непрерывный лапласиан, полученный методом конечных разностей .

Матрица Лапласа связана со многими полезными свойствами графа. Вместе с теоремой Кирхгофа ее можно использовать для расчета количества остовных деревьев для данного графа. Самый разреженный разрез графа можно аппроксимировать через вектор Фидлера — собственный вектор, соответствующий второму наименьшему собственному значению лапласиана графа — как установлено неравенством Чигера . Спектральное разложение матрицы Лапласа позволяет строить низкоразмерные вложения , которые появляются во многих приложениях машинного обучения , и определяет спектральную компоновку при построении графа . на основе графов Обработка сигналов основана на графовом преобразовании Фурье , которое расширяет традиционное дискретное преобразование Фурье путем замены стандартного базиса комплексных синусоид на собственные векторы матрицы Лапласа графа, соответствующего сигналу.

Матрицу Лапласа проще всего определить для простого графа , но она чаще встречается в приложениях для графа, взвешенного по ребрам , т. е. с весами на его ребрах — элементами матрицы смежности графа . Спектральная теория графов связывает свойства графа со спектром, то есть собственными значениями и собственными векторами матриц, связанных с графом, таких как его матрица смежности или матрица Лапласа. Несбалансированные веса могут нежелательно влиять на спектр матрицы, что приводит к необходимости нормализации — масштабирования столбца/строки элементов матрицы — что приводит к нормализованной смежности и матрицам Лапласа.

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

Матрица Лапласа

Учитывая простой график $G$ с $n$ вершины $v_{1},\ldots ,v_{n}$, его матрица Лапласа ${\textstyle L_{n\times n}}$ является определяется поэлементно как

$L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}},\end{cases}}$

или, что эквивалентно, матрицей

$L=D-A,$

где D — матрица степеней , а A — матрица смежности графа. С ${\textstyle G}$ представляет собой простой график, ${\textstyle A}$ содержит только 1 или 0, а все его диагональные элементы — 0.

Вот простой пример помеченного неориентированного графа и его матрицы Лапласа.

Маркированный график	Матрица степеней	Матрица смежности	Матрица Лапласа
	${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)}$

Для неориентированного графа мы наблюдаем, что и матрица смежности , и матрица Лапласа симметричны, и что суммы строк и столбцов матрицы Лапласа являются нулями (что напрямую означает, что матрица Лапласа сингулярна).

Для ориентированных графов либо входящая, либо исходящая степень в зависимости от приложения может использоваться , как в следующем примере:

Маркированный график	Матрица смежности	Матрица исходящих степеней	Лапласиан вне степени	Матрица в градусах	Нестепенный лапласиан
	${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&-1&-1\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1\\0&1&-1\\-1&0&2\\\end{array}}\right)}$

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

Матрица Лапласа для неориентированного графа через ориентированную матрицу инцидентности

The ${\textstyle |v|\times |e|}$ ориентированная матрица инцидентности B с элементом B _ve для вершины v и ребра e (соединяющие вершины ${\textstyle v_{i}}$ и ${\textstyle v_{j}}$, где i ≠ j ) определяется формулой

$B_{ve}=\left\{{\begin{array}{rl}1,&{\text{if }}v=v_{i}\\-1,&{\text{if }}v=v_{j}\\0,&{\text{otherwise}}.\end{array}}\right.$

Несмотря на то, что ребра в этом определении технически направлены, их направления могут быть произвольными, что все равно приводит к тому же симметричному лапласиану. ${\textstyle |v|\times |v|}$ матрица L определяется как

$L=BB^{\textsf {T}}$

где ${\textstyle B^{\textsf {T}}}$ является транспонированной B матрицей , .

Неориентированный граф	Матрица заболеваемости	Матрица Лапласа
	${\textstyle \left({\begin{array}{rrrr}1&1&1&0\\-1&0&0&0\\0&-1&0&1\\0&0&-1&-1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}3&-1&-1&-1\\-1&1&0&0\\-1&0&2&-1\\-1&0&-1&2\\\end{array}}\right)}$

Альтернативный продукт $B^{\textsf {T}}B$ определяет так называемый ${\textstyle |e|\times |e|}$ Лапласиан на основе ребер, в отличие от исходной широко используемой Лапласа на основе вершин матрицы L .

Симметричный лапласиан для ориентированного графа

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

В матричной записи матрицу смежности неориентированного графа можно определить, например, как булеву сумму матрицы смежности. $A$ исходного ориентированного графа и его матрицу транспонировать $A^{T}$, где ноль и единица $A$ рассматриваются как логические, а не числовые значения, как в следующем примере:

Матрица смежности	Симметричная смежность	Симметричная матрица Лапласа
${\textstyle \left({\begin{array}{ccc}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{ccc}0&1&1\\1&0&1\\1&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{ccc}2&-1&-1\\-1&2&-1\\-1&-1&2\\\end{array}}\right)}$

Нормализация матрицы Лапласа

Вершина с большой степенью, также называемая тяжелым узлом, приводит к тому, что в матрице Лапласа большая диагональная запись доминирует над свойствами матрицы. Цель нормализации - сделать влияние таких вершин более равным влиянию других вершин путем деления элементов матрицы Лапласа на степени вершин. Чтобы избежать деления на ноль, из процесса нормализации исключаются изолированные вершины с нулевой степенью.

Симметрично нормированный лапласиан

Симметрично нормализованная матрица Лапласа определяется как:

$L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=I-(D^{+})^{1/2}A(D^{+})^{1/2},$

где $D^{+}$ является обратным Муром-Пенроузом .

Элементы ${\textstyle L^{\text{sym}}}$ таким образом, даны

$L_{i,j}^{\text{sym}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}$

Симметрично нормированная матрица Лапласа симметрична тогда и только тогда, когда симметрична матрица смежности.

Матрица смежности	Матрица степеней	Нормализованный лапласиан
${\textstyle \left({\begin{array}{rrr}0&1&0\\1&0&1\\0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-{\sqrt {1/2}}&0\\-{\sqrt {1/2}}&1&-{\sqrt {1/2}}\\0&-{\sqrt {1/2}}&1\\\end{array}}\right)}$

Для несимметричной матрицы смежности ориентированного графа как входящую, так и исходящую степень для нормализации можно использовать :

Матрица смежности	Матрица исходящих степеней	Нормализованный лапласиан вне степени	Матрица в градусах	Нормированный в степени лапласиан
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-{\sqrt {1/2}}&-{\sqrt {1/2}}\\0&1&-1\\-{\sqrt {1/2}}&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-{\sqrt {1/2}}\\0&1&-{\sqrt {1/2}}\\-{\sqrt {1/2}}&0&1\\\end{array}}\right)}$

Левый (случайное блуждание) и правый нормализованный лапласиан

Левая (случайного блуждания) нормализованная матрица Лапласа определяется как:

$L^{\text{rw}}:=D^{+}L=I-D^{+}A,$

где $D^{+}$ является обратным Муром-Пенроузом .Элементы ${\textstyle L^{\text{rw}}}$ даны

$L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}$

Аналогично, нормализованная справа матрица Лапласа определяется как

$LD^{+}=I-AD^{+}$.

Левая или правая нормализованная матрица Лапласа не является симметричной, если матрица смежности симметрична, за исключением тривиального случая, когда все изолированные вершины. Например,

Матрица смежности	Матрица степеней	Левонормированный лапласиан	Правый нормализованный лапласиан
${\textstyle \left({\begin{array}{rrr}0&1&0\\1&0&1\\0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\-1/2&1&-1/2\\0&-1&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-1&1&-1\\0&-1/2&1\\\end{array}}\right)}$

Этот пример также показывает, что если $G$ не имеет изолированных вершин, то $D^{+}A$ правый стохастический и, следовательно, является матрицей случайного блуждания , так что левый нормированный лапласиан $L^{\text{rw}}:=D^{+}L=I-D^{+}A$ каждая строка суммируется до нуля. Таким образом, мы иногда альтернативно называем $L^{\text{rw}}$ нормированный лапласиан случайного блуждания . В менее редко используемом правонормированном лапласиане $LD^{+}=I-AD^{+}$ сумма каждого столбца равна нулю, поскольку $AD^{+}$ остается стохастическим .

Для несимметричной матрицы смежности ориентированного графа также необходимо выбрать входящую или исходящую степень для нормализации:

Матрица смежности	Матрица исходящих степеней	Выходная степень левого нормализованного лапласиана	Матрица в градусах	Нормированный лапласиан в степени справа
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&-1/2\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1/2\\0&1&-1/2\\-1&0&1\\\end{array}}\right)}$

Нормализованный лапласиан левой исходящей степени с суммами строк, равными 0, относится к правому стохастику. $D_{\text{out}}^{+}A$ , в то время как правый нормализованный в степени лапласиан с суммами по столбцам, равными всем 0, содержит левый стохастический $AD_{\text{in}}^{+}$.

Определения графов с взвешенными ребрами

Распространенные в приложениях графы с взвешенными ребрами удобно определять с помощью матриц смежности, где значения записей являются числовыми и больше не ограничиваются нулями и единицами. При спектральной кластеризации на основе графов и обработке сигналов , где вершины графа представляют точки данных, веса ребер могут быть вычислены, например, как обратно пропорциональные расстояниям между парами точек данных, что приводит к тому, что все веса становятся неотрицательными с большими значениями неформально. соответствующие более похожим парам точек данных. Использование корреляции и антикорреляции между точками данных естественным образом приводит как к положительным, так и к отрицательным весам. Большинство определений простых графов тривиально распространяются на стандартный случай неотрицательных весов, тогда как отрицательные веса требуют большего внимания, особенно при нормализации.

Матрица Лапласа

Матрица Лапласа определяется формулой

$L=D-A,$

где D — матрица степеней , а A — матрица смежности графа.

Для ориентированных графов либо входящая, либо исходящая степень в зависимости от приложения может использоваться , как в следующем примере:

Матрица смежности	Матрица в градусах	Нестепенный лапласиан	Матрица исходящих степеней	Лапласиан вне степени
${\textstyle \left({\begin{array}{rrr}0&1&2\\3&0&5\\6&7&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}9&0&0\\0&8&0\\0&0&7\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}9&-1&-2\\-3&8&-5\\-6&-7&7\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&0&0\\0&8&0\\0&0&13\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&-1&-2\\-3&8&-5\\-6&-7&13\\\end{array}}\right)}$

Петли графа, проявляющиеся ненулевыми элементами на главной диагонали матрицы смежности, допускаются, но не влияют на значения лапласа графа.

Симметричный лапласиан через матрицу инцидентности

Двухмерная пружинная система.

Для графов с взвешенными ребрами можно определить взвешенную матрицу инцидентности B и использовать ее для построения соответствующего симметричного лапласиана как $L=BB^{\textsf {T}}$. Альтернативный более чистый подход, описанный здесь, состоит в том, чтобы отделить веса от связности: продолжить использовать матрицу инцидентности, как и для обычных графиков, и ввести матрицу, просто содержащую значения весов. Пружинная система является примером этой модели, используемой в механике для описания системы пружин заданных жесткостей и единичной длины, где значения жесткостей играют роль весов ребер графа.

Таким образом, мы повторно используем определение невесомости. ${\textstyle |v|\times |e|}$ матрица инцидентности B с элементом B _ve для вершины v и ребра e (соединяющие вершины ${\textstyle v_{i}}$ и ${\textstyle v_{j}}$, где i > j ), определяемый формулой

$B_{ve}=\left\{{\begin{array}{rl}1,&{\text{if }}v=v_{i}\\-1,&{\text{if }}v=v_{j}\\0,&{\text{otherwise}}.\end{array}}\right.$

Теперь мы также определим диагональ ${\textstyle |e|\times |e|}$ матрица W, содержащая веса ребер. Несмотря на то, что ребра в определении B технически направлены, их направления могут быть произвольными, что все равно приводит к тому же симметричному лапласиану. ${\textstyle |v|\times |v|}$ матрица L определяется как

$L=BWB^{\textsf {T}}$

где ${\textstyle B^{\textsf {T}}}$ является транспонированной B матрицей , .

Конструкция иллюстрируется следующим примером, где каждое ребро ${\textstyle e_{i}}$ присваивается весовое значение i , при этом ${\textstyle i=1,2,3,4.}$

Неориентированный граф	Матрица заболеваемости	Краевые веса	Матрица Лапласа
	${\textstyle \left({\begin{array}{rrrr}1&1&1&0\\-1&0&0&0\\0&-1&0&1\\0&0&-1&-1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}1&0&0&0\\0&2&0&0\\0&0&3&0\\0&0&0&4\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}6&-1&-2&-3\\-1&1&0&0\\-2&0&6&-4\\-3&0&-4&7\\\end{array}}\right)}$

Симметричный лапласиан для ориентированного графа

Как и в случае с простыми графами, матрица Лапласа ориентированного взвешенного графа по определению обычно несимметрична. Симметрию можно обеспечить, превратив исходный ориентированный граф в неориентированный перед построением лапласиана. Матрица смежности неориентированного графа может быть определена, например, как сумма матрицы смежности $A$ исходного ориентированного графа и его матрицу транспонировать $A^{T}$ как в следующем примере:

Матрица смежности	Симметричная матрица смежности	Симметричная матрица Лапласа
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}0&1&2\\1&0&1\\2&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&-1&-2\\-1&2&-1\\-2&-1&3\\\end{array}}\right)}$

где ноль и единица записи $A$ рассматриваются как числовые, а не логические значения, как для простых графиков, что объясняет разницу в результатах - для простых графиков симметризованный граф все еще должен быть простым, а его симметризованная матрица смежности имеет только логические, а не числовые значения, например логическая сумма равна 1 v 1 = 1, а числовая сумма равна 1 + 1 = 2.

Альтернативно, симметричную матрицу Лапласа можно вычислить из двух лапласианов, используя входящую и выходную степень , как в следующем примере:

Матрица смежности	Матрица исходящих степеней	Лапласиан вне степени	Матрица в градусах	Нестепенный лапласиан
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&-1&-1\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1\\0&1&-1\\-1&0&2\\\end{array}}\right)}$

Сумма транспонированного лапласиана исходящей степени и лапласиана входной степени равна симметричной матрице Лапласа.

Нормализация матрицы Лапласа

Цель нормализации, как и в случае с простыми графами, состоит в том, чтобы сделать все диагональные элементы матрицы Лапласа единичными, а также соответствующим образом масштабировать недиагональные элементы. Во взвешенном графе вершина может иметь большую степень из-за малого числа связных ребер, но с большими весами, а также из-за большого количества связных ребер с единичными весами.

Петли графа, то есть ненулевые элементы на главной диагонали матрицы смежности, не влияют на значения лапласа графа, но их, возможно, придется учитывать для расчета коэффициентов нормализации.

Симметрично нормированный лапласиан

Симметрично нормированный лапласиан определяется как

$L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=I-(D^{+})^{1/2}A(D^{+})^{1/2},$

где L — ненормированный лапласиан, A — матрица смежности, D — матрица степеней, а $D^{+}$ является обратным Муром-Пенроузом . Поскольку матрица степеней D диагональна, ее обратный квадратный корень ${\textstyle (D^{+})^{1/2}}$ - это просто диагональная матрица, диагональные элементы которой являются обратными квадратным корням диагональных элементов D . Если все веса ребер неотрицательны, то все значения степеней автоматически также неотрицательны, и поэтому каждое значение степени имеет уникальный положительный квадратный корень. Чтобы избежать деления на ноль, вершины с нулевой степенью исключаются из процесса нормализации, как в следующем примере:

Матрица смежности	Матрица в градусах	Нормированный в степени лапласиан	Матрица исходящих степеней	Нормализованный лапласиан вне степени
${\textstyle \left({\begin{array}{rrr}0&1&0\\4&0&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&4&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-2&1&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}4&0&0\\0&1&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-2&1&0\\0&0&0\\\end{array}}\right)}$

Симметрично нормированный лапласиан является симметричной матрицей тогда и только тогда, когда матрица смежности A симметрична, а диагональные элементы D неотрицательны, и в этом случае мы можем использовать термин симметричный нормализованный лапласиан .

Симметричную нормализованную матрицу Лапласа можно также записать как

$L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=(D^{+})^{1/2}BWB^{\textsf {T}}(D^{+})^{1/2}=SS^{T}$

используя невесомость ${\textstyle |v|\times |e|}$ матрица инцидентности B и диагональ ${\textstyle |e|\times |e|}$ матрица W, содержащая веса ребер и определяющая новый ${\textstyle |v|\times |e|}$ взвешенная матрица заболеваемости ${\textstyle S=(D^{+})^{1/2}BW^{{1}/{2}}}$ строки которого индексируются вершинами, а столбцы индексируются рёбрами G, так что каждый столбец, соответствующий ребру e = {u, v}, имеет запись ${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$ в строке, соответствующей u , запись ${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$ в строке, соответствующей v , и имеет 0 записей в других местах.

Случайное блуждание, нормализованный лапласиан

Нормированный лапласиан случайного блуждания определяется как

$L^{\text{rw}}:=D^{+}L=I-D^{+}A$

где D — матрица степеней. Поскольку матрица степеней D диагональна, ее обратная ${\textstyle D^{+}}$ просто определяется как диагональная матрица, имеющая диагональные элементы, обратные соответствующим диагональным элементам D . Для изолированных вершин (со степенью 0) обычно выбирают соответствующий элемент ${\textstyle L_{i,i}^{\text{rw}}}$ до 0. Матричные элементы ${\textstyle L^{\text{rw}}}$ даны

$L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if}}\ i=j\ {\mbox{and}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}$

Название нормализованного лапласиана случайного блуждания происходит от того факта, что эта матрица имеет вид ${\textstyle L^{\text{rw}}=I-P}$, где ${\textstyle P=D^{+}A}$ это просто матрица перехода случайного блуждающего человека на графе, предполагающая неотрицательные веса. Например, пусть ${\textstyle e_{i}}$ обозначают i-й стандартный базисный вектор. Затем ${\textstyle x=e_{i}P}$ - вектор вероятности, представляющий распределение местоположений случайного пешехода после того, как он сделал один шаг от вершины ${\textstyle i}$; то есть, ${\textstyle x_{j}=\mathbb {P} \left(v_{i}\to v_{j}\right)}$. В более общем случае, если вектор ${\textstyle x}$ — распределение вероятностей местоположения случайного блуждающего человека по вершинам графа, тогда ${\textstyle x'=xP^{t}}$ - распределение вероятностей ходока после ${\textstyle t}$ шаги.

Нормированный лапласиан случайного блуждания также можно назвать левым нормализованным лапласианом. $L^{\text{rw}}:=D^{+}L$ поскольку нормализация осуществляется путем умножения лапласиана на матрицу нормализации $D^{+}$ слева. Сумма каждой строки равна нулю, поскольку $P=D^{+}A$ является правым стохастическим , предполагая, что все веса неотрицательны.

В менее редко используемом правонормированном лапласиане $LD^{+}=I-AD^{+}$ сумма каждого столбца равна нулю, поскольку $AD^{+}$ остается стохастическим .

Для несимметричной матрицы смежности ориентированного графа также необходимо выбрать входящую или исходящую степень для нормализации:

Матрица смежности	Матрица исходящих степеней	Выходная степень левого нормализованного лапласиана	Матрица в градусах	Нормированный лапласиан в степени справа
${\textstyle \left({\begin{array}{rrr}0&1&0\\0&0&2\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\0&1&-1\\-1&0&1\\\end{array}}\right)}$

Нормализованный лапласиан левой исходящей степени с суммами строк, равными 0, относится к правому стохастику. $D_{\text{out}}^{+}A$ , в то время как правый нормализованный в степени лапласиан с суммами по столбцам, равными всем 0, содержит левый стохастический $AD_{\text{in}}^{+}$.

Отрицательные веса

Отрицательные веса создают несколько проблем для нормализации:

• Наличие отрицательных весов естественным образом может привести к нулевым суммам строк и/или столбцов для неизолированных вершин. Вершина с большой суммой строк положительных весов и столь же отрицательно большой суммой строк отрицательных весов, которые вместе дают ноль, может считаться тяжелым узлом, и оба больших значения масштабируются, в то время как диагональный элемент остается нулевым, как для изолированная вершина.
• Отрицательные веса могут также давать отрицательные суммы строк и/или столбцов, так что соответствующая диагональная запись в ненормализованной матрице Лапласа будет отрицательной и положительный квадратный корень, необходимый для симметричной нормализации, не будет существовать.
• Можно привести аргументы в пользу принятия абсолютного значения сумм строк и/или столбцов с целью нормализации, таким образом рассматривая возможное значение -1 как допустимую единицу измерения главной диагонали нормализованной матрицы Лапласа.

Характеристики

Для (неориентированного) графа G и его матрицы Лапласа L с собственными значениями ${\textstyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}$:

• L симметричен ​ .
• L положительно -полуопределенный (т.е. ${\textstyle \lambda _{i}\geq 0}$ для всех ${\textstyle i}$). Это видно из того, что лапласиан симметричен и доминирует по диагонали .
• L — M-матрица (ее недиагональные элементы неположительны, но вещественные части ее собственных значений неотрицательны).
• Каждая сумма строк и сумма столбцов L равна нулю. Действительно, в сумме степень вершины суммируется с «-1» для каждого соседа.
• В результате ${\textstyle \lambda _{0}=0}$, поскольку вектор ${\textstyle \mathbf {v} _{0}=(1,1,\dots ,1)}$ удовлетворяет ${\textstyle L\mathbf {v} _{0}=\mathbf {0} .}$ Это также означает, что матрица Лапласа сингулярна.
• Количество компонентов связности в графе — это размерность нулевого пространства лапласиана и алгебраическая кратность собственного значения 0.
• Наименьшее ненулевое собственное значение L называется спектральной щелью .
• Второе наименьшее собственное значение L (может быть равно нулю) представляет собой алгебраическую связность (или значение Фидлера ) G и аппроксимирует самый разреженный разрез графа.
• Лапласиан — это оператор в n-мерном векторном пространстве функций ${\textstyle f:V\to \mathbb {R} }$, где ${\textstyle V}$ - множество вершин G, и ${\textstyle n=|V|}$.
• Когда G является k-регулярным , нормализованный лапласиан имеет вид: ${\textstyle {\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A}$, где A — матрица смежности, а I — единичная матрица.
• Для графа с несколькими связными компонентами L представляет собой блочную диагональную матрицу, где каждый блок представляет собой соответствующую матрицу Лапласа для каждого компонента, возможно, после переупорядочения вершин (т. е. L аналогична перестановке блочной диагональной матрице).
• След матрицы Лапласа L равен ${\textstyle 2m}$ где ${\textstyle m}$ – количество ребер рассматриваемого графа.
• Теперь рассмотрим собственное разложение ${\textstyle L}$, с собственными векторами единичной нормы ${\textstyle \mathbf {v} _{i}}$ и соответствующие собственные значения ${\textstyle \lambda _{i}}$:

${\begin{aligned}\lambda _{i}&=\mathbf {v} _{i}^{\textsf {T}}L\mathbf {v} _{i}\\&=\mathbf {v} _{i}^{\textsf {T}}M^{\textsf {T}}M\mathbf {v} _{i}\\&=\left(M\mathbf {v} _{i}\right)^{\textsf {T}}\left(M\mathbf {v} _{i}\right).\\\end{aligned}}$

Потому что ${\textstyle \lambda _{i}}$ можно записать как внутренний продукт вектора ${\textstyle M\mathbf {v} _{i}}$ с самим собой, это показывает, что ${\textstyle \lambda _{i}\geq 0}$ и поэтому собственные значения ${\textstyle L}$ все неотрицательны.

• Все собственные значения нормализованного симметричного лапласиана удовлетворяют условию 0 = µ ₀ ⩽ … ⩽ µ _n−1 ⩽ 2. Эти собственные значения (известные как спектр нормализованного лапласиана) хорошо соотносятся с другими инвариантами графов для общих графов.

• Это можно проверить:

$L^{\text{rw}}=I-D^{-{\frac {1}{2}}}\left(I-L^{\text{sym}}\right)D^{\frac {1}{2}}$,

то есть, ${\textstyle L^{\text{rw}}}$ аналогичен нормированному лапласиану ${\textstyle L^{\text{sym}}}$. По этой причине, даже если ${\textstyle L^{\text{rw}}}$ вообще не симметричен, имеет вещественные собственные значения — точно такие же, как собственные значения нормированного симметричного лапласиана ${\textstyle L^{\text{sym}}}$.

Интерпретация как дискретный оператор Лапласа, аппроксимирующий непрерывный лапласиан

Графовую матрицу Лапласа можно далее рассматривать как матричную форму отрицательного дискретного оператора Лапласа на графе, аппроксимирующем отрицательный непрерывный оператор Лапласа, полученный методом конечных разностей .(См. Дискретное уравнение Пуассона ) В этой интерпретации каждая вершина графа рассматривается как точка сетки; локальная связность вершины определяет шаблон конечно-разностной аппроксимации в этой точке сетки, размер сетки всегда один для каждого ребра, и нет никаких ограничений на какие-либо точки сетки, что соответствует случаю однородного граничного условия Неймана , т.е. , свободная граница. Такая интерпретация позволяет, например, обобщить матрицу Лапласа на случай графов с бесконечным числом вершин и ребер, что приведет к матрице Лапласа бесконечного размера.

Обобщения и расширения матрицы Лапласа.

Обобщенный лапласиан

Обобщенный лапласиан $Q$ определяется как:

${\begin{cases}Q_{i,j}<0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\Q_{i,j}=0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is not adjacent to }}v_{j}\\{\mbox{any number}}&{\mbox{otherwise}}.\end{cases}}$

Обратите внимание, что обычный лапласиан является обобщенным лапласианом.

Магнитный лапласиан

Элементы матрицы смежности могут быть комплексными, и в этом случае понятие симметрии матрицы необходимо заменить эрмитовой матрицей . Магнитный лапласиан для ориентированного графа с действительными весами $w_{ij}$ строится как произведение Адамара вещественной симметричной матрицы симметризованного лапласиана и эрмитовой фазовой матрицы с комплексными элементами

$\gamma _{q}(i,j)=e^{i2\pi q(w_{ij}-w_{ji})}$

которые кодируют направление фронта в фазу в комплексной плоскости.В контексте квантовой физики магнитный лапласиан можно интерпретировать как оператор, описывающий феноменологию свободной заряженной частицы на графе, подверженной действию магнитного поля и параметра $q$ называется электрическим зарядом. В следующем примере $q=1/4$:

Матрица смежности	Симметризованный лапласиан	Фазовая матрица	Магнитный лапласиан
${\textstyle \left({\begin{array}{rrrr}0&1&0&0\\1&0&1&0\\0&0&0&0\\0&0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}2&-2&0&0\\-2&3&-1&0\\0&-1&2&-1\\0&0&-1&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}1&1&1&1\\1&1&i&1\\1&-i&1&-i\\1&1&i&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}2&-2&0&0\\-2&3&-i&0\\0&i&2&i\\0&0&-i&1\\\end{array}}\right)}$

Деформированный лапласиан

обычно Деформированный лапласиан определяется как

$\Delta (s)=I-sA+s^{2}(D-I)$

где I — единичная матрица, A — матрица смежности, D — матрица степеней, а s — (комплексное) число.
Стандартный лапласиан просто ${\textstyle \Delta (1)}$ и ${\textstyle \Delta (-1)=D+A}$ является беззнаковым лапласианом.

Беззнаковый лапласиан

определяется Беззнаковый лапласиан как

$Q=D+A$

где $D$ - матрица степеней, а $A$ – матрица смежности. Как подписанный лапласиан $L$, беззнаковый лапласиан $Q$ также является положительно полуопределенным, поскольку его можно факторизовать как

$Q=RR^{\textsf {T}}$

где ${\textstyle R}$ – матрица инцидентности. $Q$ имеет 0-собственный вектор тогда и только тогда, когда он имеет двудольную связную компоненту (изолированные вершины являются двудольными связными компонентами). Это можно показать как

$\mathbf {x} ^{\textsf {T}}Q\mathbf {x} =\mathbf {x} ^{\textsf {T}}RR^{\textsf {T}}\mathbf {x} \implies R^{\textsf {T}}\mathbf {x} =\mathbf {0} .$

Это имеет решение, где $\mathbf {x} \neq \mathbf {0}$ тогда и только тогда, когда граф имеет двудольную компоненту связности.

Направленные мультиграфы

Аналог матрицы Лапласа можно определить для ориентированных мультиграфов. В этом случае матрица Лапласа L определяется как

$L=D-A$

где D — диагональная матрица с D _{i , i} равна исходящей степени вершины i, а A — матрица с A _{i , j} равна количеству ребер от i до j (включая петли).

Реализации программного обеспечения с открытым исходным кодом

• SciPy
• СетьX
• Юлия

Прикладное программное обеспечение

• scikit-learn Спектральная кластеризация
• PyGSP: обработка сигналов графа в Python
• megaman: многообразное обучение за миллионы очков
• гладкийG
• Обнаружение точки изменения Лапласа для динамических графиков (KDD 2020)
• LaplacianOpt (Пакет Julia для максимизации второго собственного значения Лапласа взвешенных графов)
• LigMG (Большой нерегулярный граф MultiGrid)
• Лапласианцы.jl

См. также

• Матрица жесткости
• Расстояние сопротивления
• Матрица скорости перехода
• Исчисление на конечных взвешенных графах
• Графовое преобразование Фурье