Social Network Analysis. Methoden zur Analyse von Sozialen Netzwerken

Inhaltsverzeichnis

Kapitel 1 Einleitung

Kapitel 2 Social Networks
2.1 Begriff
2.2 Datenerhebung und Datensammlung für SNA

Kapitel 3 Modellierung
3.1 Visualisierung
3.2 Metriken
3.3 Centrality
3.3.1 Degree Centrality
3.3.2 Closeness Centrality
3.3.3 Betweenness Centrality
3.3.4 Eigenvector Centrality

Kapitel 4 Gruppenidentifikation
4.1 Allgemeines
4.2 Link Removal/Girvan-Newman Algorithmus
4.3 Graph Partitioning/Spectral Clustering
4.4 Anwendungsbereiche

Kapitel 5 Link Mining & Anwendungen
5.1 Object-related Tasks
5.1.1 Link-based Object Ranking
5.1.2 Link-based Object Classification
5.1.3 Object Identification
5.2 Link-based Tasks
5.2.1 Link Prediction
5.3 Graph-related Tasks
5.3.1 Subgraph Discovery
5.3.2 Graph Classification

Kapitel 6 Zusammenfassung und Ausblick

Abbildungsverzeichnis

Literaturverzeichnis

Kurzfassung

Im Zeitalter von Web 2.0 ist die Integration der Nutzer für die Gestaltung des World Wide Webs so wichtig wie noch nie. Vor allem Soziale Netzwerke nehmen dort eine zentrale Rolle ein. Deshalb ist die Analyse dieser Netzwerke zu einem interessanten Forschungsgebiet geworden. Im Verlauf der Arbeit werden Ansätze zur Visualisierung vorgestellt, die das Fundament für die Erhaltung von Messwerten bilden. Diese Metriken erlauben es die sozialen Netzwerke zu charakterisieren, was anhand von Beispielen veranschaulicht wird. Insbesondere werden hierbei verschiedene Zentralitätskennzahlen erläutert. Da Gruppen in Netzwerken von besonderer Bedeutung sind, ist es eine der Aufgaben der Netzwerkanalyse diese zu identifizieren. Dafür werden zwei Algorithmen aus dem Bereich der Gruppenidentifikation vorgestellt. Abschließend werden noch grundlegende Methoden aus dem Gebiet des Link Minings beschrieben und mit Anwendungen ergänzt.

Abstract

In the age of WEB 2.0, the integration of the user for formation of the world-wide-web is more important than ever before. At the top, social networks take up a central role. Therefore, the analysis of these networks has become an interesting field of research. During the course of the studies, approaches to visualization are imagined, that shape the base for the collection of data logging. These results make it possible to characterize the social networks, which by means of the examples are exemplified. In particular, while doing this different identification numbers are given. As groups in networks have particular importance, it is one of the tasks of the network analysis to identify these groups. For this, two algorithms from the area of the group identifications are conceived. Finally, fundamental methods from the area of Link Mining are described and completed with applications.

Kapitel 1 Einleitung

Soziale Netzwerke sind in der heutigen Zeit aus dem Alltag nicht mehr wegzudenken. Alleine die Plattform Facebook ist mit ungefähr 800 Millionen Nutzern weltweit ein fester Bestandteil des World Wide Webs. Die rasche Entwicklung und Verbreitung der Netzwerke machen es zu einem interessanten Forschungsgebiet für deren Analyse. In dieser Arbeit werden daher grundlegende Ansätze und Methoden vorgestellt, die für eine Charakterisierung herangezogen werden. Dabei werden sowohl Techniken für die Analyse einzelner Einheiten und deren Verbindungen, als auch für die Gruppen und die gesamte Netzwerkstruktur erläutert.

Im zweiten Kapitel werden zunächst grundlegende Informationen über soziale Netzwerke gegeben. Im Einzelnen wird dabei der Begriff definiert und ein Überblick über die aktuelle Situation und die Bedeutung des Themas gegeben. Im weiteren Verlauf wird geklärt woher die Daten in einem sozialen Netzwerk stammen, wie diese extrahiert und für die Analyse verwendet werden können.

