Матрица Лапласа помогает анализировать связность графа и его свойства. 1

Структура графа сети представляется симметричной матрицей Лапласа. 2 Диагональные элементы матрицы определяются степенью соответствующей вершины (количеством связей, исходящих из данных вершин). 2 Недиагональные элементы определяются как −1, если существует связь между парой вершин, и как 0 в противном случае. 2

Некоторые особенности работы матрицы Лапласа в анализе связности графов:

• Сумма элементов любой строки или столбца такой матрицы равна нулю. 2
• Собственные значения матрицы Лапласа являются неотрицательными вещественными числами. 2
• Кратность нулевого собственного значения равна количеству компонент связности. 2
• Наименьшее положительное собственное значение определяет алгебраическую связность рассматриваемого графа. 2
• Собственный вектор, соответствующий этому собственному значению, содержит всю информацию об интересующей структуре графа. 2
• По значениям (величинам) компонент собственного вектора можно сгруппировать вершины графа по отдельным группам, которые называют сообществами. 2