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?
źródło
Odpowiedzi:
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 λt2
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) 2log2n log2n
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) Cnlogn−−−−−√ Ω(nlogn−−−−−√) Cn−−√
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.
źródło
(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 doG=(V,E) Rn n=|V| f:V→R f∈Rn λ∈R Af=λf A G Af v∈V ∑u∈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 λ
źródło
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−1dA I n×n A f:V→R ⟨⋅,⋅⟩ L ⟨f,Lf⟩=1d∑(u,v)∈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 mamyA d L 0 λ2 A L 1−λ2d
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⟨f,Lf⟩ f f:V→R f0 f0(u)=f(u)−1n∑v∈Vf(v)
Teraz trochę obliczeń pokazuje, że i podstawiając powyższy oraz dzieląc licznik i mianownik przez , mamy⟨f0,f0⟩=1n∑{u,v}∈(V2)(f(u)−f(v))2 n2
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) dd−λ2 G
źródło