Was ist der Sinn von Strukturen?
in der Natur: max Stabilität bei min Gewicht
Partner-/Futtersuche
Phys. Effektivität
Schutz/Verteidigung
in technischen Systemen: max kurze Wege mit min Verbindungen
Resourcenmanagement
Geschwindigkeit
Suche
Fehlertoleranz
Sicherheit
4 Zusammenhänge zwischen System- und Grapheneigenschaften
Untergraphen, Clusterkoeffizient -> Systemabgrenzungen, Systemkomponenten, Systemhierarchieen
Zusammenhang, Wege, Kreise -> Fehlertoleranz, Ausfallsicherheit
kürzeste/längste Wege -> Kommunikationszeiten, Kosen
Durchmesser -> maximale Kommunikationszeit, Kosten
7 Arten von Strukturen
Linien- (Bus-) Strukturen
gibt Anfangs- und ein Endelement
direkt nebeneinander liegende Elemente miteinander verbunden
Ringe
Knoten im Kreis angeordnet
(Rechteckige) Gitterstrukturen
Knoten haben eine feste Anzahl von Nachbarn (2n bei n Dimensionen) -> gibt auch hexagonale und dreieckige Gitter
Entstehen durch nebeneinanderlegen von Linien und Ringen
Hypercubes
n-dimensionale entstehen durch (n-1) dimensionale Hypercubes
besitzen 2^n Knoten
Vollständig vermaschtes Netz
jeder Knoten ist mit jedem anderen verbunden
Sterne
ein Knoten in der Mitte, alle gehen von ihm aus
Bäume
Struktur geht von Wurzelknoten aus
immer Verzweigung in Wurzelknoten
Vor- und Nachteile bei Linien- und Ringen (2 und 3)
Vorteile:
minimaler Leistungsaufwand
einfach erweiterbar
Nachteile:
Überlastung bei hohem Volumen
lange Wege
Totalausfall, wenn eine Station ausfällt
a) Linie/ Bus, b) Ring
Vor- und Nachteile von Gitterstrukturen (4 und 1)
einfache 2- aber auch n-dimensionale Strukturen
leicht erweiterbar
starker Zusammenhang = viele Wege zwischen 2 Knoten
Es gibt Koordinaten
relativ lange Wege
Vor- und Nachteile von Hypercubes (2 und 1)
Vorteil:
kurze Wege
Nachteil:
feste Knotenanzahl bei gegebenem n
Vor- und Nachteile von vollständig vermaschten Netzen
extrem leistungsfähig, weil immer nur ein Schritt zwischen 2 Knoten
unempfindlich gegen Störungen
besonders aufwändig und teuer -> n * (n - 1) / 2 Verbindungen nötig
Vor und Nachteile von Sternen (2 und 2)
einfache Struktur
unempfindlich gegenüber Ausfällen von Knoten/ Verbindungen
Abhängig vom Sternknoten
herausgehobene Rolle des Zentralknotens
Vor- und Nachteile von Bäumen (4 und 1)
kurze Wege (~ ln N)
hierarchische Struktur
Abhängigkeit vom Wurzel-/ Vaterknoten
Was bedeutet das Small World Phänomen
basiert auf Experimenten von Stanley Milgram (Briefe senden)
relativ kurze Wege zwischen willkürlichen Personen
in Graphen mit der Eigenschaft: viele Knoten, die nicht direkte Nachbarn sind, aber deren Nachbarn sind mit hoher Wahrscheinlichkeit Nachbarn
--> überraschend kurze Pfade zwischen beliebigen Teilnehmern
Suchstrategie z.B. Greedy-Algorithmus
5 + 1 Modelle für Small World Networks (nur nennen)
Erdös-Rényi Modell
a) Watts und Strogatz
b) Edge-Addition
Preferential Attachment
Evolving Web Graph Growth
Random Power Law Graphs
Beschreibe Konstruktion von Erdös-Rényi Modell
Wieviele Kanten im Mittel?
Gegeben: Modell G(N, p)
N Knoten
Wahrscheinlichkeit p
E = Menge aller möglichen Kanten zwischen allen Knoten
Konstruktion:
Starte mit Nullgraphen (alle Knoten, 0 Kanten)
füge jedes e in E mit Wahrscheinichkeit p hinzu
Diskussion:
im Mittel (N über 2) x p Kanten = n x (n-1) / 2 x p
Nachteile von Erdösz-Renyi (2)
feste Anzahl Knoten
-> keine Modellierung dynamisch wachsender/ schrumpfender Graphen
kaum Clusterbildung
(wichtig für Modellierung sozialer Netzwerke)
Was ist der Clusterkoeffizient
Formel
Koeffizient gibt an, wie stark Nachbarn eines Knotens untereinander vernetzt sind
(“Freunde kennen sich mit hoher Wahrscheinlichkeit untereinander)
Ci = Knoten i
e_j, k = Kanten zwischen zwei Nachbarn des Knoten
k = Anzahl aller Nachbarn des Knotens
= Anzahl aller Kanten / Anzahl möglicher Kanten
Wie berechnet sich globaler Clustercoeffizient?
Mittelwert aus allen lokalen Clusterkoeffizienten
Beschreibe Konstruktion von Watts und Strogatz
und 2 Eigenschaften
Gegeben: Modell G(N,d,p)
d = Anzahl der Nachbarn
Starte mit Ring aus N Knoten
Verbinde jeden Knoten mit seinen d nächsten Nachbarn
-> ergibt Menge E der existierenden (n x d)/2 Kanten
für alle e in E : Edge Reassignment
= mit Wahrscheinlichkeit p bekommt e einen neuen Endpunkt
Eigenschaften:
kleiner mittlere Pfadlänge L
hoher Clusterkoeffizient C
Beschreibe Edge-Addition
3 Eigenschaften
2 Nachteile
Erweiterung von Watts-Strogatz-Modell durch Newman, Moore und Watts
statt Kanten mzubiegen werden (mu x N x d) /2 zusätzliche Kanten hinzugefügt
mathematisch leichter zu handhaben
kleine mittlere Pfadlänge L
feste Knotennanzahl
feste Anzahl ausgehender Kanten
Was ist der Durchmesser?
= maximal auftretende Distanz zwischen zwei beliebigen Knoten im Graphen
Was ist der effektive Durchmesser?
= Distanz unter der sich mindestens 90% aller Knoten untereinander erreichen können
Konstruktion des Preferential Attachment
starte mit Nullgraph aus kleiner Anzahl von m_0 Knoten
zu jedem Zeitpunkt t:
füge neuen Knoten mit m <= m_0 Kanten hinzu
Wahrscheinlichkeit Pi dass neuer Knoten mit einem existierenden Knoten i verbunden ist:
d_i = Valenz von i = Anzahl der existierenden, ungerichteten Kanten, die mit i verbunden sind
2 Eigenschaften von Preferential Attachment
beliebig wachsende Graphen möglich
Power Law Verteilung
= Wahrscheinlichkeit, dass Knoten Valenz k hat, ist polynomiell abhängig von k
Beispiel für Power Law in realen Netzwerken
und 2 andere Beispiele
2 andere Beispiele:
Auftreten natürlicher Zahlen auf Webseiten
Antwortzeiten im Briefverkehr
Grundlage des Evolving Web Growth Graph
und 2 Varianten nennen
Stochastische Modellierung des Webgraphen
Modell G_t= (V_t, E_t)entwickelt sich in diskreten Zeitschritten t = 1, 2, …
Knoten und Kanten werden gemäß Funktion f.V(V.t, t) und f.e(f.V, G.t, t) hinzugefügt
beide Funktionen beschreiben Graphen vollständig
2 Varianten:
Lineares Wachstum
exponentielles Wachstum
Konstruktion des Evolving Web Graph mit linearem Wachstum
zur Zeit t wird ein neuer Knoten u erzeugt (f.v(V.t, t) = 1)
u bekommt Kopierfaktor p in (0,1) und konstante Ausgangsvalenz d+ > 0
ein Prototypknoten v aus V.t wird ausgewählt
d+ Kanten von u ausgehend erzeugen
i-te Kanten führt mit Wahrscheinlichkeit p zu einem beliebigen Endknoten aus V.t
mit Wahrscheinlichkeit 1-p wird der i-te Endknoten aus den Kanten des Prototypenknotens v kopiert
= Seite u verweist in ein existierendes Themengebiet (repräsentiert durch v) und erweitert dieses durch einen Link
Konstruktion des Evolving Web Graph mit exponentiellem Wachstum
beschrieben durch:
Wachstumskonstante p
loop-Faktor gamma = Anteil Schleifen = Verweise auf sich selbst
tail-copy Faktor gamma’ = 1- gamma’ ist Wahrscheinlichkeit, dass Kante auf gerade hinzugefügten Knoten zeigt
out-degree Faktor d
Anzahl Knoten die zum Zeitpunkt t+1 erzeugt werden ist binomialverteilt über V.t und p f.V(V.t, t) ~ B(V.t, p)
Topologie des WWW
Scc = Strongly Connected Cluster
In = eingehende Links
Out = ausgehende Links vom SCC
Tendrils = Sackgassen
Tubes = verbinden Randbereiche des WWW
Was ist ein Cluster?
(Newman-Moore-Watts)
= Menge von Knoten, die einen vollständigen Untergraph bilden
2 Rollen von Knoten in einem Cluster
Authority
Hub
-> Knoten können auch beide Rollen einnehmen
Was ist eine Authority? (Gibson 1998)
Seite mit Inhalt, die gut auf eine Suchanfrage passt
Eigenschaft korreliert nicht ausschließlich mit Eingangsvalenz
auch wie sehr Knoten selbst meint, eine Authority zu sein
Was ist ein Hub?
Verweist auf eine oder mehrere Authorities
-> Suchmaschinen sollen möglichst kleine Menge von Authority-Seiten ausweisen
Was ist eine Adjazenzmatrix?
repräsentiert Graphen mit N Knoten als Matrix
1, wenn Knoten Nachbarn haben, sonst 0
(gingen von ungerichteten Graphen aus)
Was ist HITS
= Hyperlinked Induced Topic Search
identifiziert Hubs und Authorities
Vorgehen:
mit Menge S von Seiten beginnen
z.B. durch Anfrage bei einer Suchmaschine
ist kleiner Webuntergraph zu einem spezielllen Thema
Graph durch Seiten erweitern, auf die aus S verwiesen wird oder die auf Knoten in S verweisen
-> ergibt Graph G
für jeden Knoten x von G berechnen:
a(x) - einen nichtnegativen Authority-Wert (Initialwert: 1)
h(x) - einen nichtnegativen Hub-Wert (Initalwert: 1)
Für alle Vorängerknoten v von x:
für alle Nachfolgerknoten w von x
Hub- und Authoritywerte in jedem Schritt normalisieren (rein lokale Berechnung ist nicht möglich):
Konvergiert zu den ersten Eigenvektoren:
Was ist PageRank?
und Formel
(von Google/ Bage und Brin)
jede Seite erhält Zahl, die anzeigt, wie stark andere Seiten auf sie verweisen
sagt aus wie wahrscheinlich ein random surfer auf der Seite landet
Ausgangsvalenz = 1 oder 1/N
Dämpfangsfaktor, weil auch zufälliger Surfer irgendwann nicht mehr Links folgt
Was ist PageReputation
auch Algorithmus mit Modell “Random Surfer”
Suche nach Seiten die Term tau enthalten
gibt es keine, dann willkürlich wählen
je Zeitschritt eine Seite besucht
nächste Seite:
entweder einem Ausgangslink folgen
oder zufällig wählen
Was ist Multicast im Gitter?
Nachricht wird an alle Maschinen versandt
eventuell viele identische Nachrichten versandt
Optimale Lösung: minimum spanning tree auf dem Gitter konstruieren
-> Np-hartes Problem
Was ist Kleinbergs Netzwerkmodell?
und 3 Voraussetzungen
und Ergebnis
dient zur Analyse der maximalen Effektivität von Suchverfahren in dezentralen Systemen
Wieder Knoten in 2D Gitter mit Kantenlänge n
jeder Knoten mit allen Nachbarn p-ten Grades vernetzt
z.B. p=1, dann alle direkten Nachbarn
jeder Knoten hat q weitere Links zu entfernten Nachbarn
Knoten v mit Wahrscheinlichkeit d(u,v)^-r als Nachbar gewählt wird
d(u,v) = Anzahl Schritte, um v von u zu erreichen
bei r=0 ist gleichmäßige Verteilung
Beispiel: p=1, q=2:
Voraussetzungen: Suchalgorithmus kennt…
aktuelle Position im Gitter = geographische Information
Nachbarn und Links des aktuellen Knotens = lokale Information
Nachbarn und Links bisher besuchter Knoten = History
Ergebnis:
kürzeste Suchzeit: O(log^2 n)
Abhängigkeit der Suchzeit von r
Was ist der Random Walker
Nachricht zirkuliert im System
enthält immer alle Informationen über die von ihr besuchten Knoten
jeder besuchte Knoten kann die Nachricht nutzen
Knoten können einfach hinzugefügt oder entfernt werden
Problem:
sehr langsam bei großen Netzen
Lösung:
Anzahl besuchter Knoten begrenzen
mehrere Wanderer verwalten Gruppen von Knoten
Was ist die denzentrale Kontrolle der Population?
jeder Knoten bestimmt Intervall, in dem er von Random Walker besucht werden will: [t-min, t-max]
t-min = wie oft höchstens
t-max = wie oft wenigstens
Knoten verarbeitet Besuchszeiten und bildet aus n Werten einen Mittelwert t’
kommen zu wenige Walker -> Knoten generiert einen
kommen zu viele Walker -> Knoten entfernt nächsten
Wie wird Voting lokal ausgeführt?
Community ist endliche Menge
jedes Mitglied trägt Information (Bsp. weiße oder schwarze Farbe)
jedes Mitglied wählt n-große Untermenge von M
Mitglied übernimmt Information der Mehrheit (wird schwarz gefärbt)
neue Bipartition mit der Evoluationsschritt wiederholt wird
Fazit von dezentralen Verfahren
effektive Suche auch ohne Broadcast möglich
intelligente Verfahren arbeiten nur mit lokalen Informationen ohne History
Selbstorganisation durch Strukturbildungsanalyse
Quadratisches Gitter - Clusterkoeffizient und Durchmesser
n² Knoten
Clusterkoeffizient: 0
kein Nachbar direkt mit dem anderen verbunden
Durchmesser: 2(n-1)
gegenüberliegende Ecken
Manhattan-Metrik
Bus mit n Stationen - Clusterkoeffizient und Durchmesser
wenn Bus eigene Station
Clusterkoeffizient: 1
wenn Bus multiple Kante und jeder Knoten mit jedem vernetzt ist
Durchmesser: 2
Durchmesser: 1
wenn Bus multiple Kante
Ring mit n Stationen - Clusterkoeffizient und Durchmesser
Durchmesser: n/2
gegenüberliegende Knoten
Ring mit n Stationen und unidirektional - Clusterkoeffizient und Durchmesser
Durchmesser: n-1
Entfernung zu Nachbarn, mit dem Knoten nicht direktional verbunden ist
Stern mit n Stationen - Clusterkoeffizient und Durchmesser
nur mit Zentrum verbunden
hat 0 mögliche und 0 tatsächliche Verbindungen zu Nachbarn
immer über Zentrumsknoten
d-dimensionaler Hyperwürfel - Clusterkoeffizient und Durchmesser
Durchmesser: d
Definition Hyperwürfel: in jeder Dimension nur ein Vermittlungsschritt nötig
Vollständig vermaschtes Netz mit n Stationen - Clusterkoeffizient und Durchmesser
jeder mit jedem vernetzt
Balancierter k-närer Baum mit n Elementen - Clusterkoeffizient und Durchmesser
Durchmesser: 2 * c * log_k n
c ist eine Konstante
zwischen 2 Blättern, die nur über Wurzel miteinander verbunden sind
Wie berechnet sich die mittlere Pfadlänge?
Durchschnitt der Pfadlänge zu allen anderen Knoten von k1 aus
Pfadlängen aufschreiben
durch Anzahl Knoten rechnen
Last changed10 months ago