Kapitel 3 behandelt die Modellierung der Netzwerke. Dabei werden Notationen beschrieben und verschiedene Darstellungsformen für soziale Netzwerke vorgestellt. Dieser Teilbereich fällt unter den Begriff der Visualisierung. Des Weiteren werden Metriken erläutert, die insbesondere die Zentralität eines Akteurs messen. Im Fokus der Betrachtung stehen vier verschiedene Zentralitätsmetriken, welche zum besseren Verständnis durch Anwendungsbeispiele veranschaulicht werden. Im genauen sind das die Kennzahlen des Degrees, der Closeness, der Betweenness und des Eigenvektors.

Im vierten Abschnitt der Arbeit wird ein Überblick über die Gruppenidentifikation gegeben. Hierbei wird zuerst auf die allgemeine Wichtigkeit für die Analyse hingewiesen und anschließend verschiedene Ansätze der Identifikation beschrieben. Im genauen werden zwei Algorithmen, die auf unterschiedlichen Herangehensweisen basieren. Zum einen ist das eine Link-Removal Methode, wobei als Anwendung der Girvan-Newman Algorithmus erläutert wird und eine Methode aus dem Bereich Graph Partitioning mit einer Technik, die Spectral Clustering genannt wird.

Das fünfte Kapitel behandelt das Aufgabenfeld des Link Minings, was ein Teilbereich des Data Minings ist. Dabei werden Objekt-basierte, Link-basierte und Graphen-basierte Ansätze vorgestellt, deren Aufgaben beschrieben und mit Anwendungen und Methoden ergänzt.

Kapitel 6 bildet mit dem Resümee sogleich den Abschluss der Arbeit.

Kapitel 2 Social Networks

2.1 Begriff

Soziale Netzwerke (engl, social networks) sind Beziehungsgeflechte, die Menschen und Organisationen mit anderen Menschen und Organisationen verbinden, Die Verbindungen bestehen aus den Beziehungen zwischen den Einheiten, Diese können unterschiedlicher Natur sein, wie Freundschaften, Verwandtschaften, Geschäftsbeziehungen, aber auch Interessengleichheiten können Anlass für eine Verbindung sein, Auf Basis der vorhandenen Beziehungen kommunizieren die Einheiten, in Form von Wissens- und Kommunikationsaustausch. (vgl, [KarlO])

Die Kommunikation zwischen den Einheiten ist eine, bzw, die zentrale Funktion eines sozialen Netzwerks, Bei symmetrischen Netzwerken, die typisch bei Facebook sind, gilt eine aktive Anforderung und Bestätigung der Freundschaft zwischen zwei Einheiten als Voraussetzung, Erst dann können private Nachrichten untereinander versendet, veröffentlichte Fotos eingesehen und kommentiert und Einträge an die Pinnwand geschrieben werden, Um sich in dem sozialen Netzwerk identifizieren zu können, wird fürjede Einheit ein Profil angelegt, welches alle Informationen beinhalten soll, die für die erfolgreiche Integration in das Netzwerk notwendig sind, Typische Merkmale, die man über sich selbst in primären, bzw, persönlichen Netzwerken veröffentlichen kann, sind unter anderem der eigene Name oder Name der Organisation, Alter, Interessen und Beruf, Diese Liste kann beliebig erweitert werden, je nach Anforderung des sozialen Netzwerks, Der Nutzer kann dennoch frei wählen, welche Informationen er von sich preisgibt Die gesammelten Informationen bilden die Basis dafür, in welchen Bereich sich das soziale Netzwerk segmentiert, Die Anwendungsbereiche gehen weit auseinander, Plattformen für Schüler und Studenten im deutschsprachigen Raum sind vor allem SchülerVZ bzw, StudiVZ, Für Geschäftspartner bietet Xing geeignete Funktionen und Informationen, um sich miteinander zu vernetzen, Das Internet stellt unzählige Möglichkeiten zur Verfügung, sodass jeder den eigenen Content verteilen und mit anderen Personen und Institutionen kommunizieren kann, (vgl, [Kup2O l O])

