Structural Similarity of Vertices in Networks

Abstract

Unter einem Netzwerk verstehen wir einen Datensatz bestehend aus einer Menge von Objekten oder Individuen zusammen mit einer oder mehrerer Beziehungen zwischen diesen. Netzwerkanalyse umfasst Algorithmen, die solche Datensätze als Eingabe erhalten und hieraus Informationen über das gesamte Netzwerk oder einzelne Elemente daraus berechnen. Beispiele für solche Methoden sind etwa die Berechnung der Wichtigkeit oder Zentralität von Individuen oder das Auffinden dicht zusammenhängender Teilgraphen (Cluster) innerhalb eines Netzwerks. Diese Arbeit befasst sich mit struktureller Ähnlichkeit von Knoten in Netzwerken.Das Konzept von struktureller Ähnlichkeit in Netzwerken (oder auch struktureller Netzwerkpositionen) wird schon seit Jahrzehnten in der sozialen Netzwerkanalyse eingesetzt. Frühe Definitionen sahen zwei soziale Akteure als strukturell äquivalent an, wenn diese die gleichen Beziehungen zu den gleichen anderen Akteuren haben. Obwohl diese recht strikte Definition auf verschiedene Weise relaxiert wurde, sind bisherige Ansätze entweder ungeeignet für irreguläre Anwendungsdaten, oder sie operationalisieren nur eine sehr eingeschränkte Sicht von struktureller Ähnlichkeit, bei der etwa automorph äquivalente Knoten nicht zwingend als ähnlich erkannt werden können. Der Hauptbeitrag dieser Arbeit ist eine neue Formalisierung von struktureller Ähnlichkeit, die allgemein anwendbar und gleichzeitig robust gegenüber Irregularitäten ist.Nach einer systematischen Übersicht über bisherige Definitionen stellen wir unsere neue Formalisierung von struktureller Ähnlichkeit vor. Darüber hinaus zeigen wir anhand von ausführlichen Fallbeispielen wie strukturelle Ähnlichkeiten in der Analyse und Visualisierung von Anwendungsdaten eingesetzt werden können. Die erhaltenen Methoden sind effizient und lassen sich auf irreguläre, empirische Daten anwenden in denen Annahmen an die Netzwerkstruktur nur ungefähr erfüllt sind.