Dokumenty do uznania za spektralny podział grafów

27

Jeśli jest nieukierunkowane -regular wykres i jest podzbiorem wierzchołków liczności , wywołać ekspansję krawędzi o o ilościd S | V | / 2G=(V,E)dS|V|/2S

ϕ(S):=Edges(S,VS)d|S||VS|

Gdzie jest liczbą krawędzi z jednego punktu końcowego w i jednego punktu końcowego w . Następnie problemem rozszerzenia krawędzi jest znalezienie zestawu z który minimalizuje . Wywołaj rozszerzenie optymalnego zestawu.A BEdges(A,B)AB| S | | V | / 2 ϕ ( S ) ϕ ( G )S|S||V|/2ϕ(S)ϕ(G)

Widmowa podziału Algorytm do problemu rozszerzeń krawędź działa od stwierdzenia wektor własny z drugiej największej wartości własnej macierz przylegania do , i biorąc pod uwagę wszystkie `` zestawów progowe „” formy powyżej wszystkich progów . Jeśli pozwolimy, aby była drugą co do wielkości wartością własną macierzy , wówczas analiza algorytmu podziału spektralnego pokazuje, że najlepszy zestaw progów znaleziony przez algorytm spełniaA G S { v : x ( v ) t } t λ 2 1xAGS{v:x(v)t}tλ2SSP1dASSP

ϕ(SSP)2ϕ(G)

Wynika to z nierówności Cheegera

ϕ(SSP)2(1λ2)

i

1λ22ϕ(G)

Jaki jest pierwszy artykuł, który wysunął takie roszczenie? Jakie dokumenty mają przypisać pomysły? Oto co mam:

  • N. Alon i VD Milman. , nierówności izoperymetryczne dla wykresów i superkoncentratory, Journal of Combinatorial Theory, Series B, 1985, 38 (1): 73-88 λ1

    Udowodnij wynik w duchu „prostej” nierówności Cheegera , ale zamiast ekspansji wierzchołków zamiast ekspansji krawędzi. Uznaj, że związek między ekspansją krawędzi a wartościami własnymi jest dyskretną wersją problemu badanego przez Cheegera w 1λ22ϕ(G)

    J. Cheeger. Dolna granica najmniejszej wartości własnej Laplaciana. Problemy w analizie, 1970.

  • N. Alon. Wartości własne i ekspandery. Combinatorica. 6 (2): 83–96, 1986.

    Udowadnia wynik w duchu trudnej nierówności Cheegera ale do rozszerzenia wierzchołków zamiast rozszerzenia krawędzi. ϕ(SSP)2(1λ2)

  • A. Sinclair, M. Jerrum. Przybliżone liczenie, jednolite generowanie i szybkie mieszanie łańcuchów Markowa. Information and Computation 82: 93-133, 1989 (wersja konferencyjna 1987)

    Udowodnij nierówności Cheegera, jak wspomniano powyżej. (Ich praca bada przewodnictwo_ odwracalnych w czasie łańcuchów Markowa, które zdarzają się na równi z ekspansją krawędzi na regularnych wykresach). Za techniki przypisują pracę Alona i Milmana oraz Alona. Uznają również Aldousa za powiązaną granicę między czasem mieszania a rozszerzaniem krawędzi na zwykłych wykresach.

  • M. Mihail. Przewodnictwo i zbieżność łańcuchów Markowa - kombinatoryczne leczenie ekspanderów. FOCS 1989, strony 526–531

    Chociaż głównym punktem pracy jest to, że jej techniki mają zastosowanie do nieodwracalnych w czasie łańcuchów Markowa, to gdy stosuje się ją do zwykłych grafów bezkierunkowych, ma ona przewagę nad poprzednimi pracami: pokazuje, że jeśli uruchomimy algorytm podziału widmowego z arbitralnym wektor, nadal uzyskuje się nierówność gdzie jest ilorazem Rayleigha wektora. Argumenty Alona, ​​Milmana, Sinclaira i Jerruma wymagają rzeczywistego wektora własnego. Jest to istotne w przypadku algorytmów szybkiego podziału widmowego, które wykorzystują przybliżone wektory własne. λϕ(SSP)2(1λ)λ

Czy są inne dokumenty, które należy zapisać w zakresie technik dowodowych?

Kiedy znaczenie algorytmiczne powyższych wyników, jako algorytmów podziału grafów, jest po raz pierwszy rozpoznawane? Powyższe artykuły nie mają takiej dyskusji.

Luca Trevisan
źródło
Bardzo drobny komentarz: Widziałem oznaczające liczbę krawędzi między i (zwykle podczas omawiania cięcia maks./min. wykresu). A B [ S , ¯ S ][A,B]AB[S,S¯]
Derrick Stolee

Odpowiedzi:

10

Wydaje się, że pierwszym referatem wprowadzającym ten zestaw pomysłów (przy użyciu niezmiennika algebraicznego , drugiej najmniejszej wartości własnej wykresu Laplaciana, w celu powiązania różnych właściwości wykresu) do teorii grafów była „Algebraiczna łączność wykresów” Fiedlera w czechosłowackiej matematyce Dziennik. Pojawił się w 1973 roku, mniej więcej w tym samym czasie, co artykuł Cheegera (1970), który zajmował się rozmaitością. Nie jestem pewien, kto jako pierwszy zaobserwował podobieństwo między wykresami i rozmaitościami. jest czasem nazywana liczbą Fiedlera.λ 2λ2λ2

Co ciekawe, na końcu artykułu Fiedlera znajduje się uwaga, wskazująca na niezależny raport techniczny Andersona i Morleya zatytułowany Wartości własne Laplaciana na wykresie z 1971 r., Który najwyraźniej miał podobne pomysły. Jednak artykuł Andersona i Morleya o tym samym tytule ukazał się w Algebrze liniowej i wieloliniowej dopiero w 1985 roku.

Misza Belkin
źródło
6

Kilka dodatkowych odniesień, które pamiętam z tamtej epoki:

1) Diaconis i Stroock, Geometryczne granice wartości własnych łańcuchów Markowa, The Annals of Applied Probabil, 1991; ale pamiętam, jak kiedyś dostałem preprint w 1990 roku. To z kolei odnosi się do tego artykułu

2) Dodziuk, Równania różnicowe, nierówność izoperymetryczna i przemijalność niektórych losowych spacerów, Transactions of the American Mathematical Society, 1984.

Istotnym dokumentem „towarzyszącego algorytmu” dla Sinclaira i Jerruma w tym czasie był

3) Dyer Frieze Kannan, algorytm losowego wielomianu czasowego do aproksymacji objętości ciał wypukłych, STOC 89. Oczywiście, wyniki tutaj zostały zbudowane na SJ.

V Vinay
źródło