Введение

Второе наименьшее собственное значение графа Лапласа

Алгебраическая связность (также известная как значение Фидлера или собственное значение Фидлера в честь Мирослава Фидлера) графа G — это второе наименьшее собственное значение (при этом кратные собственные значения учитываются отдельно) матрицы Лапласа графа G. Это собственное значение больше 0 тогда и только тогда, когда граф G связный. Это следует из того факта, что количество нулей в спектре матрицы Лапласа равно количеству связных компонент графа. Модуль этого значения отражает степень связности графа в целом. Оно используется для анализа устойчивости и синхронизируемости сетей.

Свойства

Алгебраическая связность ненаправленных графов с неотрицательными весами, причем неравенство строгое тогда и только тогда, когда G связен. Однако алгебраическая связность может быть отрицательной для общих ориентированных графов, даже если G является связным графом. Кроме того, значение алгебраической связности ограничено сверху традиционной (вершинной) связностью графа. Если число вершин ненаправленного связного графа с неотрицательными весами ребер равно n, а диаметр равен D, то алгебраическая связность также ограничена снизу , и фактически (по результату Брендана МакКея) для графа с 6 узлами, показанного выше (n=6, D=3), эти границы означают, что 4/18 = 0.222 ≤ алгебраическая связность ≤ 0.722 ≤ связность 1. В отличие от традиционной связности, алгебраическая связность зависит от числа вершин, а также от способа соединения вершин. В случайных графах алгебраическая связность уменьшается с увеличением числа вершин и увеличивается с увеличением средней степени. Точное определение алгебраической связности зависит от типа используемого лапласиана. Фан Чунг разработал обширную теорию, используя масштабированную версию лапласиана, устраняя зависимость от числа вершин, так что границы несколько иные. В моделях синхронизации в сетях, таких как модель Курамото, матрица Лапласа возникает естественным образом, поэтому алгебраическая связность дает представление о том, насколько легко сеть будет синхронизироваться. Другие меры, такие как среднее расстояние (характерная длина пути), также могут быть использованы, и на самом деле алгебраическая связность тесно связана с (обратной величиной) среднего расстояния.

Вектор Фидлера

Первоначальная теория алгебраической связности была разработана Мирославом Фидлером. В его честь собственный вектор, соответствующий алгебраической связности, получил название вектора Фидлера. Вектор Фидлера можно использовать для разбиения графа на части.

Разделение графа с помощью вектора Фидлера

Для примера графа в вводной части вектор Фидлера выглядит следующим образом. Отрицательные значения соответствуют плохо связанной вершине 6 и соседней точке сочленения, вершине 4, а положительные – остальным вершинам. Таким образом, знаки значений в векторе Фидлера можно использовать для разделения графа на два компонента: в качестве альтернативы, значение 0,069 (которое близко к нулю) можно отнести к отдельному классу, разделив граф на три компонента: или переместить в другой компонент, как показано на рисунке. Квадраты компонентов вектора Фидлера, в сумме дающие единицу, поскольку вектор нормализован, можно интерпретировать как вероятности отнесения соответствующих точек данных к компонентам, сформированным на основе знаков.