Network Analysis
3. Semester, Matthias Dehmer
3. Semester, Matthias Dehmer
Was sind die Knoten und was die Kanten bei folgenden Netzwerkten:
- Gehirn (Neuronale Netze)
- Websites
- Facebook
- V: alle Mitglieder
- E: {v,v`} ist eine Kate falls v und v` befreundet sind
- Gehirn
- V: Neuronen
- E: Verbindung zwischen den Neureonen
- Websites
- V: Webpages
- E: Links zwischen den Pages
Was sind Modelle?
???
Menge der Komplexen Netzwerke defineiren:
Durch ausschluss von einffachen Graphen:
- ???
Nenne Beispiele für Netzwerkmodelle.
- Small-Worls
- Scale Free
- Random-Modell
Nenne Netzwerkeigenschaften und Beispiele dafür.
- Descriptive Eingenschaften (beschreibend)
- Graphklassen
- Small-World
- Scale-Free
- Graphklassen
- Quantitative Eigenschaften (messend)
- Tool
- Netzwerk Complexity
- Comparative Analysis
- Tool
Was ist die Gradverteilung?
Sie zeigt, wie unterschiedlich die Kanten auf die einzelnen Knoten im Netzwerk verteilt sein können.
Die Verteilung der Knotengrade ist eines der wichtigsten Merkmale zur Charakterisierung von Netzwerken.
Welche Arten von Gradverteilungen gibt es?
- heavy tailed
- erreicht 0 weniger schnell als eine Exponentalverteilungs-Tail
- Poisson-Verteilt
- klassische Annhame, dass die Grade alelr Knoten um einen Durchschnittswert schwanken
- Zufallsgraphenmodell (Random-Modell)
- klassische Annhame, dass die Grade alelr Knoten um einen Durchschnittswert schwanken
- Polynomieller Zusammenhang
- typische "ungeliche" Gradverteilung realer Netzwerkte
- Potenzgesetz
- Atraktivitätsmodell
- typische "ungeliche" Gradverteilung realer Netzwerkte
Was sind Homogenitätsmasse?
???
Wie wird ein klassischer Zufallsgraph nach ERdös-Renyi erzeugt?
- n und p werden festgelet
- n leere Knoten erstellen
- jede Kante wird mit der Wahrscheinlichkeit p (zwischen 0 und 1) erstellt
- Anhand dieser Wahrscheinlichkeit wird eine Kante zwischen den Knoten erstellt oder nicht
bei p = 1, würde ein Vollständiger Graph (jeder Knoten mit jedem verbunden) erstellt werden
Wie wird ein Small-World Netzwerkt nach Watts Strogatz erzeugt?
Es wird ein Reguläreres Netzwerk genommen und so angepasst, dass es schlussendlich random wird.
???
Was ist ein Reguläreres Netzwerk?
Wenn alle Knoten den gleichen Grad besitzen.
Was ist ein Hub?
Ein Hub ist ein Knoten mit einem höhrern Grad als der durchschnitts Grad.
Hubs sind wichtige Knoten, da bei ihrem wegfall / ausfall die Verbindung zu vielen anderen Knoten unterbrochen/ verlängert wird.
Was ist "Powerlaw"?
Die Wahrscheinlichkeit, dass ein Knoten einen spezifischen Grad hat
Was ist ein Clustering Coeffizient
ist ein Mass für die Cliquenbildung bzw. Transitivitä eines Netzwerkes.
Nenne Eigenschaften eines Scale Free Netzwerks:
- sind Zufallsgaphen
- Die Gräder folgem dem Powerlaw
- haben wenige Hubs und viele Knoten mit kleinen Grädern
Wie wird ein Scale-Free Netzwerk nach Barabasi Albert erzeugt?
Ein Knoten v verbindet sich mit höherer Wahrscheinlichkeit an Hubs.
- Knoten mit höherem Grad werden grösser, Knoten mit kleinem Grad bleiben klein
- Beispiel: Facebook
- Bekannte Leute bekommen mehr Follower als unbekannte
Wie wird der "Local clustering Coefficient" berechnet?
- Formel
- Berechnung der Graphen im Anhang
c(vi) = Knoten bei welchem wir den Koeffizient messen wollen
mi = tatsächlich direkt verlaufenden Kanten zwischen den Nachbarn
ki = Anzahl Nachbarn
Wie wird die "Closeness Zentralität" gemessen?
- Formel
- Lösung zum Graph im Anhang
D = distanz, kürzester Pfad zwischen v und w
Welches ist der wichtigeste Knoten in einem Netzwerk? (Most Important)
Der Knoten mit dem höchsten Zentralität Mass (Closeness Zentralität)
Wie wird die "Betweenness Zentralität" gemessen?
- Formel
- Lösung zum Graph im Anhang
Sag aus, wie viele Knoten benötigen werden um von einem Knoten zu einem andern zu gelangen.
Was ist ein Komplexitäts-Mass?
Ein Mass für die berechnung der Komplexität eines Graphen.
Was ist ein Graphmass?
Ist eine Abbildung eines Graphen auf eine reelle Zahl.
G -> R
Welche Komplexitäts-Masse gibt es?
- Wiener Index
- Summe des kürzesten Weges zwischen zwei Knoten
- Randic Index
- ??
- d(G,H) oder s(G,H)
- Ähnlichkeit zweier Graphen
Wie wird die komplexität eines Netzwerkes bestimmt?
Hängt vom Auge des betrachters ab.
Muss somit vorab definiert werden, damti alle mit dem gleichen Komplexitäts-Mass rechnen.
Was versteht man unter "Modul suche"?
Das auffinden von einer dichten Anzahl an Knoten in einem Teil-GrapH
Nenne Anwendungen von Graph-Mining?
- suchen von Modulen
- Ähnlichkeitssuche
- Netzwerkvergleiche (z.B. Webseiten)
- Graph Datenbanken
- QSAR/QSPR und drug design
- Quantitative Structured Activity Relationship
- Quantitative Structured Property Relationship
Wie lautet die Definition von "Data-Mining"?
Aus Daten werden interessante Muster gesucht mit denen Wissen generiert werden können um Aufgaben zu lösen
Wie analysiert man Netzwerke/Graphen?
- Quantitative Graphentheorie
- Messende Analyse
- Netzwerk auf eine Zahl reduzieren -> z.B. Anzah Knoten/Kanten
- Deskriptive Graphentheorie
- Beschreibende Analyse / Empierisch
Was ist ein "deterministischer Graph" ?
Beschreibung und Beispiel
Deterministisch:
Wenn die Erstellungsmethode immer wieder den selben Graphen generiert.
Nicht Zeitabähnig.
Beispiele:
- Internes Computer Netzwerk
- Strassen-Netzwerk
- U-Bahn
- Chemische Strukturen
Was ist ein "nicht deterministischer Graph"?
Beschreibung und Beispiel
Wenn die Erstellungsmethode immer wieder einen anderen Graphen generiert, ohne Anpassung an der Methode selber.
Biepspiel:
- Aktien-Graph
- Biologische-Netzwerke
Welcher Durchmesser hat dieser Graph?
2
Wie wird der Durchmesser (diameter) eines Graphen bestimmt?
Mit dem längsten kürzesten Weg zwischen zwei beliebigen Knoten eines Graphen.
Die Formel ist so zu verstehen, dass alle kürzesten Wege zwischen allen Knoten gesucht werden und dann der längste (maximale) ausgewählt wird.
Ist der Durchmesser das beste Mass um einen Graphen zu beschreiben?
Nein, weil...
Was ist ein Graphvergleichsmass?
Ist das Karthesische Produkt aller geordnenten Tupel aus dem Graphen. G x G -> R
Beispiel:
(1,5) x (1,7) = (1,1), (1.7), (5.1), (5.7)
Was sind die Bedingungen für einen Baum-Graphen?
- Zusammenhängend (keine losen Knoten)
- Zyklusfrei
- Zwei Knoten haben nur einen gemeinsam Pfad
Was sind die Bedingungen für einen Wurzelbaum-Graphen?
- gleiche wie bei einem Baum
- Alle Knoten sind Weggerichtet --> Es ergibt sich eine Wurzel
Nenne verschiedene Typen von Netzen:
- Social Netzworks
- Fachebook
- Web Graphs
- Document Structures
- Knoeledge (Information) Networks
- Technology Networks
- Internet
- Strom
- Wasser
- Biological Networks
- Neuronen
- Transport Networks
- Züge
- Strom
Beschreibe und zeichne "Reflexive-Beziehung" im einem Graphen.
a ist gleich alt wie a und b ist gleich alt wie b
Beschreibe und zeichne "Symmetrisch-Beziehung" im einem Graphen.
a ist gleich alt wie b, somit ist b auch gleich alt wie a
Beschreibe und zeichne "Transitive-Beziehung" im einem Graphen.
a ist gleich alt wie b, b ist gleich alt wie c, somit ist auch a gleich alt wie c
-
- 1 / 69
-
Lernkarten
Wie lautet die Adjazenzmatrix für den folgenden Graphen?
Um welche Adjazenzmatrix handelt es ich hier?
Es handelt sich um eine Quadratische Adjazenzmatrix,
Was bedeutet Adjazenz?
Ein Knoten ist adhazent mit einem anderne Knoten, wenn sie über eine Kante miteinander verbunden sind.
Knoten-Knoten Verbindung = Adjazenz
Was macht eine symmetische Adjazentzmatrix aus?
- ungerichtet, so können alle Kanten in beide richtungen genutzt werden
- Matrix ist so entlang der Diagonalen symmetrisch
Was ist der "kürzestete Weg"?
Ist der minimale Pfad zwischen zwei Knoten.
Was ist eine "topologische distanz"?
"topologische distanz" = Ist die Anzahl der Kanten in einem kürzesten Weg zwischen zwei Knoten.
Was ist eine Distanzmatrix?
Ist eine Matrix mit der jeweiligen Anzahl Kanten des kürzesten Weges zwischen den zwei Knoten.
Definition von Netzwerken
Abstrakte Objekte, um Zusammenhänge und Interaktionen zwischen Elementen von komplexen und heterogenen Systemen zu beschreiben.
Ein Netzwerk (oder Graoh) ist ein Paar(V, E)
- V: endliche Menge von Knoten
- E: Teilmenge von V2 (Kanten)
Nenne Beispiele für reale Netzwerke?
- Facebook (soziale Netzwerke)
- Gehirn (Neuronale Netze)
- Sind durch Deep-Learning wieder interessant gewornden
- Websites (z.B. FFhs-Webseite)
Was sind die Knoten und was die Kanten bei folgenden Netzwerkten:
- Gehirn (Neuronale Netze)
- Websites
- Facebook
- V: alle Mitglieder
- E: {v,v`} ist eine Kate falls v und v` befreundet sind
- Gehirn
- V: Neuronen
- E: Verbindung zwischen den Neureonen
- Websites
- V: Webpages
- E: Links zwischen den Pages
Was sind Modelle?
???
Menge der Komplexen Netzwerke defineiren:
Durch ausschluss von einffachen Graphen:
- ???
Nenne Beispiele für Netzwerkmodelle.
- Small-Worls
- Scale Free
- Random-Modell
Nenne Netzwerkeigenschaften und Beispiele dafür.
- Descriptive Eingenschaften (beschreibend)
- Graphklassen
- Small-World
- Scale-Free
- Graphklassen
- Quantitative Eigenschaften (messend)
- Tool
- Netzwerk Complexity
- Comparative Analysis
- Tool
Was ist die Gradverteilung?
Sie zeigt, wie unterschiedlich die Kanten auf die einzelnen Knoten im Netzwerk verteilt sein können.
Die Verteilung der Knotengrade ist eines der wichtigsten Merkmale zur Charakterisierung von Netzwerken.
Welche Arten von Gradverteilungen gibt es?
- heavy tailed
- erreicht 0 weniger schnell als eine Exponentalverteilungs-Tail
- Poisson-Verteilt
- klassische Annhame, dass die Grade alelr Knoten um einen Durchschnittswert schwanken
- Zufallsgraphenmodell (Random-Modell)
- klassische Annhame, dass die Grade alelr Knoten um einen Durchschnittswert schwanken
- Polynomieller Zusammenhang
- typische "ungeliche" Gradverteilung realer Netzwerkte
- Potenzgesetz
- Atraktivitätsmodell
- typische "ungeliche" Gradverteilung realer Netzwerkte
Was sind Homogenitätsmasse?
???
Wie wird ein klassischer Zufallsgraph nach ERdös-Renyi erzeugt?
- n und p werden festgelet
- n leere Knoten erstellen
- jede Kante wird mit der Wahrscheinlichkeit p (zwischen 0 und 1) erstellt
- Anhand dieser Wahrscheinlichkeit wird eine Kante zwischen den Knoten erstellt oder nicht
bei p = 1, würde ein Vollständiger Graph (jeder Knoten mit jedem verbunden) erstellt werden
Wie wird ein Small-World Netzwerkt nach Watts Strogatz erzeugt?
Es wird ein Reguläreres Netzwerk genommen und so angepasst, dass es schlussendlich random wird.
???
Was ist ein Reguläreres Netzwerk?
Wenn alle Knoten den gleichen Grad besitzen.
Was ist ein Hub?
Ein Hub ist ein Knoten mit einem höhrern Grad als der durchschnitts Grad.
Hubs sind wichtige Knoten, da bei ihrem wegfall / ausfall die Verbindung zu vielen anderen Knoten unterbrochen/ verlängert wird.
Was ist "Powerlaw"?
Die Wahrscheinlichkeit, dass ein Knoten einen spezifischen Grad hat
Was ist ein Clustering Coeffizient
ist ein Mass für die Cliquenbildung bzw. Transitivitä eines Netzwerkes.
Nenne Eigenschaften eines Scale Free Netzwerks:
- sind Zufallsgaphen
- Die Gräder folgem dem Powerlaw
- haben wenige Hubs und viele Knoten mit kleinen Grädern
Wie wird ein Scale-Free Netzwerk nach Barabasi Albert erzeugt?
Ein Knoten v verbindet sich mit höherer Wahrscheinlichkeit an Hubs.
- Knoten mit höherem Grad werden grösser, Knoten mit kleinem Grad bleiben klein
- Beispiel: Facebook
- Bekannte Leute bekommen mehr Follower als unbekannte
Wie wird der "Local clustering Coefficient" berechnet?
- Formel
- Berechnung der Graphen im Anhang
c(vi) = Knoten bei welchem wir den Koeffizient messen wollen
mi = tatsächlich direkt verlaufenden Kanten zwischen den Nachbarn
ki = Anzahl Nachbarn
Wie wird die "Closeness Zentralität" gemessen?
- Formel
- Lösung zum Graph im Anhang
D = distanz, kürzester Pfad zwischen v und w
Welches ist der wichtigeste Knoten in einem Netzwerk? (Most Important)
Der Knoten mit dem höchsten Zentralität Mass (Closeness Zentralität)
Wie wird die "Betweenness Zentralität" gemessen?
- Formel
- Lösung zum Graph im Anhang
Sag aus, wie viele Knoten benötigen werden um von einem Knoten zu einem andern zu gelangen.
