Intuicja za wartościami własnymi macierzy przylegania

10

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?

m.raynal
źródło
Czy znasz związek między widmem macierzy przyległości a zbieżnością losowych spacerów na wykresie?
Yuval Filmus
@YuvalFilmus Wcale nie, pomimo tego, że naprawdę dobrze zna losowe spacery i jakoś zna spektrum macierzy sąsiedztwa. Tak naprawdę interesuje mnie twój widok :)
m.raynal

Odpowiedzi:

6

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λ2t

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)2log2nlog2n

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.

Yuval Filmus
źródło
5

(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)Rnn=|V|f:VRfRnλRAf=λfAGAfvVuN(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)uffλ

dkaeae
źródło
Wielkie dzięki, nigdy nie „widziałem”, że wektor własny pomnożony przez \ lambda ma wartość sumy wartości funkcji sąsiadów (nawet jeśli pochodzi wprost z definicji).
m.raynal
1
Ja też :) Znalazłem to przypadkiem w sylabusie dotyczącym wartości własnych grafów.
dkaeae
5

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 : GdGL=I1dAIn×nAf:VR,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 mamyAdL0λ2AL1λ2d

1λ2d=min{f,Lff,f:vVf(v)=0,f0}.

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 piszf,Lfff:VRf0f0(u)=f(u)1nvVf(v)

1λ2d=min{f,Lff0,f0:f not constant}.

Teraz trochę obliczeń pokazuje, że i podstawiając powyższy oraz dzieląc licznik i mianownik przez , mamyf0,f0=1n{u,v}(V2)(f(u)f(v))2n2

1λ2d=min{2nd(u,v)E(f(u)f(v))22n2{u,v}(V2)(f(u)f(v))2:f not constant}.

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).uGf(u)ddλ2G

Sasho Nikolov
źródło