Modifizieren des Top k Closeness Centrality Algorithmus von Bergamini
- Diese Arbeit handelt vom Modifizieren des Top k Closeness Centrality Algorithmus von Bergamini. Aufbauend auf den vorhandenen Forschungen des ursprünglichen Papers von Bergamini wurde untersucht in welchen Fällen die zwei Heuristiken BFSCut und BFSBound angewendet werden sollten. In der Einleitung wird dieser Algorithmus mit seinen Heuristiken, wie auch alle komplexeren Konzepte kurz erklärt. Zu den Untersuchungen werden eine Vielzahl von Graph-Generatoren erangezogen, die mit verschiedenen Parametern initialisiert und genutzt werden,
um die Laufzeiten der beiden Heuristiken zu messen.
Es wird in dieser Arbeit auch ein neuer Algorithmus beschrieben, der Netze eines bestimmten Mindestdurchmessers erzeugt und auch zur Laufzeitanalyse eingesetzt wird. Ebenso werden andere Anwendungsfelder und Verbesserungen dieses Generators angedacht. Danach werden Arten der Evaluierung des Graphen beschrieben und bewertet. Schließlich wird eine statische Voranalyse des Graphen beschrieben und getestet.
Alle diese Daten werden mit einem hohen wissenschaftlichen Standard gesammelt und in übersichtlichen Grafiken visualisiert. Am Ende werden die Ergebnisse dieser Arbeit noch zusammengefasst und in einen Kontext gesetzt. Diese Arbeit zielt nicht darauf ab, den grundlegenden Algorithmus oder die Heuristiken von Bergamini zu verändern, sondern den Algorithmus in verschiedenen Szenarien zu beurteilen und daraus eine analytische Strategie zu entwickeln, die ihn wesentlich benutzerfreundlicher macht. Somit soll die Voranalyse der meisten Graphen wegfallen bzw. auch bei der manuellen Wahl der Heuristik wichtige Anhaltspunkte zum Laufzeitverhalten geliefert werden.