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
-
Cartes-fiches
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
Beschreibe und zeichne "asymetrisch-Beziehung" und eine "antisymmetrische-Beziehung" im einem Graphen.
a ist älter als b, somit kann b nicht älter sein als a.
und a kann nicht älter als a sein.
sowie b nicht älter als b sein kann.
Was sind Mehrfachkanten?
Zwei oder mehr Kanten welche die Selben Endknoten haben.
Was sind multiple Knoten?
Knoten welche mit zwei oder mehr Kanten verbunden sind.
Müssen sie auch gerichtet sein?
Was ist ein zusammenhängender Graph?
Ein Graph heist zusammenhängend falls jede zwei Knoten durch ein pfad verbunden sind.
Wie lautet die Definition eines einfach / schlichten Graphen?
Ein Graph der Schleifenfrei und keine multiplen Knoten besitzt heisst einfach / schlicht.
Wie lautet die Mathematische Deifiton eines Graphen?
G := (V, E)
G ist ein Tupel
V ist die Knotenmenge
E ist die Kantenmenge welche Knoten verbindet
Was ist der Unterschied zwischen runden Klammern und geschweiften Kammern?
E := { {1,2}, {1,5} }
E := { (1,2), (1,5) }
E := { {1,2}, {1,5} }
Geschweifteklammern = Ungerichtet
E := { (1,2), (1,5) }
Rundeklammern = Gerichtet
Was ist eine Gewichtsfunktion?
w: E -> R
Eine Funktion welche Kanten auf reelle Zahlen abbildet. --> Gewichtete Kanten
Wie lautet V und E für diesen Graphen?
V = {1,2,3}
E = { {1,2}, {2,3} }
Wie lautet das Knotenalphabet für diesen Graphen?
\(A_V = \{AC, BC, CF \}\)
Wie lautet die Knotenmarkierungsfunktion \(\int_v: V \to A_v\) für diesen Graphen?
\(\int_v(2) = BC\)
\(\int_v(1) = AC\)
Wie lautet das Kantenalphabet für diesen Graphen?
\(A_E = \{ \pi , \sqrt 2 \}\)
Wie lautet die Kantenmarkierungsfunktion \(\int_E: E \to A_E\) für diesen Graphen?
\(\int_E(e_1) = \pi\)
\(\int_E(e_2) = \sqrt2\)
Was ist ein stark zusammenhängender gerichteter Graph?
Ein gerichteter Graph ist stark zusammenhaengend falls es ein gerichteten Pfad von einem beliebigen Knoten zu jedem
anderen Knoten gibt.
Was bedeutet Inzident?
Kanten welche an den gleichen Knoten anschliessen sind Inzidente-Kanten.
Kanten-Knoten Verbindung = Inzidente-Kanten
Wie definiert sich der Grad eines Knotens?
- In-Degree: Anzahl eingehender Kanten
- Out-Degree: Anzahl ausgehender Kanten
Degree = indeg + outdeg
Wie lautet die Defintion eines "Pfades"?
Ein Pfad ist ein walk/Weg in dem alle Kanten und Knoten verschieden sind.
Wie lautet die Defintion eines "Zyklus / Kreis"?
Ein Zyklus ist ein geschlossener walk/Weg in dem alle Kanten verschieden sind.
Start- und End-Knoten sind gleich.
Was ist ein regulärer Graph?
- Zusammenhängend
- Alle Knoten haben den selben Grad
Der Grad gibt die regularität an.
Beispiel: Grad 3 -> 3-Regilär-Graph
Was ist ein Vollständiger Graph?
- Jeder Knoten ist mit jedem anden Knoten verbunden
Die Vollständigkeit wird mit K + die Anzahl Knoten angegben.
