OPUS


Volltext-Downloads (blau) und Frontdoor-Views (grau)

Betweenness Clusterung für schlichte, ungerichtete Graphen

  • 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.

Download full text files

Export metadata

Additional Services

Search Google Scholar

Statistics

frontdoor_oas
Metadaten
Author:Alrik Messner
URN:urn:nbn:de:bsz:mit1-opus-29417
Document Type:Bachelor Thesis
Language:German
Date of Publication (online):2013/06/26
Publishing Institution:Hochschule Mittweida
Release Date:2013/06/26
GND Keyword:Graphentheorie; Cluster-Analyse
Institutes:03 Mathematik / Naturwissenschaften / Informatik
DDC classes:510 Mathematik
Open Access:Frei zugänglich
Licence (German):License LogoUrheberrechtlich geschützt