Aufsätze für die spektrale Aufteilung von Graphen

Wenn ein ungerichteter regelmäßiger Graph ist und eine Teilmenge der Eckpunkte der Kardinalität , nenne die Kantenexpansion von die Menged S ≤ | V | / 2 $G=(V,E)$$d$$S$$\leq |V|/2$$S$

$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$

Wo ist die Anzahl der Kanten mit einem Endpunkt in und einem Endpunkt in . Dann besteht das Kantenerweiterungsproblem darin, eine Menge mit , die minimiert . Nenne die Erweiterung einer optimalen Menge.A $Edges(A,B)$$A$$B$| S | ≤ | V | / 2 ϕ ( S ) ϕ ( G $S$$|S|\leq |V|/2$$\phi(S)$$\phi(G)$

Die Spectral Partitionierungsalgorithmus für das Problem Edge - Erweiterung funktioniert durch ein Eigenvektor zu finden des zweitgrößten Eigenwert von , die Adjazenzmatrix von und unter Berücksichtigung dann alle `` Schwelle Sätze ‚‘ der Form über alle Schwellenwerte . Wenn der zweitgrößte Eigenwert der Matrix , dann zeigt die Analyse des Spektralpartitionierungsalgorithmus, dass der vom Algorithmus gefundene beste Schwellensatz erfüllt istA G S { v : x ( v ) ≤ t } t λ 2 $x$$A$$G$$S$$\{ v : x(v) \leq t \}$$t$$\lambda_2$SS$\frac 1d \cdot A$$S_{SP}$

$\phi(S_{SP}) \leq 2\sqrt {\phi(G)}$

Was sich aus den Cheeger-Ungleichungen ergibt

$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

und

$1-\lambda_2 \leq 2 \phi(G)$

Was ist das erste Papier, das eine solche Behauptung aufstellt? Welche Papiere sind für die Ideen zu würdigen? Folgendes habe ich:

• N. Alon und VD Milman. , isoperimetrische Ungleichungen für Graphen und Superkonzentratoren, Journal of Combinatorial Theory, Series B, 1985, 38 (1): 73-88 $\lambda_1$

  Beweisen Sie ein Ergebnis im Geiste der "einfachen" Cheeger-Ungleichung , jedoch für die Scheitelpunkterweiterung anstelle der Kantenerweiterung. Erkennen Sie, dass die Beziehung zwischen Kantenexpansion und Eigenwerten die diskrete Version eines von Cheeger in untersuchten Problems ist $1-\lambda_2 \leq 2\phi(G)$

  J. Cheeger. Eine Untergrenze für den kleinsten Eigenwert des Laplace. Probleme in der Analyse, 1970.

• N. Alon. Eigenwerte und Expander. Combinatorica. 6 (2): 83 & ndash; 96, 1986.

  Beweist ein Ergebnis im Geiste der schwierigen Cheeger-Ungleichung jedoch für die Scheitelpunkterweiterung anstelle der Kantenerweiterung. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

• A. Sinclair, M. Jerrum. Ungefähre Zählung, gleichmäßige Erzeugung und schnelles Mischen von Markov-Ketten. Information and Computation 82: 93-133, 1989 (Konferenzversion 1987)

  Beweisen Sie die Cheeger-Ungleichungen wie oben angegeben. (Ihre Arbeit untersucht die Leitfähigkeit von zeitreversiblen Markov-Ketten, die in regelmäßigen Graphen gleich der Kantenexpansion ist.) Sie schreiben die Arbeit von Alon und Milman und von Alon für die Techniken zu. Sie schreiben Aldous auch eine verwandte Grenze zwischen Mischzeit und Kantenexpansion in regulären Diagrammen zu.

• M Mihail. Leitfähigkeit und Konvergenz von Markov-Ketten - eine kombinatorische Behandlung von Expandern. FOCS 1989, Seiten 526-531

  Während der Hauptpunkt der Arbeit darin besteht, dass seine Techniken für nicht-zeitreversible Markov-Ketten gelten, hat es bei der Anwendung auf reguläre ungerichtete Graphen einen Vorteil gegenüber früheren Arbeiten: Es zeigt, dass, wenn man den spektralen Partitionierungsalgorithmus mit einem beliebigen Algorithmus ausführt erhält man immer noch die Ungleichung wobei der Rayleigh-Quotient des Vektors ist. Die Argumente von Alon, Milman, Sinclair und Jerrum erfordern einen tatsächlichen Eigenvektor. Dies ist relevant für schnelle spektrale Partitionierungsalgorithmen, die ungefähre Eigenvektoren verwenden. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda')}$$\lambda'$

Wann wird die algorithmische Signifikanz der obigen Ergebnisse als Graph-Partitionierungsalgorithmen zum ersten Mal erkannt? Die obigen Papiere haben keine solche Diskussion.

Es scheint, dass der erste Artikel, der diese Ideenmenge (unter Verwendung der algebraischen Invariante , des zweitkleinsten Eigenwerts des Laplace-Graphen, um verschiedene Eigenschaften des Graphen zu binden) mit der Graphentheorie vorstellte, Fiedlers "Algebraische Konnektivität von Graphen" in der tschechoslowakischen Mathematik war Tagebuch. Es erschien 1973, ungefähr zur gleichen Zeit wie die Zeitung von Cheeger (1970), die sich mit Mannigfaltigkeiten befasste. Ich bin mir nicht sicher, wer als Erster die Parallele zwischen Graphen und Mannigfaltigkeiten in dieser Hinsicht beobachtet hat. λ 2 wird manchmal als Fiedlerzahl bezeichnet.$\lambda_2$$\lambda_2$

Interessanterweise gibt es eine Bemerkung am Ende der Arbeit von Fiedler, die auf einen unabhängigen technischen Bericht von Anderson und Morley mit dem Titel Eigenwerte des Laplace auf einem Graphen von 1971 hinweist, der anscheinend ähnliche Ideen hatte. Die gleichnamige Arbeit von Anderson und Morley erschien jedoch erst 1985 in der linearen und multilinearen Algebra.

Einige zusätzliche Referenzen, an die ich mich erinnere:

1) Diaconis und Stroock, Geometrische Grenzen für Eigenwerte von Markov-Ketten, The Annals of Applied Probability, 1991; Aber ich erinnere mich, dass ich 1990 irgendwann einen Vorabdruck in die Hände bekommen habe

2) Dodziuk, Differenzgleichungen, isoperimetrische Ungleichung und Vergänglichkeit bestimmter Zufallsläufe, Transactions of the American Mathematical Society, 1984.

Auch ein wichtiger "algorithmischer Begleiter" für Sinclair und Jerrum war zu dieser Zeit

3) Dyer Frieze Kannan, ein zufälliger polynomieller Zeitalgorithmus zur Approximation des Volumens von konvexen Körpern, STOC 89. Natürlich wurden die Ergebnisse hier auf SJ aufgebaut.