Введение
Матричное представление графа
В математической области теории графов, матрица Лапласа, также называемая графовым Лапласом, матрицей проводимости, матрицей Кирхгофа или дискретным Лапласом, является матричным представлением графа. Названная в честь Пьера Симона Лапласа, матрица Лапласа графа может рассматриваться как матричная форма отрицательного дискретного оператора Лапласа на графе, аппроксимирующая отрицательный непрерывный Лапласиан, полученный методом конечных разностей. Матрица Лапласа связана со многими полезными свойствами графа. Вместе с теоремой Кирхгофа она может быть использована для вычисления числа остовных деревьев для заданного графа. Минимальный разрез графа можно приближенно вычислить с помощью вектора Фидлера — собственного вектора, соответствующего второму наименьшему собственному значению графа Лапласа, как установлено неравенством Чигера. Спектральное разложение матрицы Лапласа позволяет строить низкоразмерные вложения, которые используются во многих приложениях машинного обучения, и определяет спектральную компоновку при визуализации графов. Сигнальная обработка на основе графов основана на преобразовании Фурье графа, которое расширяет традиционное дискретное преобразование Фурье путем замены стандартного базиса комплексных синусоид на собственные векторы матрицы Лапласа графа, соответствующие сигналу. Матрицу Лапласа легче всего определить для простого графа, но она более распространена в приложениях для взвешенного графа, то есть графа с весами на ребрах — элементами матрицы смежности графа. Спектральная теория графов связывает свойства графа со спектром, то есть собственными значениями и собственными векторами матриц, связанных с графом, таких как матрица смежности или матрица Лапласа. Несбалансированные веса могут нежелательно влиять на спектр матрицы, что приводит к необходимости нормализации — масштабированию элементов матрицы по столбцам и строкам, — в результате чего получаются нормализованные матрицы смежности и Лапласа.
In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method. The Laplacian matrix relates to many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the Fiedler vector — the eigenvector corresponding to the second smallest eigenvalue of the graph Laplacian — as established by Cheeger's inequality. The spectral decomposition of the Laplacian matrix allows constructing low dimensional embeddings that appear in many machine learning applications and determines a spectral layout in graph drawing. Graph based signal processing is based on the graph Fourier transform that extends the traditional discrete Fourier transform by substituting the standard basis of complex sinusoids for eigenvectors of the Laplacian matrix of a graph corresponding to the signal. The Laplacian matrix is the easiest to define for a simple graph, but more common in applications for an edge weighted graph, i. e., with weights on its edges — the entries of the graph adjacency matrix. Spectral graph theory relates properties of a graph to a spectrum, i. e., eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. Imbalanced weights may undesirably affect the matrix spectrum, leading to the need of normalization — a column/row scaling of the matrix entries — resulting in normalized adjacency and Laplacian matrices.
Нормализация матрицы Лапласа
Вершина с большой степенью, также называемая тяжелым узлом, приводит к большому значению на главной диагонали матрицы Лапласа, которое оказывает доминирующее влияние на свойства матрицы. Нормализация направлена на то, чтобы уменьшить влияние таких вершин и сделать его более сопоставимым с влиянием других вершин, путем деления элементов матрицы Лапласа на степени вершин. Чтобы избежать деления на ноль, изолированные вершины с нулевой степенью исключаются из процесса нормализации.
Симметрически нормализованный лаплациан
Симметрично нормализованная матрица Лапласа определяется как: В данной интерпретации каждая вершина графа рассматривается как точка сетки; локальная связность вершины определяет шаблон дискретизации с использованием конечных разностей в этой точке сетки, размер ячейки сетки всегда равен единице для каждого ребра, и на все точки сетки не наложено никаких ограничений, что соответствует случаю однородного граничного условия Неймана, то есть свободной границе. Такая интерпретация позволяет, например, обобщить матрицу Лапласа на случай графов с бесконечным числом вершин и ребер, что приводит к матрице Лапласа бесконечного размера.
Направленные мультиграфы
Аналог матрицы Лапласа может быть определен для ориентированных мультиграфов. В этом случае матрица Лапласа L определяется как
где D — диагональная матрица с элементами Di,i, равными полустепени исходящих ребер вершины i, а A — матрица с элементами Ai,j, равными количеству ребер от вершины i к вершине j (включая петли).