In dieser Dissertation wird der Entwurf von schnellen und parameterfreien Graphen-Clustering-Methoden beschrieben, die robuste Clusterzuordnungen bestimmen können. Die Dissertation bietet eine Spektralanalyse sowie Algorithmen, die die erhaltenen theoretischen Ergebnisse an die Implementierung robuster Graphen-Clustering-Techniken anpassen.

Ein erster Beitrag dieser Arbeit ist die Definition eines spärlichen Graphenmodells, das mit den Zielen des Graphenclustering vereinbar ist. Dieses Modell basiert auf einer vorteilhaften Eigenschaft, die sich aus einer blockdiagonalen Darstellung einer Matrix ergibt, die die Dichte der Verbindungen innerhalb von Clustern und die Spärlichkeit der Verbindungen zwischen ihnen fördert. Es wird eine Spektralanalyse des spärlichen Graphenmodells einschließlich der Eigenwertzerlegung der Laplace-Matrix durchgeführt. Die Analyse der Laplace-Matrix wird durch die Definition eines Vektors vereinfacht, der alle relevanten Informationen enthält, die in der Laplace-Matrix enthalten sind. Die gewonnenen spektralen Eigenschaften spärlicher Graphen werden auf der Grundlage von zwei Methoden, die die Bestimmung des Spärlichkeitsniveaus als Annäherungen an die spektralen Eigenschaften der spärlichen Graphenmodelle formulieren, an das Clustering angepasst.

Ein zweiter Beitrag dieser Arbeit besteht darin, die Auswirkungen von Ausreißern auf das Graphenclustering zu analysieren und Algorithmen vorzuschlagen, die die Robustheit und den Grad der Spärlichkeit gemeinsam berücksichtigen. Die Grundlage für diesen Beitrag ist die Spezifizierung grundlegender Ausreißertypen, die in Fällen extremer Spärlichkeit auftreten, und die mathematische Analyse ihrer Auswirkungen auf dünn besetzte Graphen, um Algorithmen für das Graphenclustering zu entwickeln, die gegenüber den untersuchten Ausreißereffekten robust sind. Basierend auf den erhaltenen Ergebnissen werden zwei verschiedene robuste und spärlichkeitsbasierte Methoden zur Konstruktion von Affinitätsmatrizen vorgeschlagen. Motiviert durch die Auswirkungen von Ausreißern auf Eigenvektoren, werden eine robuste Fiedler-Vektor-Schätzung und eine robuste spektrale Clustermethode vorgeschlagen. Desweiteren wird ein Algorithmus zur Erkennung von Ausreißern, der auf dem Vertex-Grad aufbaut, vorgeschlagen und auf die Ganganalyse angewendet.

Die Ergebnisse dieser Arbeit zeigen, wie wichtig es ist, die Robustheit und den Grad der Spärlichkeit von Graphen Clustering-Algorithmen gemeinsam zu berücksichtigen. Darüber hinaus liefert die vereinfachte Laplace-Matrix Analyse vielversprechende Ergebnisse für die Entwicklung von Graphenkonstruktionsmethoden, die durch die Optimierung in einem Vektorraum, anstelle des normalerweise verwendeten Matrixraums, effizient berechnet werden können.