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

Матричное представление графа

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

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

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

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

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

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

${\displaystyle 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}}}$

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

${\displaystyle L=D-A,}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где – обратное Мура–Пенроуза . ${\displaystyle D^{+}}$

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

${\displaystyle 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}}}$

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

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

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

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

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

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

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

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

${\displaystyle L=D-A,}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$

Название нормализованного лапласиана случайного блуждания происходит от того факта, что эта матрица равна , где — просто матрица перехода случайного блуждающего человека на графе с учетом неотрицательных весов. Например, пусть обозначает i-й стандартный базисный вектор. Тогда — вектор вероятности , представляющий распределение местоположений случайного пешехода после того, как он сделал один шаг от вершины ; то есть, . В более общем смысле, если вектор представляет собой распределение вероятностей местоположения случайного пешехода в вершинах графа, то это распределение вероятностей пешехода после шагов. ${\textstyle L^{\text{rw}}=I-P}$ ${\textstyle P=D^{+}A}$ ${\textstyle e_{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}$

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

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

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

Нормализованный лапласиан левой исходящей степени с суммами строк, равными всем 0, относится к правому стохастику , тогда как нормализованный лапласиан правой внутренней степени с суммами столбцов, равными всем 0, содержит левый стохастик . ${\displaystyle D_{\text{out}}^{+}A}$ ${\displaystyle 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-мерном векторном пространстве функций , где – множество вершин G, и . ${\textstyle f:V\to \mathbb {R} }$ ${\textstyle V}$ ${\textstyle n=|V|}$
• Когда G является k-регулярным , нормализованный лапласиан имеет вид: , где A — матрица смежности, а I — единичная матрица. ${\textstyle {\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A}$
• Для графа с несколькими связными компонентами L представляет собой блочную диагональную матрицу, где каждый блок представляет собой соответствующую матрицу Лапласа для каждого компонента, возможно, после переупорядочения вершин (т. е. L аналогична перестановке блочной диагональной матрице).
• След матрицы Лапласа L равен где – числу ребер рассматриваемого графа. ${\textstyle 2m}$ ${\textstyle m}$
• Теперь рассмотрим собственное разложение с собственными векторами единичной нормы и соответствующими собственными значениями : ${\textstyle L}$ ${\textstyle \mathbf {v} _{i}}$ ${\textstyle \lambda _{i}}$

${\displaystyle {\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. Эти собственные значения (известные как спектр нормализованного лапласиана) хорошо связаны с другими инвариантами графов для общих графов. ^[1]

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

${\displaystyle 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}}}$

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

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

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

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

Обобщенный лапласиан определяется как: ^[3] ${\displaystyle Q}$

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle Q=D+A}$

где – матрица степеней, – матрица смежности. ^[6] Как и знаковый лапласиан , беззнаковый лапласиан также является положительно полуопределенным, поскольку его можно факторизовать как ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle L}$ ${\displaystyle Q}$

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

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

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

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

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

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

${\displaystyle L=D-A}$

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

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

• СкиПи ^[8]
• СетьX ^[9]
• Юлия ^[10]

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

• scikit-learn Спектральная кластеризация ^[11]
• PyGSP: обработка сигналов графа в Python ^[12]
• мегамен: многообразное обучение для миллионов очков ^[13]
• гладкийG ^[14]
• Обнаружение точки изменения по Лапласу для динамических графиков (KDD 2020) ^[15]
• LaplacianOpt (Пакет Julia для максимизации второго собственного значения Лапласа взвешенных графов) ^[16]
• LigMG (MultiGrid с большими нерегулярными графами) ^[17]
• Лапласианцы.jl ^[18]

Смотрите также

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

Рекомендации

1. Чунг, Фан (1997) [1992]. Спектральная теория графов. Американское математическое общество. ISBN 978-0821803158.
2. Смола, Александр Дж.; Кондор, Ризи (2003), «Ядра и регуляризация на графах», Теория обучения и машины с ядром: 16-я ежегодная конференция по теории обучения и 7-й семинар по ядрам, COLT/Kernel 2003, Вашингтон, округ Колумбия, США, 24–27 августа 2003 г., Труды , Конспекты лекций по информатике, вып. 2777, Springer, стр. 144–158, CiteSeerX 10.1.1.3.7020 , doi : 10.1007/978-3-540-45167-9_12, ISBN  978-3-540-40720-1.
3. Годсил, К.; Ройл, Г. (2001). Алгебраическая теория графов, Тексты для аспирантов по математике . Спрингер-Верлаг.
4. Сатоши Фурутани; Тошики Сибахара; Мицуаки Акияма; Кунио Хато; Масаки Аида (2020). Обработка графовых сигналов для ориентированных графов на основе эрмитова лапласиана (PDF) . ECML PKDD 2019: Машинное обучение и обнаружение знаний в базах данных. стр. 447–463. дои : 10.1007/978-3-030-46150-8_27.
5. Морбиди, Ф. (2013). «Протокол деформированного консенсуса» (PDF) . Автоматика . 49 (10): 3049–3055. doi :10.1016/j.automatica.2013.07.006. S2CID  205767404.
6. Цветкович, Драгош; Симич, Слободан К. (2010). «К спектральной теории графов, основанной на беззнаковом лапласиане, III». Прикладной анализ и дискретная математика . 4 (1): 156–166. дои : 10.2298/AADM1000001C . ISSN  1452-8630. JSTOR  43671298.
7. Чайкен, С.; Клейтман, Д. (1978). «Теоремы о матричном дереве». Журнал комбинаторной теории, серия А. 24 (3): 377–381. дои : 10.1016/0097-3165(78)90067-5 . ISSN  0097-3165.
8. "SciPy". Гитхаб . 4 октября 2023 г.
9. "СетьX". Гитхаб . 4 октября 2023 г.
10. "Юлия". Гитхаб . 4 октября 2023 г.
11. «2.3. Кластеризация».
12. «PyGSP: обработка сигналов графа в Python» . Гитхаб . 23 марта 2022 г.
13. «Мегамен: Многообразное обучение на миллионы очков» . Гитхаб . 14 марта 2022 г.
14. "ГладкийG". Гитхаб . 17 сентября 2020 г.
15. «Анонсируем нашу статью на KDD 2020» .
16. "Harshangrjn/LaplacianOpt.jl" . Гитхаб . 2 февраля 2022 г.
17. «LigMG (Large Irregular Graph MultiGrid) — лапласовский решатель графов с распределенной памятью для больших нерегулярных графов» . Гитхаб . 5 января 2022 г.
18. "Лапласианцы.jl". Гитхаб . 11 марта 2022 г.