Ein auf Kommunikationserkennung basierendes Zentralitätsproblem
18.02.2011Bei Zentralitätsproblemen wird eine Menge von Knoten eines Graphen gesucht, die - als Gruppe - möglichst zentral gelegen ist. Martin Fink stellt auf der Konferenz WALCOM'11 Algorithmen und weitere Ergebnisse zu dem Zentralitätsproblem "Maximum Betweenness Centrality" vor, das er gemeinsam mit Joachim Spoerhase untersucht hat.
Bei diesem Problem geht es darum, in einem Graphen, in dem den Knoten verschiedene Kosten zugeordnet sind, unter Einhaltung eines Budgets eine Gruppe von Knoten zu finden, die die Wahrscheinlichkeit maximiert, Kommunikation zu entdecken. Die Wahrscheinlichkeit, Kommunikation zu entdecken, ist dabei die Wahrscheinlichkeit, dass mindestens einer der Knoten auf einem zufällig gewählten kürzesten Weg zwischen einem zufällig gewählten Paar von Knoten liegt.
Bisher war lediglich die Einheitskostenversion des Problems untersucht worden, die schon NP-vollständig ist. Für diese Version gab es auch schon einen (1-1/e)-Approximationsalgorithmus (Dolev et al., 09). Martin Fink und Joachim Spoerhase entwickelten einen Algorithmus, der auch das allgemeine Problem mit einem Faktor von 1-1/e approximiert und zeigten, dass die Abschätzung der Approximationsgüte beider Algorithmen bestmöglich ist. Zudem konnten sie beweisen, dass für dieses Problem kein Polynomialzeitapproximationsschema existiert, also in Polynomialzeit keine beliebig gute Lösung gefunden werden kann. Schließlich gaben sie noch einen Polynomialzeitalgorithmus an, der das Problem Maximum Betweenness Centrality auf Baumgraphen optimal löst.
Weitere Informationen liefern der Konferenzartikel und die Vortragsfolien.
