Алгебраическая теория графов: спектры и лапласианы

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

• **PageRank (Google):** алгоритм ранжирования страниц основан на спектре матрицы переходов - второе собственное число определяет скорость сходимости
• **Кластеризация изображений:** спектральная кластеризация Shi-Malik использует вектор Фидлера лапласиана для сегментации
• **Cryptography expanders:** расширяющие графы с малым lambda_2 используются для построения хэш-функций и кодов

Предварительные знания

• Generating Functions

Матрица смежности и спектр графа

Google PageRank обрабатывает граф из 1.9 триллиона страниц, используя спектральные свойства матрицы смежности. Второе по величине собственное число определяет скорость сходимости алгоритма случайных блужданий.

Лапласиан графа и его спектр

Алгоритм спектральной кластеризации Shi-Malik (2000), применявшийся в системах сегментации изображений Nvidia, строится на втором собственном векторе лапласиана. Для изображения 512x512 это задача на собственные числа матрицы 262144x262144.

Ключевые идеи

• **Спектр графа:** собственные числа A вещественны (A симметрична); tr(A^k) считает замкнутые пути длины k
• **Лапласиан L=D-A:** квадратичная форма x^T L x = sum_{(i,j)} (x_i-x_j)^2; кратность нуля = компоненты связности
• **Число Фидлера mu_2:** управляет изопериметрическим числом (неравенство Чигера); mu_2>0 тогда и только тогда, когда граф связен
• **Expander-граф:** d-регулярный граф с lambda_2 <= 2*sqrt(d-1) (граница Рамануджана)

Вопросы для размышления

• Почему кратность нулевого собственного числа лапласиана равна числу компонент связности, а не числу вершин степени 0?
• Как спектральный разрыв lambda_1 - lambda_2 связан со скоростью смешивания случайного блуждания на графе?
• Почему для регулярных графов d-регулярность означает lambda_1=d, а что происходит для нерегулярных?

Связанные уроки

• prob-05-independence