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