Intuicja za wartościami własnymi macierzy przylegania

Obecnie pracuję nad zrozumieniem użycia granicy Cheegera i nierówności Cheegera, a także ich zastosowania do podziału widmowego, przewodnictwa, ekspansji itp., Ale wciąż mam trudności z początkową intuicją dotyczącą drugiej wartości własnej macierzy przylegania.
Zwykle w teorii grafów większość pojęć, które spotykamy, jest dość prosta do intuicji, ale w tym przypadku nie mogę nawet wymyślić, jakiego rodzaju wykresy miałyby drugą wartość własną, która jest bardzo niska lub bardzo wysoka.
Czytałem podobne pytania zadawane tu i tam w sieci SE, ale zazwyczaj dotyczą wartości własnych w różnych dziedzinach ( analizie wieloczynnikowej , Euklidesowej matryce odległość , macierze korelacji ...).
Ale nic o podziale spektralnym i teorii grafów.

Czy ktoś może spróbować podzielić się swoją intuicją / doświadczeniem tej drugiej wartości własnej w przypadku wykresów i macierzy przyległości?

Druga (własna) wartość własna kontroluje szybkość konwergencji losowego przejścia na wykresie. Wyjaśnia to wiele notatek z wykładów, na przykład notatek z wykładów Lucy Trevisana . Z grubsza mówiąc, odległość L2 do jednorodności po krokach może być ograniczona przez .$t$$\lambda_2^t$

Innym miejscem, w którym pojawia się druga wartość własna, jest problem sadzonej kliki . Punktem wyjścia jest obserwacja, że ​​losowy wykres zawiera klikę o rozmiarze , ale chciwy algorytm znajduje tylko klikę o rozmiarze i nie jest znany lepszy algorytm. (Chciwy algorytm po prostu wybiera losowy węzeł, wyrzuca wszystkich nie sąsiadów i powtarza.)$G(n,1/2)$$2\log_2 n$$\log_2 n$

Sugeruje to posadzenie dużej kliki na . Pytanie brzmi: jak duża powinna być klika, abyśmy mogli ją skutecznie znaleźć. Jeśli posadzimy klikę o rozmiarze , wówczas możemy zidentyfikować wierzchołki kliki tylko na podstawie ich stopnia; ale ta metoda działa tylko w przypadku klików o rozmiarze . Możemy to poprawić za pomocą technik spektralnych: jeśli posadzimy klikę o rozmiarze , wówczas drugi wektor własny koduje klikę, jak pokazali Alon, Krivelevich i Sudakov w klasycznej pracy.$G(n,1/2)$$C\sqrt{n\log n}$$\Omega(\sqrt{n\log n})$$C\sqrt{n}$

Mówiąc bardziej ogólnie, kilka pierwszych wektorów własnych jest użytecznych do podziału wykresu na małą liczbę klastrów. Zobacz na przykład rozdział 3 notatek z wykładów Lucy Trevisana , który opisuje nierówności Cheegera wyższego rzędu.

(Zastrzeżenie: Ta odpowiedź dotyczy ogólnie wartości własnych wykresów, a nie drugiej wartości własnej w szczególności. Mam nadzieję, że mimo wszystko jest pomocna).

Ciekawym sposobem myślenia o wartościach własnych wykresu jest przyjęcie przestrzeni wektorowej gdziei identyfikowanie każdego wektora za pomocą funkcji (tj. etykietowanie wierzchołków). Wektor własny macierzy przylegania jest zatem elementem takim, że istnieje (tj. Wartość własna) z , jest matryca przylegania z . Zauważ, że jest wektorem powiązanym z mapą, która wysyła każdy wierzchołek do$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$$A f$$v \in V$$\sum_{u \in N(v)} f(u)$, jest zbiorem sąsiadów (tj. Wierzchołków przylegających do) . Dlatego w tym ustawieniu właściwość wektora własnego odpowiada właściwości, która sumując wartości funkcji (pod ) sąsiadów wierzchołka daje taki sam wynik, jak pomnożenie wartości funkcji wierzchołka przez stałą .$N(v)$$u$$f$$f$$\lambda$

Myślę, że w przypadku większości rzeczy bardziej produktywne jest spojrzenie na Laplaciana z wykresu , który jest ściśle związany z macierzą przylegania. Tutaj możesz go użyć, aby powiązać drugą wartość własną z właściwością „lokalnego vs globalnego” wykresu.$G$

Dla uproszczenia załóżmy, że jest -regular. Wtedy znormalizowanym Laplacianem z jest , gdzie to tożsamość , a to macierz przylegania. Zaletą Laplaciana jest to, że pisząc wektory jako funkcje jak @dkaeae, i używając dla zwykłego produktu wewnętrznego, mamy to bardzo miłe wyrażenie dla formy kwadratowej podanej przez : $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}.$$

Największa wartość własna wynosi i odpowiada najmniejszej wartości własnej , która wynosi ; druga największa wartość własna z odpowiada drugiej najmniejszej wartości własnej , czyli . Zgodnie z zasadą min-max mamy$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\}.$$

Zauważ, że nie zmienia się, gdy przesuwamy o tę samą stałą dla każdego wierzchołka. Tak więc, dla każdej , możesz zdefiniować funkcję „wyśrodkowaną” przez i pisz$\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\}.$$

Teraz trochę obliczeń pokazuje, że i podstawiając powyższy oraz dzieląc licznik i mianownik przez , mamy$\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\}.$$

Znaczy to, że jeśli miejsce każdy wierzchołek z na prostej w punkcie , a średnia odległość pomiędzy dwoma niezależnymi losowych wierzchołków grafu (mianownik) wynosi co najwyżej razy średnia odległość między punktami końcowymi losowej krawędzi na wykresie (licznik). W tym sensie duża luka widmowa oznacza, że ​​to, co dzieje się na losowej krawędzi (zachowanie lokalne), jest dobrym predyktorem tego, co dzieje się na losowej, nieskorelowanej parze wierzchołków (zachowanie globalne).$u$$G$$f(u)$$\frac{d}{d - \lambda_2}$$G$