Алгебраическая связность
Алгебраическая связность (также известная как значение Фидлера или собственное значение Фидлера в честь Мирослава Фидлера ) графа G является вторым наименьшим собственным значением (считая несколько собственных значений отдельно) Лапласа матрицы G . [1] Это собственное значение больше 0 тогда и только тогда, когда G — связный граф . Это следствие того факта, что количество раз, когда 0 появляется в качестве собственного значения в лапласиане, соответствует количеству связных компонентов в графе. Величина этого значения отражает, насколько хорошо связан весь график. Он использовался при анализе устойчивости и синхронизируемости сетей.
Характеристики
[ редактировать ]
Алгебраическая связность неориентированных графов с неотрицательными весами, причем неравенство является строгим тогда и только тогда, когда G связна. Однако алгебраическая связность может быть отрицательной для общих ориентированных графов, даже если G — связный граф . [2] Кроме того, значение алгебраической связности ограничено сверху традиционной (вершинной) связностью графа: . [3] Если число вершин неориентированного связного графа с неотрицательными весами ребер равно n , а диаметр равен D , известно также, что алгебраическая связность ограничена снизу выражением , [4] и фактически (в результате благодаря Брендану Маккею ) . [5] Для графа с 6 узлами, показанного выше (n=6,D=3), эти границы означают: 4/18 = 0,222 ≤ алгебраическая связность 0,722 ≤ связность 1.
В отличие от традиционной формы связности графа , определяемой локальными конфигурациями, удаление которых приведет к отключению графа, алгебраическая связность зависит от глобального количества вершин, а также от способа их соединения. В случайных графах алгебраическая связность уменьшается с увеличением числа вершин и увеличивается с увеличением средней степени . [6]
Точное определение алгебраической связности зависит от типа используемого лапласиана. Фань Чунг разработал обширную теорию, используя измененную версию лапласиана, устраняющую зависимость от количества вершин, так что границы несколько отличаются. [7]
В моделях синхронизации в сетях, таких как модель Курамото , матрица Лапласа возникает естественным образом, поэтому алгебраическая связность дает представление о том, насколько легко сеть будет синхронизироваться. [8] Другие меры, такие как среднее расстояние (характерная длина пути), также могут использоваться. [9] и на самом деле алгебраическая связность тесно связана со средним расстоянием (обратным величине). [5]
Алгебраическая связность также связана с другими атрибутами связности, такими как изопериметрическое число , которое ограничено снизу половиной алгебраической связности. [10]
Вектор Фидлера
[ редактировать ]Оригинальная теория, связанная с алгебраической связностью, была разработана Мирославом Фидлером . [11] [12] В его честь собственный вектор, связанный с алгебраической связностью, был назван вектором Фидлера . Вектор Фидлера можно использовать для разделения графа.
Разбиение графа с помощью вектора Фидлера
[ редактировать ]
Для примера графика во вводном разделе вектор Фидлера равен . Отрицательные значения связаны с плохо связанной вершиной 6 и соседней точкой сочленения , вершиной 4; в то время как положительные значения связаны с другими вершинами. значений Таким образом , знаки вектора Фидлера можно использовать для разделения этого графа на два компонента: . Альтернативно, значение 0,069 (которое близко к нулю) можно поместить в отдельный класс, разделив график на три компонента: или перенесен в другой раздел , как на фото. Квадраты значений компонентов вектора Фидлера, суммирующиеся до единицы, поскольку вектор нормализован, можно интерпретировать как вероятности того, что соответствующие точки данных будут отнесены к знаковому разделу.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Вайсштейн, Эрик В. « Алгебраическая связность ». Из MathWorld — веб-ресурса Wolfram.
- ^ Ву, Чай Вай (2005). «Алгебраическая связность ориентированных графов». Линейная и полилинейная алгебра . 53 (3). Тейлор и Фрэнсис : 203–223. дои : 10.1080/03081080500054810 . S2CID 121368189 .
Даже если G квазисильно связен, что эквивалентно тому, что G содержит ориентированное остовное дерево, a(G) все равно может быть неположительным, как показывают взрывающаяся звезда и теорема 1.
- ^ Гросс, Дж.Л.; Йеллен Дж., ред. (2004). Справочник по теории графов . ЦРК Пресс. п. 314. дои : 10.1201/b16132 . HDL : 2117/22000 . ISBN 0-203-49020-7 .
- ^ Гросс и Йеллен 2004 , с. 571
- ^ Jump up to: а б Мохар, Боян (1991). «Лапласовский спектр графов» (PDF) . В Алави, Ю.; Шартран, Г.; Оллерманн, Орегон ; Швенк, Эй Джей (ред.). Теория графов, комбинаторика и приложения. Материалы шестой раз в два года международной конференции по теории и приложениям графов . Том. 2. Уайли. стр. 871–898. Збл 0840.05059 .
- ^ Холройд, Майкл (2006). «Синхронизация и связность дискретных сложных систем» . Международная конференция по сложным системам .
- ^ Чанг, ФРК (1997). Спектральная теория графов . Серия региональных конференций по математике. Том. 92. Амер. Математика. Соц. ISBN 0-8218-8936-2 . Неполное исправленное издание
- ^ Перейра, Тьяго (2011). «Устойчивость синхронного движения в сложных сетях». arXiv : 1112.2297 [ nlin.AO ].
- ^ Уоттс, Д. (2003). Шесть степеней: наука эпохи подключений . Винтаж. ISBN 0-434-00908-3 . OCLC 51622138 .
- ^ Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Издательство Кембриджского университета. стр. 28, 58. ISBN. 0-521-45897-8 .
- ^ Фидлер, М. (1973). «Алгебраическая связность графов» . Чехословацкий математический журнал . 23 (98): 298–305. дои : 10.21136/CMJ.1973.101168 . МР 0318007 . Збл 0265.05119 .
- ^ Фидлер, М. (1989) [1987]. «Лапласиан графов и алгебраическая связность» . Публикации Банахового центра . 25 (1): 57–70. дои : 10.4064/-25-1-57-70 .