2.2 Datenerhebung und Datensammlung für SNA

Die Daten spielen eine zentrale Rolle in sozialen Netzwerken, Die erstellten Profile sollen möglichst genaue Abbildungen der Personen sein, die sie repräsentieren, Gleich zu Beginn, wenn ein neuer Account angelegt wird, wird der Benutzer aufgefordert einige Daten über sich preiszugeben, In der Regel sind das grundlegende Daten wie Geburtsdatum, Name und die E- Mail-Adresse. Die spezifischen Formulare sind an das jeweilige Netzwerk angepasst. Die Kategorie bzw. das Interessengebiet des sozialen Netzwerks ist dafür ausschlaggebend. So werden Gruppierungen, deren Interesse bei Videospielen liegt eventuell Angaben verlangen über die aktuellen Favoriten der Nutzer. Eine Accounterstellung erfordert in der Regel nur wenige Klicks und Angaben, sodass der Benutzer unkompliziert der Gemeinschaft beitreten kann. Die untere Abbildung zeigt das Registrierungsformular für das soziale Netzwerk Facebook.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1 Facebook Registrierung Quelle: [Facll]

Zu Beginn werden nur die nötigsten Daten erfasst. Im weiteren Verlauf, insbesondere bei der Nutzung, wird der Nutzer allmählich mehr Informationen über sich preisgeben. Prinzipiell wird zwischen Daten unterschieden, die der Nutzer bewusst preisgibt und die aus seiner Sicht unbewusst erfasst werden. Dazu gehören insbesondere Logfiles und Nachrichten, die gespeichert werden. Das Hauptproblem bei der Datenerfassung ist vor allem, dass die Daten ungenau oder sogar falsch sind. Da diese jedoch die Grundlage für die Analyse bilden, kann dies die Qualität der Analyse erheblich beeinträchtigen.

Durch die starke Popularität der sozialen Netzwerke steigt auch das Interesse der Wissenschaftler für deren Untersuchung. Vor allem weil in der heutigen Zeit die Kommunikation über das Internet günstiger und einfacher geworden ist. Das Verstehen der Netzwerke, deren Entwicklung und Design sind die zentralen Fragen, wenn es um die Analyse geht. Aus den Informationen und Daten in den Netzwerken lassen sich durch verschiedene Methoden Vorhersagen modellieren, mit denen dann weitere Annahmen getroffen werden können. Das Ziel der Analyse von sozialen Netzwerken ist es deshalb diese Prozesse und Strukturen zu optimieren und die Effizienz zu steigern. Die Schnittstellen um die Daten zu extrahieren werden teilweise von den Anbietern selbst zu Verfügung gestellt, jedoch gibt es auch Werkzeuge von Dritten, die dies ermöglichen. Diese bieten unter anderem Funktionen wie die Visualisierung des Netzwerkes. So können die Zusammenhänge zwischen den Knoten einfach dargestellt und untersucht werden. Des Weiteren kann man dies zum Beispiel für eine einzige Person anwenden, sodass dessen Verbund in das Netzwerk untersucht werden kann. Vor allem wenn die vorhergegangenen Ergebnisse der Analysen Hinweise gegeben haben, dass diese Einheit eine besondere Funktion, Stellung oder Macht besitzt. (vgl. [FGPO08])

Eines der Tools ist das TellUsWho. Es erlaubt die Zusammenstellung von detaillierten Informationen aus einer größeren Menge von Individuen innerhalb einer kurzen Zeitspanne, woraus dann für einzelne Benutzer die sozialen Kontakte visualisiert werden. (vgl. [RSGJ10])

Im nächsten Kapitel werden die Modellierung, sowie die Visualisierung von sozialen Netzwerken weiter im Detail behandelt.

Kapitel 3 Modellierung

3.1 Visualisierung

