Grundkonzepte der SNA

Question 1

Wege

Answer 1

„A walk is a sequence of nodes and lines, starting and ending with nodes, in which each node is incident with the lines following and preceding it in the sequence.“
[Wasserman & Faust, 1994]

• Ein Weg („walk“) ist eine Abfolge von Knoten, die durch Kanten verbunden sind.
• Die Reihenfolge der Knoten und Kanten ist beliebig; Knoten und Kanten dürfen auch mehrfach passiert werden.
• Die Länge eines Weges entspricht der Anzahl an Kanten entlang des Weges.

Question 2

Pfade

Answer 2

„A path is a walk in which all nodes and all lines are distinct.“ [Wasserman & Faust, 1994]

• Ein Pfad („path“) ist ein Spezialfall eines Weges.
• Alle Elemente (Knoten und Kanten) dürfen nur einmal passiert werden.
• Die Länge eines Pfades entspricht der Anzahl der Kanten entlang des Pfades.

Question 3

Zyklen

Answer 3

„A cycle is a closed walk of at least three nodes in which all lines are distinct, and all nodes except the beginning and ending node are distinct.“ [Wasserman & Faust, 1994]

• Ein Zyklus („cycle“) ist eine Spezialform eines Pfades.
• Start- und Endknoten sind identisch. Abgesehen davon dürfen keine Elemente mehrfach passiert werden.
• Ein Zyklus beinhaltet stets mindestens drei Knoten.
• Die Länge eines Zyklus entspricht der Anzahl seiner Kanten.

Question 4

Kürzeste Pfade & Durchmesser

Answer 4

„A shortest path between two nodes is referred to as a geodesic. […] The diameter of a connected graph is the length of the largest geodesic between any pair of nodes.“ [Wasserman & Faust, 1994]

• Der Abstand zwischen zwei Knoten entspricht der Länge des kürzesten Pfades („geodesic“) zwischen ihnen.
• Zwischen zwei Knoten kann es mehrere gleich lange (bzw. kurze) kürzeste Pfade geben.
• Die Länge des längsten kürzesten Pfades in einem Netzwerk wird als Durchmesser („diameter“) des Netzwerks bezeichnet.

Question 5

Bestimmung der Pfadlänge

Answer 5

• In kleineren und/oder wenig komplexen Netzwerken kann die Pfadlänge anhand der graphischen Darstellung bestimmt werden.
• In allen anderen Fällen hilft die Adjazenzmatrix.
• Die Bestimmung der Länge der kürzesten Pfade erfolgt dann mithilfe der Potenzen der Adjazenzmatrix.

Question 6

Aus Skriptum: Paths, Walks, and Cycles

Answer 6

Note that for the convention of setting gii = 0, g^2 = g x g tells us how many walks there are of length 2 between any two nodes.
The k’th power of the network, g^k, keeps track of all possible walks of length k between any two nodes, including walks with many cycles within them. Hence the use of the term walk rather than path.

Question 7

Grundidee

Answer 7

• In der Adjazenzmatrix 𝑔 ist festgehalten, ob zwei Knoten 𝑖 und 𝑗 miteinander
verbunden sind.
• Anders gesagt: Die Adjazenzmatrix 𝑔 zeigt an, ob eine direkte Verbindung zwischen den Knoten 𝑖 und Knoten 𝑗 existiert.
• Oder auch: Die erste Potenz 𝑔^1 der Adjazenzmatrix zeigt an, wie viele Wege der Länge 1 zwischen von Knoten 𝑖 zu Knoten 𝑗 existiert.
• Grundsätzlich gilt: Die 𝑘-te Potenz der Adjazenzmatrix 𝑔^𝑘 zeigt an, wie viele
Wege der Länge 𝑘 zwischen zwei Knoten existieren.
• Voraussetzungen:
• Das Netzwerk ist verbunden.
• Das Netzwerk ist ungewichtet.
• Für die Hauptdiagonalelemente gilt 𝑔𝑖𝑖 = 0.

Question 8

Intuitive Vorgehensweise

Answer 8

• Der kürzeste Pfad zwischen zwei Knoten ist immer auch der kürzeste Weg.
• Wenn man Schritt für Schritt überprüft, ob ein Weg der Länge 𝑘, 𝑘 + 1,… zwischen zwei Knoten existiert, stößt man früher auf den kürzesten Pfad zwischen allen Knotenpaaren.
• Es wird vorausgesetzt, dass alle Knotenpaare über mindestens einen Pfad miteinander verbunden sind (verbundenes Netzwerk).
• Die Berechnung ist dann abgeschlossen, wenn für alle Knotenpaare ein kürzester Pfad identifiziert wurde.