ASN
Netzwerk
Knoten 🏁
Kanten🏁
N (Knotenmenge des Netzwerkes), Einzelknoten (i,j)
Beziehung zwischen Knoten und Kanten= Verbindung🏁
Formen: Ähnlichkeit, soziale Beziehung, Interaktion, Ströme
NetzwerkTYPEN🏁
gerichtet: Beziehung besteht nur in eine Richtung
ungerichtet: das Verhältnis zwischen Knoten ist symmetrisch (Handelsbeziehung, Freundschaft)
gewichtet: zeigt die Stärke einer Beziehung an
Akteur-Ereignis-NW (two-Mode-NW): 2 Arten von Knoten sind vorhanden, Beziehungen bestehen nur zwischen Konten verschiedenen Typs.
Graph🏁 repräsentiert das NW formal, (N,g)
Matrix (Adjazenzmatrix): g, enthält die Beziehung zwischen den Knoten
Matrixelement (g i,j), bezeichnet die Beziehung zwischen zwei Knoten (i,j)
Loops: sind Selbstbezüge eines Knotens (werden in Matrix auf 0 gesetzt)
ungerichtetes NW: zwei Knoten sind verbunden: (g i,j)= 1
zwei Knoten sind nicht verbunden: (g i,j)= 0
Edgelist: enthält alle Kanten
besteht eine Verbindung zwischen zwei Knoten: ( ij E g)
Adjazenzliste: beinhaltet den Startknoten und alle Endknoten, zu denen eine Verbindung besteht
G (N): ist die Menge aller Kanten in einem NW
Isomorphe Netzwerke g´
Pfad:
Ein Pfad („path“) zwischen zwei Knoten 𝑖 und 𝑗 ist eine Abfolge von Kanten, die 𝑖 als Start- und 𝑗 als
Endknoten hat und bei der alle Zwischenknoten 𝑖1, i2,…,ik verschieden sind.
🚩Jeder Knoten darf nur einmal passiert werden
Weg:
In einem ungerichteten Netzwerk ist ein Weg („walk“) zwischen zwei Knoten 𝑖 und 𝑗 eine Abfolge von
Kanten, die 𝑖 als Start- und 𝑗 als Endknoten hat.
🚩 (i,j können mehrfach passiert werden)
Die Länge eines Pfades oder Weges entspricht der Anzahl der Kanten, die passiert werden. (k)
In einem ungerichteten Netzwerk ist ein Zyklus („cycle“) ein
Weg, der am selben Knoten beginnt und endet. Der Start- und
Endknoten wird dabei doppelt passiert, alle Zwischenknoten
sind jedoch verschieden.
Der kürzeste Pfad („geodesic“) zwischen zwei Knoten 𝑖 und 𝑗.
Das heißt, kein Pfad zwischen 𝑖 und 𝑗 hat weniger Kanten als
der kürzeste Pfad.
Power Law (Potenzgesetz):
Für Netzwerke mit 𝑔𝑖𝑖 = 0 kann man anhand der Adjazenzmatrix bestimmen, wie viele Wege der Länge 𝑘
zwischen zwei Knoten existieren. Die Matrix g2 = 𝑔𝑥𝑔 gibt an, wie viele Wege der Länge 𝑘 = 2 zwischen
zwei Knoten im Netzwerk bestehen, 𝑔3 die Anzahl der Wege mit Länge 𝑘 = 3 usw.
Die 𝑘-te Potenz der
Adjazenzmatrix ergibt die Anzahl der Wege der Länge 𝑘 zwischen zwei Knoten.
gerichtete NW:
Es gilt: Nur diejenigen Kanten werden für die Bestimmung von Wegen und Pfaden genutzt, die in die
„richtige“ Richtung fließen. Das heißt, wenn eine Kante von A nach B führt und keine Kante von B nach
A, wir aber einen Pfad von B nach A suchen, kommt diese Kante nicht für einen Weg oder Pfad in
Frage.
Komponenten (𝑁´, 𝑔´)
maximal verbundene Subgraphen eines NW
Teilmenge eines Netzwerks in der alle Knoten mit
Pfaden verbunden sind.
sagt z.B. etwas über die Verbundenheit im NW aus
Die Menge der Komponenten eines ungerichteten Netzwerks
(𝑁, 𝑔) wird als 𝐶(𝑁,𝑔) oder 𝐶(𝑔) bezeichnet, die Komponente, in
der ein konkreter Knoten 𝑖 eingebettet ist als 𝐶𝑖(𝑔).
Partition:
Ein Netzwerk kann auch die spezifische Partition
dargestellt werden, die durch die Komponenten
impliziert wird. Es wird demnach als die Menge aller
durch Pfade verbundenen Teilmengen dargestellt.
𝑁, 𝑔 = 2 , 1,3,4,5 , 6,10 , 7,8,9
Zentralitäten für Akteure C=centrality
(Nicht standardisiertes Maß für gleich große NW)
Prestige für Akteure
setzt gerichtetes NW voraus, Prestige hat, wer von vielen anderen Akteuren direkt oder indirekt gewählt wird (z.B. um Hilfe gebeten werden, Zitiert werden...)
Zentralitäten für ganze NW/Gruppen in NW
Closeness (C)🏁
Betweenness (B)🏁
Degree (D)🏁
Zentral ist der , der viele direkte Beziehungen hat,
von Akteuren (in ungerichteten NW)
zentral ist der der in vielen Beziehungen beteiligt und sichtbar ist
Grund: sie haben Zugang zu NW-Ressourcen, Kontrollmöglichkeiten, Informationen
Kap. 4, S. 45
Zentral ist der, der nur durch kurze Pfaddistanzen von allen anderen getrennt ist,
es werden auch indirekte Beziehungen erfasst,
indirekte Beziehungen sind schwächer als direkte
d. h. er ist selten auf Übermittlerdienste angewiesen, Informationen und Ressourcen kommen auf kurzem Weg an
zentral ist der, der für viele Paare im NW auf deren kürzesten Verbindungsstrecken liegt, d.h. er muss häufig als "Makler" benutzt werden, damit kann er viele Aktivitäten im NW kontrollieren
Brücke🚩
Eine Kante 𝑖𝑗 wird als Brücke bezeichnet, wenn das Netzwerk ohne diese Kante mehr
Komponenten aufweist als mit.
Ausschlaggebend ist, dass neue Komponenten entstehen – auch wenn das Netzwerk
vorher nicht zusammenhängend war.
lokale Brücke🚩
Eine Kante 𝑖𝑗 wir als lokale Brücke bezeichnet, wenn sich die Länge des kürzesten
Pfades zwischen zwei Knoten durch den Wegfall des Kante auf mehr als 2 verlängert.
Die Logik dahinter ist, dass zwei Knoten 𝑖 und 𝑗 durch die Kante 𝑖𝑗 direkt miteinander
verbunden sind, das heißt, die Länge des kürzesten Pfades beträgt 1. Nach Entfernen
der Kante bleiben die Knoten verbunden, doch der Pfad verlängert sich wesentlich.
Unter wesentlich verstehen wir, dass seine Länge größer 2 (anders gesagt, mindestens
3) beträgt – das bedeutet eine Verlängerung um mindestens 2.
schwach zusammenhängende Graphen🚩
wenn in einem gerichteten Graphen, die Richtung der Kanten im Netzwerk ignoriert wird,wird davon ausgegangen, dass zwei Knoten verbunden sind, sobald ein Pfad in einer Richtung zwischen ihnen besteht.
❗Die Unterscheidung zwischen stark und
schwach zusammenhängenden Graphen ist nur in gerichteten Netzwerken sinnvoll.
Richtung ignorieren❗
Die maximal zusammenhängenden Subgraphen eines Netzwerks, in dem jeder Knoten jeden anderen über einen gerichteten Pfad erreichen kann, zählen.
Tree🏁
Bei einem Tree ist das Netzwerk zusammenhängend; es besteht aus einer
einzigen Komponente, in denen alle Knoten direkt oder indirekt miteinander verbunden sind.
Forest🏁
Ein Forest liegt vor, wenn das Netzwerk aus mehreren Komponenten besteht, die alle eine Tree-Struktur
aufweisen.
Star🚩
In einem Sterngraph ist ein zentraler Knoten mit allen anderen Knoten durch Kanten verbunden, während die anderen Knoten neben diesem zentralen Knoten keine weiteren Nachbarn besitzen.
Der Akteur in der Mitte des Sterns weißt die höchste Zentralist auf.
ein sternförmiges NW weißt den höchsten Grad an Zentralität auf
Circle🏁
ist ein Kreis, wo jeder Knoten maximal 2 Nachbarn hat.
Complete NW🏁
alle möglichen Verbindungen sind vorhanden,
𝑔ij = 1 for all 𝑖 ≠ 𝑗.
Konzept der Nachbarschaft🏁
umfasst alle diejenigen Knoten, mit denen er verbunden ist.
Der interessierende Knoten (häufig auch Ego-Knoten genannt) ist ausgeschlossen. Die Nachbarschaft eines Knotens 𝑖 in 𝑔 wird als 𝑁𝑖(𝑔) notiert.
Die Nachbarschaft einer Knotenmenge 𝑆 ist die Vereinigungsmenge der Nachbarschaften
der Knoten in 𝑆, das heißt, alle Knoten, die mit mindestens einem der Knoten in 𝑆 verbunden sind.
Thema 3, S. 93
Konzept der erweiterten Nachbarschaft (Extended Neighbourhood)🏁
Das Konzept der erweiterten Nachbarschaft bezieht auch Knoten mit ein, die mit einem Knoten nur indirekt
verbunden sind. 𝑁𝑖
2(𝑔) beispielsweise ist die Menge aller Knoten, die mit Knoten 𝑖 über Pfade mit einer
Länge von höchstens 2 verbunden sind
Anmerkung zur Nachbarschaft in gerichteten Netzwerken: Es
zählen alle Knoten, die der Startknoten 𝑖 über gerichtete Pfade
erreichen kann (nicht: die Knoten, die 𝑖 erreichen können).
walk-connected🚩 Spezialfall der erw. NB:Ganz allgemein gesprochen ist die erweiterte Nachbarschaft (ohne Angabe der
Entfernung) die Menge aller Knoten, mit denen ein Knoten über Pfade verbunden ist. Mit
Angabe einer Pfaddistanz 𝑘 entsteht also ein Spezialfall der erweiterten Nachbarschaft.
Der Degree eines Knotens entspricht der Anzahl seiner
Verbindungen zu anderen Knoten. Der Degree
eines Knotens entspricht der Anzahl seiner Nachbarknoten. Die Degree-Zentralität berücksichtigt nur die direkten Verbindungen zu anderen Knoten.
𝑑 i (𝑔)
Die normalisierte Degree-Zentralität gibt
an, mit vielen der Knoten eines Netzwerks relativ gesehen in Verbindung steht. Ihr Wert liegt
zwischen 0 und 1 und entspricht dem Anteil der Knoten, mit denen ein Knoten direkt verbunden ist,
gemessen an der Gesamtzahl der Knoten im Netzwerk.
In-Degree❗
Die Anzahl der eingehenden Verbindungen eines Knotens (Kanten, die zu diesem
Knoten hinzeigen) wird als „In-Degree“ bezeichnet.
Out-Degree❗
Die Anzahl der von einem Knoten ausgehenden
Verbindungen (Kanten, die von ihm wegzeigen), ist der „Out-Degree“.
Dichte (Density)🏁
Die
Dichte gibt an, wieviel Prozent der Kanten, die in einem Netzwerk maximal vorhanden sein könnten, tatsächlich
vorliegen.
liegen viele oder wenige Beziehungen vor?
Degree-Verteilung🚩
zeigt an , wie sich die Kanten auf die Knoten verteilen und trifft eine deutlichere Aussage über die Struktur des NW als die Dichte #
reguläres NW🏁
Hier weisen alle Knoten denselben Degree 𝑘 auf. Das
heißt, die relative Häufigkeit des Degrees 𝑘 ist 1
ZufallsNW🏁
In Zufallsnetzwerken wird die Existenz einer Kante als Folge eines Zufallsprozesses betrachtet. In
unserem Fall unterstellen wir eine Poisson-Verteilung (die Poisson-Verteilung beschreibt die
Wahrscheinlichkeit des Eintretens eines Ereignisses – hier: das Vorliegen einer Kante – innerhalb
eines bestimmten Zeitraums).
skalenfreies NW🏁
Sie sind dadurch
gekennzeichnet, dass die Degree-Verteilung dem Potenzgesetz (einem sogenannten „power law“) folgt. In
diesen Netzwerken haben viele Akteure einen sehr niedrigen Degree (sprich: sehr wenige Nachbarn),
während einige wenige Knoten einen sehr hohen Degree haben.
Hubs🚩
stark verbundene Zentren eines NW werden als Hubs bezeichnet
Distanz🏁
Sie entspricht der Länge des kürzesten Pfades zwischen diesen Knoten, wobei die Länge eines
Pfades der Anzahl der Kanten entlang des Pfades entspricht.
Durchmesser🏁
Der Durchmesser eines Netzwerks lässt sich als die längste Distanz zwischen zwei Knoten im
Netzwerk beschreiben.
Von Bedeutung ist der längste Pfad, der zwischen zwei (beliebigen) Knoten feststellbar ist.
Umfang (girth & circumference)🏁
der Umfang eines NW kann für die Länge des kürzesten Zyklus‘ im Netzwerk („girth“)
oder auch des längsten Zyklus („circumference“) stehen.
Von der Pfadlänge abgeleitete Kennzahlen tragen zur strukturellen Charakterisierung von Netzwerken bei.
durchschnittliche Pfadlänge🏁
Die Closeness-Zentralität🏁
misst, wie nahe ein Knoten allen anderen Knoten im Netzwerk ist; sprich:
Wie schnell oder über wie viele Schritte er sie erreichen kann. Die Closeness-Zentralität misst, inwiefern ein Knoten unabhängig von anderen die übrigen Knoten im
Netzwerk erreichen kann,
Logischerweise basiert die Closeness-Zentralität auf der Distanz zwischen Knoten. Die Idee dahinter
ist: Je größer die Distanz zwischen zwei Knoten, desto größer ist ihr Abstand und desto stärker nimmt
der Bezug ab.
Der Wert der Closeness-Zentralität ist also maximal, wenn ein Knoten mit allen anderen
Knoten im Netzwerk direkt verbunden ist, und nimmt ab, je länger der Pfad zu anderen ist. Denken Sie
daran, dass der Pfad zwischen zwei nicht verbundenen Knoten eine unendliche Länge hat.
Decay-Zentralität🏁
Auch hier nimmt das Zentralitätsmaß
umso größere Werte an, je kürzer die Verbindungen eines Knotens zu allen anderen Knoten im Netzwerk
sind.
die Betweenness-Zentralität bewertet das Potenzial eines Knotens, die
Verbindung zwischen anderen zu kontrollieren. Hohe Werte der Betweenness-Zentralität zeigen an,
dass ein Knoten auf vielen kürzesten Pfaden zwischen anderen Knoten liegt. Unter der Annahme, dass
Akteure möglichst kurze Pfade zur Interaktion nutzen, gibt das einem Akteur die Möglichkeit, als
Vermittler oder auch Erpresser aufzutreten, der Ressourcen abzweigen oder abwandeln kann (z.B.
Informationen verfälschen, Geld einbehalten).
Eigenvector-Zentralität🏁
Die Grundidee der Eigenvektor-Zentralität besagt, dass die Zentralität eines Knotens proportional zur
Summe der Zentralitäten seiner Nachbarn ist.
Zentralisierung des Netzwerkes🏁
Die Zentralisierung eines Netzwerks beschreibt die Tendenz eines einzelnen Knotens im Netzwerk,
zentraler zu sein als alle übrigen Knoten. Man betrachtet also den Gegensatz zwischen Zentrum und
Peripherie eines Netzwerks, wobei ein Knoten im Zentrum wesentlich höhere Zentralitätswerte
aufweist als die Knoten in der Peripherie. Die hier vorgestellte Maßzahl bezieht sich auf die Idee eines
einzelnen zentralen Akteurs. Das Konzept kann jedoch auch auf Gruppen zentraler bzw. dezentraler
Knoten erweitert werden.
stark zusammenhängendes NW🚩
Ein Netzwerk, in dem jeder Knoten mit
jedem anderen über einen gerichteten Pfad verbunden ist, wird als stark zusammenhängend
bezeichnet.
nicht stark zusammenhängendes NW🚩
wenn ein Knoten von
allen anderen Knoten über einen gerichteten Pfad erreicht werden kann, selbst aber nicht alle anderen
erreichen kann, gilt das Netzwerk nicht als zusammenhängend.