Soziale Netzwerke sind komplexe Systeme, deren Strukturen sehr abstrakt sind. Deshalb werden einfache formale Graphen zur Repräsentation erstellt. Der Aufbau dieser Graphen ist unabhängig von der Art des Netzwerkes, so können die Anwendungen und Algorithmen zur Analyse gleichermaßen auf unterschiedliche Netzwerke angewendet werden. Unterschieden wird zwischen Knoten, die die Einheiten im Netzwerk darstellen, und Kanten, welche die Verbindungen zwischen den Einheiten darstellen. (vgl. [Pfe08])

Wie zuvor erwähnt stellen die Knoten die Einheiten dar, welche Personen und Organisationen sein können. Je nach Anwendung können die Knoten in ihrer Größe und Farbe unterschieden werden. Auch bei den Verbindungen werden Unterscheidungsmerkmale wie Länge und Dicke eingesetzt, sodass eine visualisierte Differenzierung einfacher ist. Diese werden gewichtete Kanten genannt. Typischerweise werden solche Datenmodelle bzw. Graphen als Grundmenge G = (V,E) bezeichnet, mit den Teilmengen Vertices V, zu Deutsch Eckpunkte, und Edges E, zu Deutsch Kanten. (vgl. [Bra08])

Die Kanten werden zwischen symmetrischen und asymmetrischen Verbindungen unterschieden, um die Informationsrichtung darzustellen. In einem sozialen Netzwerk können ohne weiteres beide Arten vorkommen. Gerichtete Beziehungen, wie sie in Abbildung 2(links) zu sehen sind, werden mit Pfeilen dargestellt. Ungerichtete Beziehungen werden im Gegensatz dazu als Linie visualisiert. Um die Intensität einer Verbindung zu veranschaulichen, wird die Stärke der Linie, bei zunehmender Intensität erhöht (Abbildung 2, rechts). (vgl. [Pfe08])

Abbildung in dieser Leseprobe nicht enthalten

Die Graphentheorie dient jedoch nicht nur zur Darstellung, sondern sie erleichtert auch das Erforschen sozialer Netzwerke im Bereich der Analyse. Deshalb sollten nur die Informationen abgebildet werden, die fur die gewünschte Analyse nötig ist. Es lässt sich kein universal ersetzbares Modell identifizieren. In der Regel sind soziale Netzwerke sehr groß, weshalb eine Zerlegung in Gruppen sinnvoll ist, um eine effektive Analyse durchzuführen. (vgl. [Bra08])

Ein Graph G hat eine Menge von Knoten V und eine Menge von Kanten E, so werden Teilgruppen GT als solche definiert, wenn die Teilmenge ET von E alle Verbindungen beinhaltet, die zwischen den Knoten der Teilgruppe VT, als Teilmenge von V, liegen. Die resultierenden Teilgruppen werden nicht zufällig gewählt, sie charakterisieren sich durch eine relativ starke Verbundenheit zwischen den Akteuren, die sich in diesen befinden. Unterschieden wird hierbei zwischen zwei Bereichen. Zum einen kann eine Teilgruppe als solche definiert werden, wenn die Einheiten nahe beieinander liegen und zum anderen, wenn innerhalb sehr viele direkte Beziehungen existieren. Solche Teilgruppen werden aufgrund ihrer starken Verbundenheit auch kohäsive Teilgruppen genannt. Um unterscheiden zu können, was Teilgraphen sind und was nicht, wird anhand des folgenden Beispiels (Abbildung 3) verdeutlicht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3 Graph und Teilgraphen Quelle: [THS05]

Der Graph (a) bildet eine Gruppe von vier Knoten und deren Beziehungen in vier Kanten. Wir erinnern uns, dass Teilmengen als solche definiert werden, wenn die Knoten und Kanten des Subgraphen Teilmengen der Knoten und Kanten eines anderen Graphen sind. Aufgrund dieser Erkenntnis lässt sich nun schließen, dass die Graphen (b) und (c) Teilgruppen von (a) sind. Des Weiteren lässt sich ableiten, dass (d) keine Teilgruppe ist, aufgrund einer in (a) nicht existierenden Verbindung zwischen den Knotenpunkten Dd und Ad. Folglich ist (e) auch keine Teilgruppe von (a), weil der in (e) vorhandene Knoten Ee nicht Teil der Menge von Knoten in(a) ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4 Nicht-Teilgraph Quelle: [THS05]

