Introduction to Network Science - Cheatsheet

Knoten, Kanten und Netzwerktopologien

Definition:

Grundlegende Bausteine der Netzwerkwissenschaft - Erklären die Struktur von Netzwerken.

Details:

• Knoten (Nodes): Repräsentieren Entitäten (z. B. Personen, Computer).
• Kanten (Edges): Verbindungen zwischen Knoten, können gerichtet oder ungerichtet sein.
• Netzwerktopologien: Struktur eines Netzwerks, beschreibt, wie Knoten und Kanten angeordnet sind.
• Formeln: Anzahl der Knoten: \( |V| \) ; Anzahl der Kanten: \( |E| \)
• Topologie-Typen:
  • Stern (Star): Eine zentrale Einheit, die mit allen anderen verbunden ist.
  • Ring (Ring): Knoten sind in einer geschlossenen Schleife verbunden.
  • Vollständig (Complete): Jeder Knoten ist mit jedem anderen Knoten verbunden.
  • Skalierungsnetzwerk (Scale-free Network): Einige Knoten aufgrund von verteilungsverteilungsähnlichem Aufbau haben viele Verbindungen (z. B. das Internet).

Netzwerkmetriken und -kennzahlen

Definition:

Netzwerkmetriken und -kennzahlen quantifizieren Eigenschaften und Strukturen in Netzwerken.

Details:

• Grad (Degree): Anzahl der Verbindungen eines Knotens. \( k_i \)
• Dichte: Anteil der möglichen Verbindungen, die tatsächlich existieren. \[ D = \frac{2m}{n(n-1)} \]
• Durchmesser: Maximale Länge der kürzesten Pfade zwischen allen Knoten.
• Clustering-Koeffizient: Wahrscheinlichkeit, dass Nachbarn eines Knotens verbunden sind. \[ C_i = \frac{2e_i}{k_i(k_i-1)} \]
• Betweenness-Zentralität: Anteil der kürzesten Pfade durch einen Knoten. \[ g_i = \sum_{s,t} \frac{\rho(s,i,t)}{\rho(s,t)} \]
• Eigenvector-Zentralität: Einfluss eines Knotens basierend auf der Vernetzung seiner Nachbarn.

Flussprobleme in Netzwerken

Definition:

Optimierungsprobleme, die sich mit dem Transport von Gütern oder Informationen innerhalb eines Netzwerks befassen. Ziel: Maximierung des Flusses von einer Quelle zu einer Senke unter Einhaltung von Kapazitätsbeschränkungen.

Details:

• Netzwerk: Gerichteter Graph mit Knoten und Kanten
• Kapazität: Maximale Flussmenge pro Kante
• Flussfunktion: Zuordnung eines Flusses zu jeder Kante, die Kapazität nicht überschreitet
• Erhaltungsbedingung: Für alle Knoten, außer Quelle und Senke, gleiche einfließende und ausfließende Flussmengen
• Max-Flow-Min-Cut-Theorem: Maximaler Fluss vom Netz entspricht der minimalen Kapazität eines Schnitts, der Quelle und Senke trennt
• Algorithmus: Ford-Fulkerson, Edmonds-Karp
• Formel für Flussfunktion: \sum_{u:(u,v)\in E} f(u,v) = \sum_{w:(v,w)\in E} f(v,w)
• Kapazitätsbeschränkung: \forall (u,v) \in E, 0 \leq f(u,v) \leq c(u,v)

Community Detection und Netzwerkcluster

Definition:

Erkennung von Gruppen eng verbundener Knoten in einem Netzwerk; zielt darauf ab, die Netzwerkstruktur zu verstehen.

Details:

• Ziel: Identifikation von Clusterstrukturen
• Modularität: Maß zur Bewertung der Clusterqualität
• Algorithmen: Girvan-Newman, Louvain-Methode, k-means
• Eigenvektor-zentrierte Methode: Spektrales Clustering
• Überlappende Gemeinschaften: Knoten können Teil mehrerer Cluster sein

Netzwerksicherheit und -schutzmechanismen

Definition:

Netzwerksicherheit beschäftigt sich mit dem Schutz der Netzwerk-Infrastruktur und -Daten gegen unbefugten Zugriff, Missbrauch oder Ausfall. Schutzmechanismen sind Strategien und Technologien zur Prävention, Erkennung und Reaktion auf Sicherheitsbedrohungen.

Details:

• Firewall: Filtert den Netzwerkverkehr basierend auf vordefinierten Regeln.
• Intrusion Detection System (IDS): Überwacht Netzwerkverkehr auf verdächtige Aktivitäten.
• Verschlüsselung: Sichert Daten durch Umwandlung in unleserliche Form.
• VPN: Schützt Kommunikation über unsichere Netzwerke durch Verschlüsselung.
• Zugangskontrolle: Regelt, wer auf Netzwerkressourcen zugreifen darf.
• Patch-Management: Regelmäßige Updates zur Behebung von Sicherheitslücken.

Genregulations- und Protein-Interaktions-Netzwerke

Definition:

Netzwerke, die Genexpression und Proteininteraktionen in biologischen Systemen beschreiben.

Details:

• Genregulationsnetzwerke: Knoten = Gene, Kanten = regulatorische Interaktionen (Aktivierung, Repression)
• Protein-Interaktions-Netzwerke: Knoten = Proteine, Kanten = physikalische Interaktionen (Bindung, Modifikation)
• Mathematische Darstellung: Adjazenzmatrix, Gewichtete Graphen
• Häufig verwendete Algorithmen: DFS, BFS, Clustering
• Wichtige Begriffe: Transkriptionsfaktor, Signalkaskade, Modulare Netzwerke

Epidemiemodelle in Netzwerken

Definition:

Modelle zur Beschreibung der Ausbreitung von Krankheiten in Netzwerken.

Details:

• SIR-Modell: Drei Zustände - Susceptible (S), Infectious (I), Recovered (R).
• SIS-Modell: Zwei Zustände - Susceptible (S) und Infectious (I), keine Immunität nach Genesung.
• Mathematische Formulierung (SIR): \[ \frac{dS}{dt} = -\beta IS \]\[ \frac{dI}{dt} = \beta IS - \gamma I \]\[ \frac{dR}{dt} = \gamma I \]

Stabilität und Robustheit von Netzwerken

Definition:

Maßnahmen und Eigenschaften, die sicherstellen, dass Netzwerke trotz Fehlern und Angriffen weiter funktionieren.

Details:

• Stabilität: Fähigkeit eines Netzwerks, nach einer Störung zum Gleichgewicht zurückzukehren.
• Robustheit: Widerstandsfähigkeit eines Netzwerks gegen Ausfälle und Angriffe.
• Netzwerke zeichnen sich durch verschiedene Architekturen (z.B. skalenfreie Netzwerke) aus, die deren Stabilität und Robustheit beeinflussen.
• Wichtige Messgrößen: Clusterkoeffizient, Durchmesser, mittlere Pfadlänge.