TY  - THES
U1  - Bachelor Thesis
A1  - Messner, Alrik
T1  - Betweenness Clusterung für schlichte, ungerichtete Graphen
N2  - Es ist möglich, Graphen und Netzwerke durch Bewertung der Kanten mit Hilfe des Zentralitätsindizes Betweenness in Cluster zu zerlegen. Die Berechnung der Betweennesswerte für jede Kante eines betrachteten Graphen benötigt eine Zeit von O(n2m) für m >> n. In dieser Arbeit wird eine schnellere Methode mit einer Zeitkomplexität von O(nm) für die Berechnung eines Betweenness Rankings nach Newman und unabhängig nach Brandes vorgestellt und implementiert. Es wird ein Clusteralgorithmus nach Newman und Girvan auf Basis des Index Kanten-Betweenness und mit einer Laufzeit von O(nm2) vorgestellt und es werden verschiedene Graphen damit geclustert. Die Arbeit ist restringiert auf schlichte, ungerichtete Graphen.
KW  - Graphentheorie
KW  - Cluster-Analyse
Y2  - 2012
U6  - https://nbn-resolving.org/urn:nbn:de:bsz:mit1-opus-29417
UN  - https://nbn-resolving.org/urn:nbn:de:bsz:mit1-opus-29417
ER  -