Abbildung 4 (f) stellt keinen Graphen dar, weil der Knotenpunkt C eine Verbindung hat, die nicht Teilmenge der Verbindungen von (f) ist. Demnach ist (f) auch keine Teilgruppe von (a). Zusammenfassend lässt sich sagen, dass Teilgraphen nicht alle Verbindungen zwischen den Knotenpunkten eines Graphen G aufweisen müssen, jedoch dürfen sie keine enthalten, die nicht in G existieren. Weitere Knoten und deren Verbindungen können ebenfalls entfernt werden, ohne dass die Eigenschaft verloren geht um sie als Teilgraphen zu definieren.

Um Teilgraphen zu definieren besitzen sie noch weitere Eigenschaften. Die Vollständigkeit beschreibt den Verbindungsgrad innerhalb eines Graphen. In absolut vollständigen Graphen ist jeder Knoten mit allen anderen Knoten in demselben Graphen verbunden. Ein weiterer wichtiger Punkt sind die knotengenerierten Teilgraphen, welche die Eigenschaft besitzen, dassjeder Knoten eines Teilgraphen alle Kanten zu anderen Knoten des gleichen Teilgraphen besitzen muss, die auch im Basisgraphen existieren. Das Maximum einer Eigenschaft ist dann erreicht, wenn das Hinzufügen von Knoten oder Kanten den Verlust der Eigenschaft zur Folge hat. (vgl. [THS05])

Wichtige Vertreter im Bereich der Teilgruppen sind die Cliquen. Sie charakterisieren sich durch ihre maximale Vollständigkeit und bestehen aus mindestens drei Knoten. Wir erinnern uns, dass jeder Knoten innerhalb einer Clique mit allen anderen Knoten über eine Kante direkt verbunden sein muss. Die Einschränkung, dass eine Clique aus mindestens drei Einheiten besteht wurde bewusst gewählt, weil sonst jedes Knotenpaar, das miteinander verbunden ist als Clique zu definieren wäre. Die genau vorgegebenen Eigenschaften wirken sich stark auf deren Größe aus, weshalb die Cliquen eher klein bleiben. Mit steigender Anzahl der Knoten, erhöht sich auch die Anzahl der Kanten in einem Graphen. Einzelne Einheiten eines sozialen Netzwerks können Teil mehrerer Cliquen sein. Abbildung 5 zeigt einen einfachen Graphen G in dem verschiedene Cliquen C existieren.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5 Graph mit Cliquen Quelle: [WF94]

