Degree & Dichte

Question 1

Degree

Answer 1

Der Degree eines Knotens entspricht der Anzahl seiner Kanten. Er entspricht also der Größe der Nachbarschaft eines Knotens bzw. der Anzahl seiner Nachbarn:
𝑑𝑖(𝑔) = #{𝑗: 𝑔𝑖j = 1} = #𝑁𝑖(𝑔)

• Der Degree eines Knotens kann auf Basis der graphischen Darstellung durch Abzählen bestimmt werden.
• Alternativ kann er auch durch die Multiplikation der Adjazenzmatrix mit einem Einsenvektor berechnet werden.

Question 2

Bestimmung des Knotendegrees

Answer 2

• Durch Abzählen

* Mithilfe der Adjazenzmatrix

Question 3

Bestimmung des Knotendegrees - Besonderheiten in gerichteten Netzwerken

Answer 3

In gerichteten Netzwerken wird zwischen dem In- und dem Out-Degree eines Knotens unterschieden:

• Der In-Degree entspricht der Anzahl der eingehenden Kanten eines Knotens: 𝑑𝑖In(𝑔) = #{𝑗: 𝑔𝑗i= 1}

• Der Out-Degree entspricht der Anzahl der ausgehenden Kanten eines
Knotens: 𝑑𝑖Out(𝑔) = #{𝑗: 𝑔𝑖j = 1}

Question 4

Maximale Kantenanzahl im Netzwerk (ungerichtet)

Answer 4

• Jeder Knoten kann mit jedem anderen Knoten im
Netzwerk verbunden sein.
• Das heißt, jeder der 𝑛 Knoten kann mit 𝑛 − 1 anderen Knoten verbunden sein.
• Im ungerichteten Netzwerk können wir nicht zwischen ein- und ausgehenden Kanten unterscheiden. Das Ergebnis muss also halbiert werden, um Kanten nicht doppelt zu erfassen.

• Die maximale Kantenanzahl in einem ungerichteten Netzwerk beträgt also 0,5 ∙ 𝑛 ∙ (𝑛 − 1).

Question 5

Maximale Kantenanzahl im Netzwerk (gerichtet)

Answer 5

• Im gerichteten Netzwerk können wir zwischen ein und ausgehenden Kanten unterscheiden. Das Ergebnis muss also nicht mehr halbiert werden.

• Die maximale Kantenanzahl in einem gerichteten
Netzwerk beträgt also 𝑛 ∙ (𝑛 − 1).

Question 6

Dichte in einem ungerichteten Netzwerk

Answer 6

Sei 𝑔 in Netzwerk mit 𝑒 Kanten und 𝑛 Knoten.
Dann ist die Dichte von 𝑔 das Verhältnis zwischen der Anzahl der im Netzwerk existierenden Kanten 𝑒 und der maximalen Anzahl möglicher Kanten im Netzwerk 𝑒max. Für ein ungerichtetes Netzwerk gilt:
𝑒max = 0,5n(n-1)

Die Dichte für ein ungerichtetes Netzwerk wird durch folgende Formel
beschrieben: siehe Zusammenfassung

Question 7

Dichte in einem gerichteten Netzwerk

Answer 7

In einem gerichteten Netzwerk beträgt die Anzahl maximal möglicher Kanten:
𝑒max = n*(n-1)
Die Dichte wird in diesem Fall mit folgender Formel berechnet: siehe Zusammenfassung