KDD - Kapitel 5: Graph Mining
Lernkarteien zur "Knowledge Discovery in Databases (KDD)" Vorlesung bei Herrn Prof. Sattler, WS 2012/13 - TU Ilmenau.
Lernkarteien zur "Knowledge Discovery in Databases (KDD)" Vorlesung bei Herrn Prof. Sattler, WS 2012/13 - TU Ilmenau.
(Kapitel 5.1) Definieren Sie den Begriff "Graph". Welche Ziele können mit Graphen verfolgt werden und welche Anwendungsgebiete haben sie?
- Definition: Ein Graph ist eine spezielle Form der Datenrepräsentation, die Beziehungen zwischen Objekten darstellt.
- Mit Hilfe von Graphen können häufige Subgraphen gefunden werden und Communities aufgedeckt werden.
- Anwendungsgebiete:
- Web-Mining: Analyse von Muster in Web-Logs
- Netzwerktechnik: Analyse des E-Mail- oder Mobilfunk-Verkehrs
- Soziale Netzwerke: Identifikation von Eigenschaften und Communities
(Kapitel 5.1) Was versteht man unter einem Graph (im mathematischen Sinne)?
Ein Graph G ist wie folgt definiert: G = (V, E)
- V: Menge der Knoten
- E: Menge der Kanten
Die Kanten können evtl. gewichtet sein.
(Kapitel 5.1): Was versteht man unter einer Adjazenzmatrix?
Eine Adjazenzmatrix ist die Repräsentation von einem Graph durch eine Matrix. Dabei wird ein Graph mit n Knoten durch eine n*n-Matrix dargestellt. Um die Adjazenzmatrix zu erstellen, nummeriert man die Knoten von 1 bis n durch und trägt in die Matrix die Beziehungen der Knoten zueinander ein.
- Bei einem ungerichtetem Graph: Symmetrische Matrix
- Bei ungewichtetem Graph: Zellen bestehen nur aus 0 oder 1
(Kapitel 5.1): Was versteht man unter einem biparitem Graph?
Ein Graph heißt bipartit, falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine Kanten verlaufen.
=> Kanten existieren - vereinfacht ausgedrückt - nur zwischen verschiedenen Mengen.
(Kapitel 5.1): Was ist eine Zusammenhangskomponente?
Eine Zusammenhangskomponente ist eine Knotenmenge (Teilgraph), in der von jedem Knoten aus jeder andere Knoten über einen Pfad erreichbar ist.
(Kapitel 5.1): Was ist der Durchmesser in einem Graphen?
Der Durchmesser in einem Graph ist das Maximum der Abstände zweier Knoten ("längster kürzester Pfad").
(Kapitel 5.1): Was versteht man unter einem Knotengrad?
Der Knotengrad ist eine Eigenschaft eines Knotens und gibt die Anzahl der verbundenen Knoten an. Bei gerichteten Graphen unterscheidet man in Eingangs- und Ausgangsgrad.
(Kapitel 5.1): Wie funktioniert die Tiefensuche (DFS)?
Bei der Tiefensuche werden zunächst alle Kindknoten rekursiv besucht, bevor alle Geschwisterknoten besucht werden.
(Kapitel 5.1): Wie funktioniert die Breitensuche (BFS)?
Bei der Breitensuche werden zunächst alle Geschwisterknoten besucht, bevor die Kindknoten besucht werden.
(Kapitel 5.1): Was versteht man unter "Sozial Network Analysis"?
Sozial Network Analysis (SNA) ist die Untersuchung von Beziehungen zwischen Individuen, wie soziale Position und Rolle und soziale Strukturen (Freundschaftsbeziehungen).
(Kapitel 5.1): Nenne und beschreibe kurz die typischen Aufgaben von SNA.
- Zentralitätsanalyse: Identifikation von relevanten Personen, die einen zentralen Einfluss haben
- Erkennung von Communities: Analyse von Netzwerkstrukturen
- Rollenanalyse: Untersucht die Rolle verschiedener Akteure (z.B. "Brücke" zwischen verschiedenen Communities)
- Modellierung von Netzen: Repräsentation der Muster und Eigenschaften der Netzt für Simulationen
- Informationsdiffusion: Analyse der Propagierung von informationen
- Klassifikation und Ausreißererkennung: Erkennung spezieller Akteure durch zusätzliche Knoteninfos (z.B. zur Terrorabwehr)
- Virales Marketing und Linkprädiktion: Identifikation einer kleinen Gruppe von Akteuren auf Basis der Zentralitätsanalyse, Community-Strukturen und Diffusionsprozesse für das Marketing.
(Kapitel 5.2): Welche typischen Graph-Muster gibt es?
- Skalenfreie Netzwerke
- Small-World-Graphen
(Kapitel 5.2): Was versteht man unter einem "skalenfreien Netzwerk"?
Skalenfreie Netze weisen im Gegensatz zu anderen Netzwerken keine spezifische Anzahl von Links pro Knoten auf. Sie folgen vielmehr einem Potenzgesetz (power law*).
Gilt für ein Netzwerk das Power Law, so besitzt es sehr viele Knoten mit relativ wenigen Links und einige, die besonders stark verlinkt sind, sogenannte Hubs.
*Power-Law-Verteilung: Wahrscheinlichkeit nimmt mit x->∞ polynomiell ab ("long tail").
(Kapitel 5.2): Erläutere das Phänomen der Small-World-Graphen.
Das Phänomen der "kleinen Welt" stammt ursprünglich aus der Soziologie und besagt, dass eine Person über einen erstaunlich kurzen Weg mit jeder anderen Person verbunden ist.
In der Netzwerktheorie beduetet das, dass einzelne Objekte (z.B. Personen) als Knoten repräsentiert sind, zwischen denen eine Kante besteht, wenn zwischen ihnen eine Beziehung (z.B. Bekanntschaft) besteht.
Small-World-Graphen weisen im Wesentlichen zwei Eigenschaften auf:
- Transitivität:
Die Wahrscheinlichkeit, dass zwei Akteure mit einem Link zu einer dritten person auch direkt verbunden sind, ist sehr hoch. - Geringer Durchmesser:
Der Durchmesser dieser Netzwerke ist sehr klein. Das bedeutet, dass eine Nachricht, die über eine Kante zu seinen Nachbarknoten weitergereicht wird, in kürzester Zeit alle Knoten in einem Netzwerk erreicht hat.
(Kapitel 5.2): Mit welchen Maßen kann die Stärke des Small-World-Effektes gemessen werden?
- Durchmesser: Minimale Anzahl an Hops zum Erreichen aller verbundener Knoten
- Mittlerer Durchmesser: Durchschnittliche Länge aller kürzesten Wege
- Effektiver Durchmesser: Minimale Anzahl von Hops zum Erreichen von mindestens 90 % der verbundenen Knoten
(Kapitel 5.3): Was versteht man unter einer Community?
Eine Community ist eine Gruppe von Personen, die untereinander häufiger interagieren als mit Personen außerhalb der Gruppe (Transitivität).
(Kapitel 5.3): Wie kann die Stärke einer Community gemessen werden?
Die Stärke einer Community kann mit dem Clustering-Koeffizient gemessen werden. Er ist in der Graphentheorie also ein Maß für die Cliquenbildung bzw. für die Transitivität.
Sind alle Nachbarn eines Knotens paarweise verbunden, also jeder mit jedem, dann bilden sie eine Clique. Dies ist gleichbedeutend mit dem Begriff der Transitivität, denn innerhalb eine Clique gilt: Ist A mit B verbunden und A mit C, so sind auch B und C verbunden.
Der Clustering-Koeffizient ist definiert als das Verhältnis aus tatsächlichen Kanten zwischen einem Knoten di und den maximalen möglichen Kanten.
(Kapitel 5.3): Welche Ansätze zur Erkennung von Communities gibt es?
- Knoten-zentrierter Ansatz: Jeder Knoten einer Gruppe muss bestimmte Bedingungen erfüllen.
- Gruppen-zentrierter Ansatz: Betrachtung der Verbindungen innerhalbt einer Gruppe
- Netzwerk-zentrierter Ansatz: Betrachtung der Verbindungen des gesamten Netzes
- Hierarchie-zentrierter Ansatz: Hierarchisches Clustering
(Kapitel 5.3): Erläutere grob die Knoten-zentrierte Community-Erkennung.
Das Ziel der knoten-zentrierten Community-Erkennung ist das Finden maximaler Cliquen. Dies geschieht über die Erreichbarkeit im Graphen: Existieren Pfade zwischen zwei Knoten, dann gehören beide Knoten zur gleichen Community (mit Begrenzung der Distanz).
- Innerhalb einer Community sollen Akteure benachbart zu einer großen Anzahl von Community-Mitgliedern sein
- Knoten sollen innerhalb einer Gruppe mehr Verbindungen als außerhalb haben.
(Kapitel 5.3): Erläutere kurz die hierarchie-zentrierte Community-Erkennung.
Man unterscheidet bei der hierarchie-zentrierten Community-Erkennung zwischen divisives hierarchisches Clustering und agglomeratives hierarchisches Clustering.
- Divisives hierarchisches Clustering:
- Schrittweises Entfernen von Kanten, die mit einer gewissen Wahrscheinlichkeit verschiedene Communities mitenander verbinden
- Bestimmung der Anzahl der kürzesten Pfade zwischen Paaren von Knoten entlang der Kante
- Agglomeratives hierarchisches Clustering:
- Schrittweise Verschmelzen von Communities anhand der Modularität
- Modularität = Qualität der Teilung eines Netzes, d.h. Abstand der Interaktion (Kanten innerhalb einer Community) vom Fall eines zufälligen Graphen
-
- 1 / 20
-
Cartes-fiches
(Kapitel 5.1) Definieren Sie den Begriff "Graph". Welche Ziele können mit Graphen verfolgt werden und welche Anwendungsgebiete haben sie?
- Definition: Ein Graph ist eine spezielle Form der Datenrepräsentation, die Beziehungen zwischen Objekten darstellt.
- Mit Hilfe von Graphen können häufige Subgraphen gefunden werden und Communities aufgedeckt werden.
- Anwendungsgebiete:
- Web-Mining: Analyse von Muster in Web-Logs
- Netzwerktechnik: Analyse des E-Mail- oder Mobilfunk-Verkehrs
- Soziale Netzwerke: Identifikation von Eigenschaften und Communities
(Kapitel 5.1) Was versteht man unter einem Graph (im mathematischen Sinne)?
Ein Graph G ist wie folgt definiert: G = (V, E)
- V: Menge der Knoten
- E: Menge der Kanten
Die Kanten können evtl. gewichtet sein.
(Kapitel 5.1): Was versteht man unter einer Adjazenzmatrix?
Eine Adjazenzmatrix ist die Repräsentation von einem Graph durch eine Matrix. Dabei wird ein Graph mit n Knoten durch eine n*n-Matrix dargestellt. Um die Adjazenzmatrix zu erstellen, nummeriert man die Knoten von 1 bis n durch und trägt in die Matrix die Beziehungen der Knoten zueinander ein.
- Bei einem ungerichtetem Graph: Symmetrische Matrix
- Bei ungewichtetem Graph: Zellen bestehen nur aus 0 oder 1
(Kapitel 5.1): Was versteht man unter einem biparitem Graph?
Ein Graph heißt bipartit, falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine Kanten verlaufen.
=> Kanten existieren - vereinfacht ausgedrückt - nur zwischen verschiedenen Mengen.
(Kapitel 5.1): Was ist eine Zusammenhangskomponente?
Eine Zusammenhangskomponente ist eine Knotenmenge (Teilgraph), in der von jedem Knoten aus jeder andere Knoten über einen Pfad erreichbar ist.
(Kapitel 5.1): Was ist der Durchmesser in einem Graphen?
Der Durchmesser in einem Graph ist das Maximum der Abstände zweier Knoten ("längster kürzester Pfad").
(Kapitel 5.1): Was versteht man unter einem Knotengrad?
Der Knotengrad ist eine Eigenschaft eines Knotens und gibt die Anzahl der verbundenen Knoten an. Bei gerichteten Graphen unterscheidet man in Eingangs- und Ausgangsgrad.
(Kapitel 5.1): Wie funktioniert die Tiefensuche (DFS)?
Bei der Tiefensuche werden zunächst alle Kindknoten rekursiv besucht, bevor alle Geschwisterknoten besucht werden.
(Kapitel 5.1): Wie funktioniert die Breitensuche (BFS)?
Bei der Breitensuche werden zunächst alle Geschwisterknoten besucht, bevor die Kindknoten besucht werden.
(Kapitel 5.1): Was versteht man unter "Sozial Network Analysis"?
Sozial Network Analysis (SNA) ist die Untersuchung von Beziehungen zwischen Individuen, wie soziale Position und Rolle und soziale Strukturen (Freundschaftsbeziehungen).
(Kapitel 5.1): Nenne und beschreibe kurz die typischen Aufgaben von SNA.
- Zentralitätsanalyse: Identifikation von relevanten Personen, die einen zentralen Einfluss haben
- Erkennung von Communities: Analyse von Netzwerkstrukturen
- Rollenanalyse: Untersucht die Rolle verschiedener Akteure (z.B. "Brücke" zwischen verschiedenen Communities)
- Modellierung von Netzen: Repräsentation der Muster und Eigenschaften der Netzt für Simulationen
- Informationsdiffusion: Analyse der Propagierung von informationen
- Klassifikation und Ausreißererkennung: Erkennung spezieller Akteure durch zusätzliche Knoteninfos (z.B. zur Terrorabwehr)
- Virales Marketing und Linkprädiktion: Identifikation einer kleinen Gruppe von Akteuren auf Basis der Zentralitätsanalyse, Community-Strukturen und Diffusionsprozesse für das Marketing.
(Kapitel 5.2): Welche typischen Graph-Muster gibt es?
- Skalenfreie Netzwerke
- Small-World-Graphen
(Kapitel 5.2): Was versteht man unter einem "skalenfreien Netzwerk"?
Skalenfreie Netze weisen im Gegensatz zu anderen Netzwerken keine spezifische Anzahl von Links pro Knoten auf. Sie folgen vielmehr einem Potenzgesetz (power law*).
Gilt für ein Netzwerk das Power Law, so besitzt es sehr viele Knoten mit relativ wenigen Links und einige, die besonders stark verlinkt sind, sogenannte Hubs.
*Power-Law-Verteilung: Wahrscheinlichkeit nimmt mit x->∞ polynomiell ab ("long tail").
(Kapitel 5.2): Erläutere das Phänomen der Small-World-Graphen.
Das Phänomen der "kleinen Welt" stammt ursprünglich aus der Soziologie und besagt, dass eine Person über einen erstaunlich kurzen Weg mit jeder anderen Person verbunden ist.
In der Netzwerktheorie beduetet das, dass einzelne Objekte (z.B. Personen) als Knoten repräsentiert sind, zwischen denen eine Kante besteht, wenn zwischen ihnen eine Beziehung (z.B. Bekanntschaft) besteht.
Small-World-Graphen weisen im Wesentlichen zwei Eigenschaften auf:
- Transitivität:
Die Wahrscheinlichkeit, dass zwei Akteure mit einem Link zu einer dritten person auch direkt verbunden sind, ist sehr hoch. - Geringer Durchmesser:
Der Durchmesser dieser Netzwerke ist sehr klein. Das bedeutet, dass eine Nachricht, die über eine Kante zu seinen Nachbarknoten weitergereicht wird, in kürzester Zeit alle Knoten in einem Netzwerk erreicht hat.
(Kapitel 5.2): Mit welchen Maßen kann die Stärke des Small-World-Effektes gemessen werden?
- Durchmesser: Minimale Anzahl an Hops zum Erreichen aller verbundener Knoten
- Mittlerer Durchmesser: Durchschnittliche Länge aller kürzesten Wege
- Effektiver Durchmesser: Minimale Anzahl von Hops zum Erreichen von mindestens 90 % der verbundenen Knoten
(Kapitel 5.3): Was versteht man unter einer Community?
Eine Community ist eine Gruppe von Personen, die untereinander häufiger interagieren als mit Personen außerhalb der Gruppe (Transitivität).
(Kapitel 5.3): Wie kann die Stärke einer Community gemessen werden?
Die Stärke einer Community kann mit dem Clustering-Koeffizient gemessen werden. Er ist in der Graphentheorie also ein Maß für die Cliquenbildung bzw. für die Transitivität.
Sind alle Nachbarn eines Knotens paarweise verbunden, also jeder mit jedem, dann bilden sie eine Clique. Dies ist gleichbedeutend mit dem Begriff der Transitivität, denn innerhalb eine Clique gilt: Ist A mit B verbunden und A mit C, so sind auch B und C verbunden.
Der Clustering-Koeffizient ist definiert als das Verhältnis aus tatsächlichen Kanten zwischen einem Knoten di und den maximalen möglichen Kanten.
(Kapitel 5.3): Welche Ansätze zur Erkennung von Communities gibt es?
- Knoten-zentrierter Ansatz: Jeder Knoten einer Gruppe muss bestimmte Bedingungen erfüllen.
- Gruppen-zentrierter Ansatz: Betrachtung der Verbindungen innerhalbt einer Gruppe
- Netzwerk-zentrierter Ansatz: Betrachtung der Verbindungen des gesamten Netzes
- Hierarchie-zentrierter Ansatz: Hierarchisches Clustering
(Kapitel 5.3): Erläutere grob die Knoten-zentrierte Community-Erkennung.
Das Ziel der knoten-zentrierten Community-Erkennung ist das Finden maximaler Cliquen. Dies geschieht über die Erreichbarkeit im Graphen: Existieren Pfade zwischen zwei Knoten, dann gehören beide Knoten zur gleichen Community (mit Begrenzung der Distanz).
- Innerhalb einer Community sollen Akteure benachbart zu einer großen Anzahl von Community-Mitgliedern sein
- Knoten sollen innerhalb einer Gruppe mehr Verbindungen als außerhalb haben.
(Kapitel 5.3): Erläutere kurz die hierarchie-zentrierte Community-Erkennung.
Man unterscheidet bei der hierarchie-zentrierten Community-Erkennung zwischen divisives hierarchisches Clustering und agglomeratives hierarchisches Clustering.
- Divisives hierarchisches Clustering:
- Schrittweises Entfernen von Kanten, die mit einer gewissen Wahrscheinlichkeit verschiedene Communities mitenander verbinden
- Bestimmung der Anzahl der kürzesten Pfade zwischen Paaren von Knoten entlang der Kante
- Agglomeratives hierarchisches Clustering:
- Schrittweise Verschmelzen von Communities anhand der Modularität
- Modularität = Qualität der Teilung eines Netzes, d.h. Abstand der Interaktion (Kanten innerhalb einer Community) vom Fall eines zufälligen Graphen
