Identifikation von Clustern in Graphen

Abstract

Algorithm Engineering für Graphclustern beinhaltet mehr als die Entwicklung gut funktionierender Algorithmen für konkrete Anwendungen oder Datensätze. Es geht vielmehr um den systematischen Entwurf von Algorithmen für formal sauber gefasste Probleme und deren Analyse und Evaluation unter Betrachtung angemessener Qualitätsmaße. Die Wahl eines Qualitätsmaßes und eine dementsprechend saubere Formulierung eines Optimierungsproblems ist bereits für das intuitiv nahe liegende Paradigma eines starken Zusammenhangs innerhalb der Cluster gegenüber einem schwachen Zusammenhang zwischen den Clustern eine Herausforderung. Umso bedeutender ist der Erkenntnisgewinn, der aus der Methodik des Algorithm Engineering für Graphclustern erzielt werden kann. Viele Aspekte, die in diesem Artikel nur kurz angerissen werden, sind in der Arbeit [9] ausführlich beschrieben.