Introduction to Network Science - Cheatsheet

Definition und Klassifikation von Netzwerktypen

Definition:

Netzwerktypen sind Kategorien von Netzwerken, die basierend auf bestimmten Merkmalen klassifiziert werden. Dies hilft, unterschiedliche Netzwerke zu analysieren und zu verstehen.

Details:

• Reguläres Netzwerk: Netzwerke mit regelmäßiger, periodischer Struktur.
• Zufallsnetzwerk (Erdős-Rényi): Netzwerke, bei denen Kanten zufällig zwischen Knoten gezogen werden.
• Kleinwelt-Netzwerk (Watts-Strogatz): Netzwerke, die kurze Pfade und hohe Clustering-Koeffizienten aufweisen.
• Skalierbares Netzwerk (Barabási-Albert): Netzwerke mit Knoten, die nach einem skalierten Gesetz verbunden werden, oft „Power-law“ Verteilung.
• Hierarchisches Netzwerk: Netzwerke mit Ebenen oder hierarchische Struktur.

Grundlegende Netzwerkkomponenten: Knoten und Kanten

Definition:

Knoten (Nodes) sind die grundlegenden Bausteine eines Netzwerks und repräsentieren Entitäten, z.B. Personen, Computer. Kanten (Edges) sind Verbindungen zwischen Knoten und repräsentieren Beziehungen oder Interaktionen.

Details:

• Knoten: Eingekreiste Punkte
• Kanten: Linien zwischen Knoten
• Graph: Bestehend aus Knoten und Kanten
• Adjazenzmatrix: \(A = [a_{ij}]\) Darstellung von Verbindungen

Graphentheorie: Grundbegriffe und Typen von Graphen

Definition:

Details:

• Graph: Menge von Knoten (Vertices) und Kanten (Edges).
• Gerichteter Graph (Digraph): Kanten haben eine Richtung.
• Ungerichteter Graph: Kanten haben keine Richtung.
• Gewichteter Graph: Kanten haben Gewichte.
• Multigraph: Mehrere Kanten zwischen zwei Knoten möglich.
• Schleifenkanten (Loops): Kanten, die einen Knoten mit sich selbst verbinden.
• Adjazenzmatrix: Matrixdarstellung eines Graphen.
• Knotenmenge \(V\), Kantenmenge \(E\).
• Pfad: Folge von Knoten, deren benachbarte Paare durch Kanten verbunden sind.
• Kreis: Geschlossener Pfad, d.h. erster und letzter Knoten sind identisch.
• Zusammenhängender Graph: Jeder Knoten ist erreichbar von jedem anderen Knoten.
• Bipartiter Graph: Knotenmenge in zwei disjunkte Mengen teilbar, sodass jede Kante zwischen diesen Mengen verläuft.

Algorithmen der Graphentheorie: Dijkstras Algorithmus

Definition:

Dijkstra's Algorithmus: Finde kürzeste Wege in einem gewichteten Graphen vom Startknoten zu allen anderen Knoten.

Details:

• Eingabe: Graph G = (V, E) mit Kantenlängen (nicht-negativ), Startknoten s
• Ausgabe: Minimalen Distanzen von s zu allen Knoten in V
• Initialisiere \texttt{dist}(s) = 0 und \texttt{dist}(v) = \text{\texttt{∞}} für alle anderen v in V
• Verwende Prioritätswarteschlange (Min-Heap)
• Entferne den Knoten mit der kleinsten Entfernung aus der Warteschlange und aktualisiere die Distanzen der Nachbarknoten
• Schritt wiederholen, bis Warteschlange leer
• Komplexität: O((|V| + |E|)\texttt{log}|V|) mit Binärem Heap

Netzwerkmetriken: Zentralität, Clusterbildung

Definition:

Details:

• Zentralität: Messung der Wichtigkeit oder des Einflusses eines Knotens im Netzwerk.
  • Degree-Zentralität: Anzahl der direkten Verbindungen eines Knotens.
  • Betweenness-Zentralität: Häufigkeit, mit der ein Knoten auf den kürzesten Pfaden zwischen anderen Knoten liegt.
  • Closeness-Zentralität: Durchschnittliche kürzeste Entfernung eines Knotens zu allen anderen Knoten.
  • Eigenvector-Zentralität: Bedeutung eines Knotens basierend auf der Bedeutung seiner Nachbarn.
• Clusterbildung: Bewertung der Gruppierungsneigung in einem Netzwerk.
  • Clustering-Koeffizient (lokal): Maß für die Wahrscheinlichkeit, dass die Nachbarn eines Knotens untereinander verbunden sind.
  • Clustering-Koeffizient (global): Durchschnitt aller lokalen Clustering-Koeffizienten im Netzwerk.

Erkennung von Gemeinschaften in Netzwerken

Definition:

Erkennung von Gemeinschaften (oder Clustering) in Netzwerken bedeutet, Gruppen von Knoten zu identifizieren, die untereinander dichter verbunden sind als mit dem Rest des Netzwerks.

Details:

• Modularität: Maß für die Dichte von Verbindungen innerhalb von Gemeinschaften im Vergleich zu Verbindungen zwischen Gemeinschaften.
• Algo-Methoden: z. B. Girvan-Newman-Algorithmus, Louvain-Algorithmus, spektrale Methoden.
• Aufteilung vs. Verschachtelung: Gemeinschaften können disjunkt oder hierarchisch (verschachtelt) sein.
• Resolutionslimit: Feinheit, mit der kleine Gemeinschaften erkannt werden können.

Dynamische Netzwerkanalyse und Temporalität

Definition:

Analyse von Netzwerken, die sich über die Zeit ändern; Temporalität bezieht sich auf zeitliche Aspekte in Netzwerkanalysen.

Details:

• Erfassen von zeitabhängigen Veränderungen in Netzwerken
• Darstellung: Zeitgeordnete Graphen, zeitsensitive Metriken
• Wichtige Konzepte: Zeitscheiben (time slices), Zeitstempel (timestamps)
• Metriken: Zeitabhängige Zentralität, Persistenz, Netzwerkfluss

Anwendungen von Netzwerken in der Informatik: PageRank-Algorithmus

Definition:

Bewertungsalgorithmus für Webseiten, basierend auf deren Verlinkungsstruktur.

Details:

• Entwickelt von Google-Gründern Larry Page und Sergey Brin.
• Bestimmt die Relevanz einer Webseite durch die Anzahl und Qualität der eingehenden Links.
• Nutzung einer Übergangsmatrix und des Konzeptes der Markow-Ketten.
• Iterative Berechnung bis zur Konvergenz der Rangwerte.
• Formel: \[ PR(A) = \frac{1-d}{N} + d \left( \sum_{i=1}^{N} \frac{PR(T_i)}{C(T_i)} \right) \] wobei \[ d \] der Dämpfungsfaktor ist, \[ PR(A) \] der PageRank der Seite A, \[ T_i \] Seiten, die auf Seite A verlinken, und \[ C(T_i) \] die Anzahl der ausgehenden Links von Seite \[ T_i \].