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

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

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

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

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

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

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

Для простого графа с вершинами его матрица Лапласа определяется поэлементно как ^[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} .}$
• Число связных компонент в графе равно размерности нулевого пространства лапласиана и алгебраической кратности нулевого собственного значения.
• Наименьшее ненулевое собственное значение 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}}}$

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

Матрица проводимости цепи переменного тока

Лапласиан графа был впервые введен для моделирования электрических сетей. В электрической сети переменного тока (AC) действительные сопротивления заменяются комплексными импедансами. Вес ребра ( i , j ) по соглашению равен минус обратной величине импеданса непосредственно между i и j . В моделях таких сетей элементы матрицы смежности являются комплексными, но матрица Кирхгофа остается симметричной, а не эрмитовой . Такая матрица обычно называется « матрицей проводимости », обозначаемой , а не «лапласианом». Это одно из редких приложений, которые приводят к появлению комплексных симметричных матриц . ${\displaystyle Y}$

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

Существуют и другие ситуации, в которых элементы матрицы смежности являются комплексными, и лапласиан становится эрмитовой матрицей . Магнитный лапласиан для ориентированного графа с действительными весами строится как произведение Адамара действительной симметричной матрицы симметризованного лапласиана и эрмитовой фазовой матрицы с комплексными элементами ${\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 (включая петли).

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

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

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

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

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

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

Ссылки

1. Chung, Fan (1997) [1992]. Теория спектральных графов. Американское математическое общество. ISBN 978-0821803158.
2. Smola, Alexander J.; Kondor, Risi (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). Алгебраическая теория графов, Выпускные тексты по математике . Springer-Verlag.
4. Сатоши Фурутани; Тошики Шибахара; Мицуаки Акияма; Кунио Хато; Масаки Айда (2020). Обработка сигналов графа для направленных графов на основе эрмитова лапласиана (PDF) . ECML PKDD 2019: Машинное обучение и обнаружение знаний в базах данных. стр. 447–463. doi :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. doi : 10.2298/AADM1000001C . ISSN  1452-8630. JSTOR  43671298.
7. Chaiken, S.; Kleitman, D. (1978). «Теоремы о матричном дереве». Журнал комбинаторной теории, серия A. 24 ( 3): 377–381. doi : 10.1016/0097-3165(78)90067-5 . ISSN  0097-3165.
8. "SciPy". GitHub . 4 октября 2023 г.
9. "NetworkX". GitHub . 4 октября 2023 г.
10. "Джулия". GitHub . 4 октября 2023 г.
11. "2.3. Кластеризация".
12. "PyGSP: Обработка графических сигналов в Python". GitHub . 23 марта 2022 г.
13. "Megaman: многообразное обучение для миллионов точек". GitHub . 14 марта 2022 г.
14. "SmoothG". GitHub . 17 сентября 2020 г.
15. «Анонсируем нашу статью на KDD 2020» .
16. "Harshangrjn/LaplacianOpt.jl". GitHub . 2 февраля 2022 г.
17. "LigMG (Large Irregular Graph MultiGrid) — решатель задач Лапласа с распределенной памятью для больших нерегулярных графов". GitHub . 5 января 2022 г.
18. "Laplacians.jl". GitHub . 11 марта 2022 г.