В математической области теории графов , в лапласиана матрицы , которая также называется граф лапласиан , проводимость матрицы , матрицы Кирхгофа или дискретного лапласиана , является матрица представление графа . Матрицу Лапласа можно использовать для нахождения многих полезных свойств графа. Вместе с теоремой Кирхгофа его можно использовать для вычисления количества остовных деревьев для данного графа. Самый разреженный разрез графа может быть аппроксимирован вторым наименьшим собственным значением его лапласиана неравенством Чигера. Его также можно использовать для создания низкоразмерных вложений , которые могут быть полезны для различных приложений машинного обучения .
Определение
Матрица лапласа для простых графов
Учитывая простой график с участием вершин, ее матрица лапласа определяется как: [1]
где D - матрица степеней, а A - матрица смежности графа. С простой граф, содержит только единицы или нули, а его диагональные элементы - все нули.
В случае ориентированных графов , в зависимости от приложения, может использоваться степень или исходящая степень .
Элементы даны
где степень вершины .
Симметричный нормированный лапласиан
Симметричная нормализованная матрица Лапласа определяется как: [1]
- ,
Элементы даны
Нормированный лапласиан случайного блуждания
Нормированная матрица лапласиана случайного блуждания определяется как:
Элементы даны
Обобщенный лапласиан
Обобщенный лапласиан определяется как: [2]
Обратите внимание, что обычный лапласиан является обобщенным лапласианом.
Пример
Вот простой пример помеченного неориентированного графа и его матрицы Лапласа.
Маркированный график | Матрица степеней | Матрица смежности | Матрица лапласа |
---|---|---|---|
Характеристики
Для (неориентированного) графа G и его матрицы Лапласа L с собственными значениями :
- L является симметричным .
- L является положительным полуопределенной (т.е. для всех ). Это проверено в разделе матрицы инцидентности (ниже). Это также видно из того факта, что лапласиан симметричен и доминирует по диагонали .
- L является M-матрицей (ее недиагональные элементы неположительны, но действительные части ее собственных значений неотрицательны).
- Каждая сумма строк и сумма столбцов L равна нулю. Действительно, в сумме степень вершины суммируется с «-1» для каждого соседа.
- В результате, , потому что вектор удовлетворяет Это также означает, что матрица Лапласа сингулярна.
- Количество компонент связности в графе - это размерность нулевого пространства лапласиана и алгебраическая кратность нулевого собственного значения.
- Наименьшее ненулевое собственное значение оператора L называется спектральной щелью .
- Второе наименьшее собственное значение L (может быть нулем) является алгебраической связностью (или значением Фидлера ) G и аппроксимирует самый разреженный разрез графа.
- Лапласиан является оператором на п-мерном векторном пространстве функций, где - множество вершин графа G, а .
- Когда G k-регулярный , нормализованный лапласиан:, где A - матрица смежности, I - единичная матрица.
- Для графа с множеством компонент связности , L представляет собой блочно - диагональная матрица, в которой каждый блок является соответствующая лапласиан матрица для каждого компонента, возможно , после переупорядочения вершины (т.е. L является перестановкой-подобна блочно - диагональной матрицы).
- След лапласианской матрицы L равен где - количество ребер рассматриваемого графа.
Матрица заболеваемости
Определить ориентированная матрица инцидентности M с элементом M ev для ребра e (соединяющего вершину i и j , с i > j ) и вершиной v, заданной формулой
Тогда матрица Лапласа L удовлетворяет
где это транспонированная матрица из M .
Теперь рассмотрим собственное разложение , с собственными векторами единичной нормы и соответствующие собственные значения :
Так как можно записать как скалярное произведение вектора с собой, это показывает, что так что собственные значения все неотрицательны.
Деформированный лапласиан
Деформируется лапласиан обычно определяется как
где I - единичная матрица, A - матрица смежности, D - матрица степеней, а s - (комплексное) число. [3]
Стандартный лапласиан просто а также - беззнаковый лапласиан.
Беззнаковый лапласиан
Не имеющие маркировки лапласиан определяются как
где матрица степеней, а матрица смежности. [4] Как подписанный лапласиан, беззнаковый лапласиан также является положительным полуопределенным, поскольку может быть разложен на множители как
где - матрица инцидентности. имеет 0-собственный вектор тогда и только тогда, когда он имеет компоненту двудольной связности, отличную от изолированных вершин. Это может быть показано как
У этого есть решение, где тогда и только тогда, когда граф имеет двудольную связную компоненту.
Симметричный нормированный лапласиан
(Симметричный) нормализованы лапласиан определяется как
где L - (ненормализованный) лапласиан, A - матрица смежности, а D - матрица степеней. Поскольку матрица степеней D диагональна и положительна, ее обратный квадратный кореньтолько диагональная матрица, диагональные элементы являются обратными положительными квадратными корнями из диагональных элементов D . Симметричный нормализованный лапласиан - это симметричная матрица.
Надо: , где S - матрица, строки которой индексированы вершинами, а столбцы которой индексированы ребрами G, так что каждый столбец, соответствующий ребру e = {u, v}, имеет запись в строке, соответствующей u, запись в строке, соответствующей v, и имеет 0 записей в другом месте. ( обозначает транспонирование S).
Все собственные значения нормированного лапласиана действительны и неотрицательны. Мы можем увидеть это следующим образом. Ссимметричен, его собственные значения действительны. Они также неотрицательны: рассмотрим собственный вектор из с собственным значением λ и предположим . (Мы можем рассматривать g и f как действительные функции на вершинах v.) Тогда:
где мы используем внутренний продукт , сумма по всем вершинам v, и обозначает сумму по всем неупорядоченным парам смежных вершин {u, v}. Количествоназывается суммой Дирихле функции f, а выражениеназывается фактором Рэлея g.
Пусть 1 будет функцией, которая принимает значение 1 в каждой вершине. потом является собственной функцией с собственным значением 0. [5]
Фактически, собственные значения нормализованного симметричного лапласиана удовлетворяют условию 0 = μ 0 ≤… ≤ μ n − 1 ≤ 2. Эти собственные значения (известные как спектр нормализованного лапласиана) хорошо связаны с другими инвариантами графов для общих графов. [6]
Нормированный лапласиан случайного блуждания
Случайная прогулка нормализованы лапласиан определяется как
где D - матрица степеней. Поскольку матрица степеней D диагональна, ее обратнаяпросто определяются как диагональная матрица, имеющей диагональные элементы , которые являются обратными соответствующими положительными диагональными элементами D .
Для изолированных вершин (имеющих степень 0) обычно выбирают соответствующий элемент до 0.
Это соглашение приводит к хорошему свойству, заключающемуся в том, что кратность собственного значения 0 равна количеству связанных компонентов в графе.
Матричные элементы даны
Название нормализованного лапласиана случайного блуждания связано с тем, что эта матрица имеет вид , где представляет собой просто переходную матрицу случайного блуждающего на графе. Например, пустьобозначим i-й стандартный базисный вектор. потом- вектор вероятности, представляющий распределение местоположений случайного блуждающего человека после того, как он сделал один шаг из вершины; т.е.. В более общем случае, если вектор - распределение вероятностей нахождения случайного блуждающего по вершинам графа, то - распределение вероятностей ходока после шаги.
Это можно проверить
- ,
т.е. это похоже на нормированный лапласиан. По этой причине, даже еслив общем случае не эрмитов, он имеет действительные собственные значения. В самом деле, его собственные значения совпадают с собственными значениями (который является эрмитским).
Графики
Помимо случайных блужданий по графам , рассмотрим простой неориентированный граф . Рассмотрим вероятность того, что пешеход находится в вершине i в момент времени t , учитывая распределение вероятностей того, что он был в вершине j в момент времени t - 1 (при условии равномерного шанса сделать шаг по любому из ребер, прикрепленных к данной вершине) :
или в матрично-векторной записи:
(Равновесие, которое наступает как , определяется .)
Мы можем переписать это соотношение в виде
является симметричной матрицей, называемой приведенной матрицей смежности . Итак, чтобы сделать шаги в этом случайном блуждании, необходимо взять полномочия, что является простой операцией, потому что симметрично.
Интерпретация как дискретный оператор Лапласа
Матрицу Лапласа можно интерпретировать как матричное представление частного случая дискретного оператора Лапласа . Такая интерпретация позволяет, например, обобщить матрицу Лапласа на случай графов с бесконечным числом вершин и ребер, что приведет к матрице Лапласа бесконечного размера.
Предполагать описывает распределение тепла по графику , где тепло в вершине . Согласно закону охлаждения Ньютона тепло, передаваемое от узла к узлу пропорционально если узлы а также подключены (если они не подключены, тепло не передается). Тогда для теплоемкости,
В матрично-векторных обозначениях
который дает
Обратите внимание, что это уравнение принимает ту же форму, что и уравнение теплопроводности , где матрица - L заменяет оператор Лапласа; отсюда и «лапласиан графа».
Чтобы найти решение этого дифференциального уравнения, примените стандартные методы решения матричного дифференциального уравнения первого порядка . То есть напишите как линейная комбинация собственных векторов из L (так что) с зависящими от времени коэффициентами,
Подставляя в исходное выражение (поскольку L - симметричная матрица, ее собственные векторы единичной нормы ортогональны):
чье решение
Как было показано ранее, собственные значения из L неотрицательны, показывая, что решение уравнения диффузии приближается к равновесию, потому что оно только экспоненциально затухает или остается постоянным. Это также показывает, что с учетом и начальное условие , решение может быть найдено в любой момент времени t . [7]
Найти для каждого с точки зрения общего начального состояния , просто проект на собственные векторы единичной нормы ;
- .
Этот подход был применен к количественному моделированию теплопередачи на неструктурированных сетках. [8]
В случае неориентированных графов это работает, потому что симметричен, и по спектральной теореме все его собственные векторы ортогональны. Таким образом, проекция на собственные векторы представляет собой просто ортогональное преобразование координат начального условия в набор координат, которые убывают экспоненциально и независимо друг от друга.
Равновесное поведение
Понимать , единственные условия что остаются те, где , поскольку
Другими словами, равновесное состояние системы полностью определяется ядром из.
Поскольку по определению , вектор из всех находится в ядре. Если естьнепересекающиеся компоненты связности в графе, то этот вектор всех единиц можно разбить на сумму независимый собственные векторы из единиц и нулей, где каждая связная компонента соответствует собственному вектору с единицами в элементах связной компоненты и нулями в других местах.
Следствием этого является то, что для данного начального условия для графика с вершины
где
Для каждого элемента из , т.е. для каждой вершины на графике его можно переписать как
- .
Другими словами, в установившемся режиме значение сходится к одному и тому же значению в каждой из вершин графа, которое представляет собой среднее значение начальных значений во всех вершинах. Поскольку это решение уравнения диффузии тепла, интуитивно это имеет смысл. Мы ожидаем, что соседние элементы на графике будут обмениваться энергией до тех пор, пока эта энергия не будет равномерно распределена по всем элементам, которые связаны друг с другом.
Пример оператора на сетке
В этом разделе показан пример функции распространяется с течением времени по графику. График в этом примере построен на дискретной двумерной сетке с точками на сетке, соединенными с их восемью соседями. У трех начальных точек указано положительное значение, а остальные значения в сетке равны нулю. Со временем экспоненциальный спад действует для равномерного распределения значений в этих точках по всей сетке.
Полный исходный код Matlab, который использовался для создания этой анимации, представлен ниже. Он показывает процесс определения начальных условий, проецирования этих начальных условий на собственные значения матрицы Лапласа и моделирования экспоненциального убывания этих спроектированных начальных условий.
N = 20 ; % Количество пикселей по размеру изображения А = нули ( N , N ); % Изображение Adj = нули ( N * N , N * N ); % Матрица смежности % Используйте 8 соседей и заполните матрицу смежностиdx = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ]; dy = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ]; для x = 1 : N для y = 1 : N индекс = ( х - 1 ) * N + y ; для ne = 1 : длина ( dx ) новыйx = x + dx ( ne ); newy = y + dy ( ne ); если newx > 0 && newx <= N && newy > 0 && newy <= N index2 = ( newx - 1 ) * N + newy ; Adj ( index , index2 ) = 1 ; конец конец конецконец% НИЖЕ КЛЮЧЕВЫЙ КОД, ВЫЧИСЛЯЮЩИЙ РЕШЕНИЕ ДИФФЕРЕНЦИАЛЬНОГО УРАВНЕНИЯ.Deg = diag ( сумма ( Adj , 2 )); % Вычислить матрицу степеней L = Градус - Регулировка ; % Вычислить матрицу лапласиана в терминах матриц степени и смежности [ V , D ] = eig ( L ); % Вычислить собственные значения / векторы матрицы Лапласа D = диаг ( D ); % Начальное состояние (поместите несколько больших положительных значений вокруг и% обнулить все остальное)C0 = нули ( N , N ); С0 ( 2 : 5 , 2 : 5 ) = 5 ; C0 ( 10 : 15 , 10 : 15 ) = 10 ; C0 ( 2 : 5 , 8 : 13 ) = 7 ; C0 = C0 (:); C0V = V '* C0 ; % Преобразуйте начальное условие в систему координат % собственных векторовдля t = 0 : 0,05 : 5 % Время цикла и распад каждого начального компонента Фи = C0V *. Ехр ( - Д * т ); % Экспоненциального распада для каждого компонента Phi = V * Phi ; % Преобразование из системы координат собственного вектора в исходную систему координат Phi = изменить форму ( Phi , N , N ); % Показать результаты и записать в файл GIF imagesc ( Phi ); caxis ([ 0 , 10 ]); title ( sprintf ( 'Diffusion t =% 3f' , t )); кадр = getframe ( 1 ); im = frame2im ( кадр ); [ imind , cm ] = rgb2ind ( im , 256 ); если t == 0 imwrite ( imind , cm , 'out.gif' , 'gif' , 'Loopcount' , inf , 'DelayTime' , 0.1 ); еще imwrite ( imind , cm , 'out.gif' , 'gif' , 'WriteMode' , 'append' , 'DelayTime' , 0.1 ); конецконец
Приближение к отрицательному непрерывному лапласиану
Матрица Лапласа графа может далее рассматриваться как матричная форма приближения к (положительно полуопределенному) оператору Лапласа, полученному методом конечных разностей . (См. Дискретное уравнение Пуассона ) [9] В этой интерпретации каждая вершина графа рассматривается как точка сетки; локальная связность вершины определяет шаблон конечно-разностной аппроксимации в этой точке сетки, размер сетки всегда один для каждого ребра, и нет никаких ограничений на какие-либо точки сетки, что соответствует случаю однородного граничного условия Неймана , т. е. , свободная граница.
Направленные мультиграфы
Аналог матрицы Лапласа можно определить для ориентированных мультиграфов. [10] В этом случае матрица Лапласа L определяется как
где D - диагональная матрица с D i , i, равным исходной степени вершины i, а A - матрица с A i , j, равным количеству ребер от i до j (включая петли).
Смотрите также
- Матрица жесткости
- Расстояние сопротивления
- Матрица скорости перехода
- Исчисление на конечных взвешенных графах
- Графическое преобразование Фурье
Рекомендации
- ^ a b Вайсштейн, Эрик В. «Лапласова матрица» . MathWorld .
- ^ Godsil, C .; Ройл, Г. (2001). Алгебраическая теория графов, выпускные тексты по математике . Springer-Verlag.
- ^ Морбиди, Ф. (2013). «Деформированный протокол консенсуса» (PDF) . Automatica . 49 (10): 3049–3055. DOI : 10.1016 / j.automatica.2013.07.006 .
- ^ Цветкович, Драгош; Симич, Слободан К. (2010). «К спектральной теории графов на основе беззнакового лапласиана, III». Прикладной анализ и дискретная математика . 4 (1): 156–166. DOI : 10.2298 / AADM1000001C . ISSN 1452-8630 . JSTOR 43671298 .
- ^ Чанг, Фань РК (1997). Спектральная теория графов (Repr. С корр., 2. [pr.] Ed.). Провиденс, Род-Айленд: American Math. Soc. ISBN 978-0-8218-0315-8.
- ^ Чанг, Фань (1997) [1992]. Теория спектральных графов . Американское математическое общество. ISBN 978-0821803158.
- ^ Ньюман, Марк (2010). Сети: Введение . Издательство Оксфордского университета. ISBN 978-0199206650.
- ^ Yavari, R .; Коул, KD; Рао, ПК (2020). «Вычислительная теплопередача с помощью спектральной теории графов: количественная проверка» . Международный журнал тепловых наук . 153 : 106383. DOI : 10.1016 / j.ijthermalsci.2020.106383 .
- ^ Смола, Александр Дж .; Кондор, Риси (2003), «Ядра и регуляризация на графах», Теория обучения и машины ядра: 16-я ежегодная конференция по теории обучения и 7-й семинар по ядрам, COLT / Kernel 2003, Вашингтон, округ Колумбия, США, 24–27 августа 2003 г., Материалы , Lecture Notes в области компьютерных наук, 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.
- ^ Chaiken, S .; Клейтман Д. (1978). «Матричные теоремы о дереве». Журнал комбинаторной теории, Серия А . 24 (3): 377–381. DOI : 10.1016 / 0097-3165 (78) 90067-5 . ISSN 0097-3165 .
- Т. Сунада, "Дискретный геометрический анализ", Труды симпозиумов по чистой математике, (под ред. П. Экснера, Дж. П. Китинга, П. Кучмента, Т. Сунада, А. Тепляева), 77 (2008), 51–86.
- Б. Боллобаш , Современная теория графов , Springer-Verlag (1998, исправленное издание 2013 г.), ISBN 0-387-98488-7 , главы II.3 (векторные пространства и матрицы, связанные с графами), VIII.2 (матрица смежности и лапласиан), IX.2 (электрические сети и случайные блуждания).