Интуиция за собственными значениями матрицы смежности

В настоящее время я работаю над тем, чтобы понять использование границы Чигера и неравенства Чигера и их использование для спектрального разделения, проводимости, расширения и т. Д., Но я все еще изо всех сил пытаюсь понять, что такое второе собственное значение матрицы смежности.
Обычно в теории графов большинство концепций, с которыми мы сталкиваемся, довольно просты для интуитивного понимания, но в этом случае я даже не могу придумать, какой тип графиков будет иметь второе собственное значение, очень низкое или очень высокое.
Я читал подобные вопросы, задаваемые здесь и там в сети SE, но они обычно относятся к собственным значениям в различных областях ( многомерный анализ , евклидовы матрицы расстояний , корреляционные матрицы ...).
Но ничего о спектральном разбиении и теории графов.

Может кто-то попытаться поделиться своей интуицией / опытом этого второго собственного значения в случае графов и матриц смежности?

Второе (по величине) собственное значение управляет скоростью сходимости случайного блуждания на графике. Это объясняется во многих лекционных заметках, например, в лекционных заметках Луки Тревизана . Грубо говоря, расстояние L2 до равномерности после шагов может быть ограничено .$t$$\lambda_2^t$

Другое место, где появляется второе собственное значение, это проблема посаженной клики . Отправной точкой является наблюдение, что случайный граф содержит клику размером , но жадный алгоритм находит только клику размером , и лучший эффективный алгоритм не известен. (Жадный алгоритм просто выбирает случайный узел, отбрасывает всех не соседей и повторяет).$G(n,1/2)$$2\log_2 n$$\log_2 n$

Это предполагает посадку большой клики на вершине . Вопрос в том, насколько большой должна быть клика, чтобы мы могли ее эффективно найти. Если мы установим клику размером , то мы сможем идентифицировать вершины клики только по их степени; но этот метод работает только для кликов размером . Мы можем улучшить это, используя спектральные методы: если мы установим клику размером , то второй собственный вектор закодирует клику, как показали Алон, Кривелевич и Судаков в классической статье.$G(n,1/2)$$C\sqrt{n\log n}$$\Omega(\sqrt{n\log n})$$C\sqrt{n}$

В более общем смысле первые несколько собственных векторов полезны для разбиения графа на небольшое количество кластеров. См., Например, главу 3 лекционных заметок Луки Тревизана , в которой описываются неравенства Чигера высшего порядка.

(Отказ от ответственности: Этот ответ касается собственных значений графов в целом, а не второго собственного значения в частности. Я надеюсь, что он, тем не менее, полезен.)

Интересный способ размышления о собственных значениях графа $G = (V, E)$ состоит в том, чтобы взять векторное пространство $\mathbb{R}^n$ где $n = |V|$и отождествление каждого вектора с функцией $f\colon V \to \mathbb{R}$ (т. е. маркировка вершины). Собственный вектор матрицы смежности, то есть элемент $f \in \mathbb{R}^n$ такое , что существует $\lambda \in \mathbb{R}$ (то есть, собственный) с $A f = \lambda f$ , $A$является матрицей смежности $G$ . Обратите внимание , что е есть вектор , связанный с картой , который посылает каждую вершину v ∈ V в Е U ∈ N ( v ) F ( U ) , N ( v ) является набор соседей (то есть, вершины , смежные с) у . Следовательно, в этой настройке свойство собственного вектора функции f соответствует свойству, которое суммируется по значениям функции (при f )$A f$$v \in V$$\sum_{u \in N(v)} f(u)$$N(v)$$u$$f$$f$соседей вершины дает тот же результат, что и умножение значения функции вершины на постоянную $\lambda$ .

$G$

$G$$d$$G$$L= I - \frac1d A$$I$$n\times n$$A$$f: V\to \mathbb{R}$$\langle \cdot, \cdot \rangle$$L$

$$\langle f, Lf\rangle = \frac{1}{d} \sum_{(u,v) \in E}{(f(u) - f(v))^2}.$$

$A$$d$$L$$0$$\lambda_2$$A$$L$$1 - \frac{\lambda_2}{d}$

$$1 - \frac{\lambda_2}{d}=\min\left\{\frac{\langle f, Lf\rangle}{\langle f, f\rangle}:\sum_{v \in V}{f(v)} = 0, f \neq 0\right\}.$$

Обратите внимание, что не меняется, когда мы сдвигаем на одну и ту же константу для каждой вершины. Таким образом, эквивалентно, вы можете определить для любого «центрированную» функцию помощью и напишите$\langle f, Lf\rangle$$f$$f:V \to \mathbb{R}$$f_0$$f_0(u) = f(u) - \frac{1}{n}\sum_{v \in V}{f(v)}$

$$1 - \frac{\lambda_2}{d}=\min\left\{\frac{\langle f, Lf\rangle}{\langle f_0, f_0\rangle}: f \text{ not constant}\right\}.$$

Теперь немного вычислений показывает, что , и, подставив вышеприведенное и разделив числитель и знаменатель на , получим$\langle f_0, f_0\rangle = \frac{1}{n}\sum_{\{u,v\}\in {V\choose 2}}{(f(u) - f(v))^2}$$\frac{n}{2}$

$$1 - \frac{\lambda_2}{d}=\min\left\{\frac{\frac{2}{nd} \sum_{(u,v) \in E}{(f(u) - f(v))^2}}{\frac{2}{n^2}\sum_{\{u,v\}\in {V\choose 2}}{(f(u) - f(v))^2}}: f \text{ not constant}\right\}.$$

Это означает, что если мы поместим каждую вершину из на вещественную линию в точке , то среднее расстояние между двумя независимыми случайными вершинами в графе (знаменателе) будет не больше - среднее расстояние между конечными точками случайного ребра в графе (числитель). Таким образом, в этом смысле большой спектральный разрыв означает, что то, что происходит через случайный край (локальное поведение), является хорошим предиктором того, что происходит через случайную некоррелированную пару вершин (глобальное поведение).$u$$G$$f(u)$$\frac{d}{d - \lambda_2}$$G$