Es ist leicht zu erkennen, dass dieser Graph drei Cliquen beinhaltet. Somit gilt G = {C¡,C2,C3} und Ci = {V1,V2,V3}, C2 = {Vi,V3,V5}, C3 = {V3,V4,V5, Ve}- Man sieht, dass Knoten teilweise in mehreren Cliquen sind, denn Ci П C2 = {i,3}, C2 П C3 = {3}, C3 П Ci = {3,5}- Es existieren auch weniger strenge Ansätze zur Cliquenbildung. So sind n-Cliquen nicht an die Vorgabe gebunden, dass jeder Knoten direkt mit allen anderen Knoten verbunden sein muss, sondern haben die Freiheit über n-Verbindungen miteinander in Beziehung zu stehen. So wäre in Abbildung 5 {2,3,4,7} eine 2-Clique. Die grafische Aufbereitung wird in der Regel mit Softwareunterstützung durchgeführt. Matrizen, die die Informationen über die einzelnen Verbindungen zwischen den Knoten beinhalten, werden eingelesen und optisch dargestellt. Ein beliebtes Tool dafür ist UCINET 6, welches soziale Netzwerke darstellen kann und netzwerkanalytische Methoden für die Messung der Centrality, Aufdeckung von Gruppen und Permutations-basierende statistische Analysen bereitstellt. (vgl. [WF94]) Das Programm liest die Daten in Form einer Adjazenzmatrix ein, um daraus den Graphen abzubilden. Eine Adjazenzmatrix ist eine n x n Matrix, die die Verbindungen zwischen den Akteuren abbildet. Der Wert des Schnittpunktes von der vertikalen zur horizontalen Linie zeigt, ob eine Verbindung besteht, oder nicht. Wenn es keine Beziehung zwischen den Akteuren gibt, dann wird dies mit einer 0 dargestellt. Die Diagonale ist klassischer Weise eine Reihe von Nullen, da ein Akteur im Normalfall nicht mit sich selbst verbunden sein kann. In ungewichteten Netzwerken ist eine Verbindung mit dem Wert 1 festgelegt, wobei eine gewichtete Verbindung auch mit einem höheren Wert versehen werden kann. Dies ist der Fall, wenn es Unterscheidungen in der Verbindungsstärke gibt. Beispielsweise ist eine Verwandtschaft in der Regel eine stärkere Verbindung, als die zu einer Person, die man nur flüchtig kennt. Des Weiteren entspricht in symmetrischen Netzwerken die transponierte Adjazenzmatrix der der ursprünglichen Adjazenzmatrix.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6 Adjazenzmatrix fur Graph aus Abbildung 5

Abbildung 6 zeigt eine Adjazenzmatrix fur den Graphen aus Abbildung 5. (vgl. [LFH10])

Die Visualisierung von sozialen Netzwerken ist ein Basiselement im Bereich der Netzwerkanalyse. Die erstellten Modelle dienen als Lieferanten fur Kennzahlen, mit denen Messungen durchgeführt werden.

3.2 Metriken

Der Einfluss der Personen und Organisationen in sozialen Netzwerken auf andere Einheiten hängt von vielen Faktoren ab. Das Ermitteln von Metriken, auf deren Basis Netzwerkanalysen durchgeführt werden, ist ein zentraler Punkt in der Netzwerkforschung. Die Messwerte charakterisieren und individualisieren ein soziales Netzwerk. Dabei wird nicht nur das Netzwerk als gesamtes System betrachtet, sondern auch die quantitativen und qualitativen Aspekte der einzelnen Knoten und Kanten mit berücksichtigt. (vgl. [Agg11])

Es gibt verschiedene Ansatzpunkte für eine Analyse. So kann man das Netzwerk als Gesamtes untersuchen, wobei besonderes Augenmerk auf Eigenschaften wie Größe, und Dichte gelegt wird. Des Weiteren sind die Kanten und Knoten häufig untersuchte Objekte in der Netzwerkanalyse. (vgl. [XZL10])

Im weiteren Verlauf wird auf einige Metriken eingegangen, um eine Basis für die Netzwerkanalyse zu schaffen. Konkret handelt es sich dabei um Metriken aus dem Bereich der Centrality, welche die Zentralität eines Knotens messen.

3.3 Centrality

Die Centrality fasst die wichtigsten Metriken zusammen, die zur Analyse von Knoten und Kanten herangezogen werden. Sie sind wichtig um Schlüsselfiguren in sozialen Netzwerken zu identifizieren. Es gibt unterschiedliche Meinungen darüber, wann eine Person bzw. Organisation von zentraler Bedeutung für das soziale Netzwerk ist und wann nicht. Deshalb werden im Folgenden die vier wichtigsten Messzahlen vorgestellt und diese anhand von Beispielen veranschaulicht. Zuerstjedoch sollten einige Basisbezeichnungen erläutert werden. Die Anzahl der Knoten wird mit N deklariert, die momentan betrachtete Person bzw. Organisation ist standardmäßig i und die Benutzer, die mit dieser interagieren, werden alsy bezeichnet. (vgl. [VEL10])

[...]