KDD (Kap 5: Graph Mining)
KDD Kapitel 5: Graph Mining
KDD Kapitel 5: Graph Mining
Was sind Graphen? Erläutern Sie die speziellen Eigenschaften von Graphen.
Ein Graph ist eine spezielle Form der Datenrepräsentation. Es ist eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert.
Im Grunde genommen bestehen Graphen aus einer Menge von Knoten (repräsentieren Objekte) und Kanten (repräsentieren Verbindungen zw. Objekten), letzteres kann mit Gewicht versehen werden.
Graphen können durch eine Adjazenzmatrix repräsentiert werden (Knoten als zeilen und Spalten).
Was ist ein bipartiter Graph?
Bipartiter Graph: Graph mit 2 Mengen von Knoten.
Was ist eine Zusammenhangskomponente?
Zusammenhangskomponente:
Knotenmenge, in der von jedem Knoten aus jeder andere Knoten über einen Pfad erreichbar ist.
Was ist der Durchmesser eines Graphen?
Durchmesser:
Maximum der Abstände zweier Knoten ("längster kürzester Pfad"). Wird ermittelt durch: bestimme für jeden Knoten den Abstand zum am weitsten entfernten Knoten -> Maximum. Abschätzung durch Sampling.
Was ist der Knotengrad?
Knotengrad:
Anzahl der verbundenen Knoten. Bei gerichteten Graphen: Unterscheidung in Eingangs- und Ausgangsgrad.
Was ist Traversierung? Erläutern Sie kurz die beiden bekanntesten Verfahren.
Traversierung:
Verfahren, die eine Route bestimmen, bei der jeder Knoten und jede Kante eines baumförmigen Graphen genau einmal besucht wird. Die beiden bekanntesten Verfahren sind Tiefensuche und Breitensuche.
Tiefensuche (DFS): zunächst rekursiv alle Kindknoten besuchen bevor alle Geschwisterknoten besucht werden
- Bestimmung der Zusammenhangskomponente
- Wegsuche um Labyrinth
Breitensuche (BFS): zunächst alle Geschwisterknoten besuchen bevor die Kindknoten besucht werden
- Bestimmung des kürzesten Weges
Was ist Social Network Analysis (SNA) und welche zentralen Aufgaben hat sie?
Die soziale Netzwerkanalyse ist eine Methode der empirischen Sozialforschung zur Erfassung und Analyse sozialer Beziehungen zwischen Individuen, wie soziale Position und Rolle, und sozialer Netzwerke.
- Zentralitätsanalyse: Identifikation der „wichtigsten“ Akteure -> sozialer Einfluss
- Erkennung von Communities: Analyse von Netzwerkstrukturen und Topologie
- Rollenanalyse: Rolle verschiedener Akteure in Interaktionen, z.B. „Brücke“ zwischen verschiedenen Communities
- Modellierung von Netzen: Repräsentation der Muster und Eigenschaften der Netze für Simulationen
- Informationsdiffusion: Analyse der Propagierung von Informationen (z.B. Dynamik, Infektion)
- Klassifikation und Ausreißererkennung: Erkennung spezieller Akteure durch zusätzliche Knoteninfos (z.B. Terrorabwehr)
- Virales Marketing und Linkprädiktion: Identifikation einer kleinen Gruppe von Akteuren auf Basis der Zentralitätsanalyse, Community-Strukturen und Diffusionsprozesse für Marketing
Was sind skalenfreie Netzwerke bzw. Netze?
Skalenfreie oder Skaleninvariante Netzwerke oder Netze sind komplexe Netzwerke, deren Anzahl von Verbindungen pro Knoten nach einem Potenzgesetz (power law) verteilt sind. Potenzgesetze sind skaleninvariant bzgl. Streckung oder Stauchung des Maßstabes der Variablen.
Die Verteilung von Knoten und die Anzahl k von Verbindungen folgt einem Potenzgesetz (power law).
Erläutern Sie "power law".
In der Mathematik sind Potenzgesetze (engl. power laws) Gesetzmäßigkeiten, die die Form eines Monoms haben: y = a * xb
Sie gehören zu den Skalengesetzen und beschreiben die Skaleninvarianz vieler natürlicher Phänomene. Sie treten beispielsweise im Zusammenhang mit Worthäufigkeiten (Zipfsches Gesetz) oder menschlicher Wahrnehmung (Stevenssche Potenzfunktion) auf. Pareto-Verteilungen sind ebenfalls Potenzgesetze.
zB: Anzahl Staädte, die eine bestimmte Bevölkerungsgröße haben (s.Abb.)
Erläutern Sie das "small-world"-Phänomen.
Das Kleine-Welt-Phänomen (engl. small world phenomenon, manchmal auch small world paradigm) ist ein von Stanley Milgram 1967 geprägter sozialpsychologischer Begriff, der innerhalb der sozialen Vernetzung in der modernen Gesellschaft den hohen Grad abkürzender Wege durch persönliche Beziehungen bezeichnet. Er bezeichnet eine Hypothese, nach der jeder Mensch (sozialer Akteur) auf der Welt mit jedem anderen über eine überraschend kurze Kette von Bekanntschaftsbeziehungen verbunden ist. Dies ist möglich, obwohl die „Dichte“ des sozialen Netzwerks aller Akteure – gemessen als das Verhältnis der realen zu den rechnerisch möglichen Kontakten der Kontaktpersonen eines jedweden Akteurs – extrem gering ist, nämlich nahe null.
Erläutern Sie "small-world"-Graphen.
für Netzwerktheorie: Kombination von
- Eigenschaften zufälliger Graphen (geringer Durchmesser -> kurze Wege)
- hoher Clustering-Grad / Transitivität: hohe Wahrscheinlichkeit, dass zwei Akteure mit einem Link zu einer dritten Person auch direkt verbunden sind
Erläutern Sie das Modell von Watts & Strogatz.
Die Watt-Strogatz Modell ist eine Zufalls-Graph Generierungs-Modell, das Graphen mit Kleine-Welt-Eigenschaften, einschließlich kurze durchschnittliche Weglänge und hohe Clustering produziert.
„Rewiring“-Prozedur: Start mit regulärem Ring
- Wähle Knoten und Kante zum nächsten Nachbarn: mit Wahrscheinlichkeit p ersetze Kante durch Kante zu einem zufälliggewähltem Knoten des Rings (keine Duplikate)
- Wiederhole für gesamten Ring in Uhrzeigersinn
- in nächster Runde behandle Kanten zu zweitnächsten Nachbarn
- für n Knoten mit jeweils k Nachbarn: k/2 Runden
Welche Ansätze zur Erkennung / Identifikation von Communities gibt es?
- knoten-zentriert: jeder Knoten einer Gruppe muss bestimmte Bedingungen erfüllen
- gruppen-zentriert: Betrachtung der Verbindungen innerhalb einer Gruppe
- netzwerk-zentriert: Betrachtung der Verbindungen des gesamten Netzes
- hierarchie-zentriert: hierarchisches Clustering
- divisiv (schrittweises Entfernen von Kanten, die wahrscheinlich verschiedene Communities miteinander verbinden)
- agglomerativ (schrittweises Verschmelzen von Communities)
Was ist Link Mining und was sind typische Aufgaben des Link Mining?
Berücksichtigung von Links (Beziehungen zwischen Objekten als "First-Class-Citizens" in der Datenanalyse)
Typische Aufgaben:
- objekt-bezogen: Link-basiertes Ranking von Objekten, Link-basierte Klassifikation, Clustering, Entity Resolution
- link-bezogen: Link-Prediction
- graph-bezogen: Subgraph-Entdeckung, Klassifikation von Graphen, Modellgenerierung
Erläutern Sie Link Prediction.
Formeln und Gesetzmäßigkeiten, die Entwicklungen vorhersagen, wann und zwischen welchen Knoten eine neue Kante entsteht, die Interaktion, Kollaboration oder Einfluss zwischen zwei Entitäten bedeutet.
Bsp: Die Frage nach Kollaboration zwischen zwei Autoren die möglicherweise zusammen einen Artikel schreiben, dass dann im Falle dass es eintritt als Kante symbolisiert wird.
Gegeben ist eine Momentaufnahme (Snapshot) eines Graphen zu einem bestimmten Zeitpunkt t. Gesucht wird die Vorhersage der Kanten, die bis zum Zeitpunkt t' > t wahrscheinlich hinzugefügt werden.
Hierzu werden Strukturinformationen genutzt durch bestimmte Algorithmen, die das Ähnlichkeitsmaß zwischen x und y basierend auf dem Netzwerk berechnen. Die Algorithmen lassen sich in zwei Kategorien unterscheiden:
- die, die die Wahrscheinlichkeit, dass zwei Knoten eine Kante bilden, über die gemeinsamen Nachbarn der beiden Knoten berechnet (Nutzung von Nachbarschaftsinformationen)
und/oder
- die, die die kürzesten Wege zwischen den beiden Knoten zur Berechnung hernehmen (Nutzung von Pfadinformationen).
- oder beide davon.
Welches sind die Link-Prediciton Algorithmen, welche Nachbarschaftsinformationen nutzen?
- Common Neighbours (gemeinsame Nachbarn)
- Jaccard-Koeffizient
- Preferential Attachment
Welches sind die Link-Prediciton Algorithmen, welche Pfadinformationen nutzen?
- Kürzester Pfad
- Katz
- SimRank
-
- 1 / 17
-
Lernkarten
Was sind Graphen? Erläutern Sie die speziellen Eigenschaften von Graphen.
Ein Graph ist eine spezielle Form der Datenrepräsentation. Es ist eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert.
Im Grunde genommen bestehen Graphen aus einer Menge von Knoten (repräsentieren Objekte) und Kanten (repräsentieren Verbindungen zw. Objekten), letzteres kann mit Gewicht versehen werden.
Graphen können durch eine Adjazenzmatrix repräsentiert werden (Knoten als zeilen und Spalten).
Was ist ein bipartiter Graph?
Bipartiter Graph: Graph mit 2 Mengen von Knoten.
Was ist eine Zusammenhangskomponente?
Zusammenhangskomponente:
Knotenmenge, in der von jedem Knoten aus jeder andere Knoten über einen Pfad erreichbar ist.
Was ist der Durchmesser eines Graphen?
Durchmesser:
Maximum der Abstände zweier Knoten ("längster kürzester Pfad"). Wird ermittelt durch: bestimme für jeden Knoten den Abstand zum am weitsten entfernten Knoten -> Maximum. Abschätzung durch Sampling.
Was ist der Knotengrad?
Knotengrad:
Anzahl der verbundenen Knoten. Bei gerichteten Graphen: Unterscheidung in Eingangs- und Ausgangsgrad.
Was ist Traversierung? Erläutern Sie kurz die beiden bekanntesten Verfahren.
Traversierung:
Verfahren, die eine Route bestimmen, bei der jeder Knoten und jede Kante eines baumförmigen Graphen genau einmal besucht wird. Die beiden bekanntesten Verfahren sind Tiefensuche und Breitensuche.
Tiefensuche (DFS): zunächst rekursiv alle Kindknoten besuchen bevor alle Geschwisterknoten besucht werden
- Bestimmung der Zusammenhangskomponente
- Wegsuche um Labyrinth
Breitensuche (BFS): zunächst alle Geschwisterknoten besuchen bevor die Kindknoten besucht werden
- Bestimmung des kürzesten Weges
Was ist Social Network Analysis (SNA) und welche zentralen Aufgaben hat sie?
Die soziale Netzwerkanalyse ist eine Methode der empirischen Sozialforschung zur Erfassung und Analyse sozialer Beziehungen zwischen Individuen, wie soziale Position und Rolle, und sozialer Netzwerke.
- Zentralitätsanalyse: Identifikation der „wichtigsten“ Akteure -> sozialer Einfluss
- Erkennung von Communities: Analyse von Netzwerkstrukturen und Topologie
- Rollenanalyse: Rolle verschiedener Akteure in Interaktionen, z.B. „Brücke“ zwischen verschiedenen Communities
- Modellierung von Netzen: Repräsentation der Muster und Eigenschaften der Netze für Simulationen
- Informationsdiffusion: Analyse der Propagierung von Informationen (z.B. Dynamik, Infektion)
- Klassifikation und Ausreißererkennung: Erkennung spezieller Akteure durch zusätzliche Knoteninfos (z.B. Terrorabwehr)
- Virales Marketing und Linkprädiktion: Identifikation einer kleinen Gruppe von Akteuren auf Basis der Zentralitätsanalyse, Community-Strukturen und Diffusionsprozesse für Marketing
Was sind skalenfreie Netzwerke bzw. Netze?
Skalenfreie oder Skaleninvariante Netzwerke oder Netze sind komplexe Netzwerke, deren Anzahl von Verbindungen pro Knoten nach einem Potenzgesetz (power law) verteilt sind. Potenzgesetze sind skaleninvariant bzgl. Streckung oder Stauchung des Maßstabes der Variablen.
Die Verteilung von Knoten und die Anzahl k von Verbindungen folgt einem Potenzgesetz (power law).
Erläutern Sie "power law".
In der Mathematik sind Potenzgesetze (engl. power laws) Gesetzmäßigkeiten, die die Form eines Monoms haben: y = a * xb
Sie gehören zu den Skalengesetzen und beschreiben die Skaleninvarianz vieler natürlicher Phänomene. Sie treten beispielsweise im Zusammenhang mit Worthäufigkeiten (Zipfsches Gesetz) oder menschlicher Wahrnehmung (Stevenssche Potenzfunktion) auf. Pareto-Verteilungen sind ebenfalls Potenzgesetze.
zB: Anzahl Staädte, die eine bestimmte Bevölkerungsgröße haben (s.Abb.)
Erläutern Sie das "small-world"-Phänomen.
Das Kleine-Welt-Phänomen (engl. small world phenomenon, manchmal auch small world paradigm) ist ein von Stanley Milgram 1967 geprägter sozialpsychologischer Begriff, der innerhalb der sozialen Vernetzung in der modernen Gesellschaft den hohen Grad abkürzender Wege durch persönliche Beziehungen bezeichnet. Er bezeichnet eine Hypothese, nach der jeder Mensch (sozialer Akteur) auf der Welt mit jedem anderen über eine überraschend kurze Kette von Bekanntschaftsbeziehungen verbunden ist. Dies ist möglich, obwohl die „Dichte“ des sozialen Netzwerks aller Akteure – gemessen als das Verhältnis der realen zu den rechnerisch möglichen Kontakten der Kontaktpersonen eines jedweden Akteurs – extrem gering ist, nämlich nahe null.
Erläutern Sie "small-world"-Graphen.
für Netzwerktheorie: Kombination von
- Eigenschaften zufälliger Graphen (geringer Durchmesser -> kurze Wege)
- hoher Clustering-Grad / Transitivität: hohe Wahrscheinlichkeit, dass zwei Akteure mit einem Link zu einer dritten Person auch direkt verbunden sind
Erläutern Sie das Modell von Watts & Strogatz.
Die Watt-Strogatz Modell ist eine Zufalls-Graph Generierungs-Modell, das Graphen mit Kleine-Welt-Eigenschaften, einschließlich kurze durchschnittliche Weglänge und hohe Clustering produziert.
„Rewiring“-Prozedur: Start mit regulärem Ring
- Wähle Knoten und Kante zum nächsten Nachbarn: mit Wahrscheinlichkeit p ersetze Kante durch Kante zu einem zufälliggewähltem Knoten des Rings (keine Duplikate)
- Wiederhole für gesamten Ring in Uhrzeigersinn
- in nächster Runde behandle Kanten zu zweitnächsten Nachbarn
- für n Knoten mit jeweils k Nachbarn: k/2 Runden
Welche Ansätze zur Erkennung / Identifikation von Communities gibt es?
- knoten-zentriert: jeder Knoten einer Gruppe muss bestimmte Bedingungen erfüllen
- gruppen-zentriert: Betrachtung der Verbindungen innerhalb einer Gruppe
- netzwerk-zentriert: Betrachtung der Verbindungen des gesamten Netzes
- hierarchie-zentriert: hierarchisches Clustering
- divisiv (schrittweises Entfernen von Kanten, die wahrscheinlich verschiedene Communities miteinander verbinden)
- agglomerativ (schrittweises Verschmelzen von Communities)
Was ist Link Mining und was sind typische Aufgaben des Link Mining?
Berücksichtigung von Links (Beziehungen zwischen Objekten als "First-Class-Citizens" in der Datenanalyse)
Typische Aufgaben:
- objekt-bezogen: Link-basiertes Ranking von Objekten, Link-basierte Klassifikation, Clustering, Entity Resolution
- link-bezogen: Link-Prediction
- graph-bezogen: Subgraph-Entdeckung, Klassifikation von Graphen, Modellgenerierung
Erläutern Sie Link Prediction.
Formeln und Gesetzmäßigkeiten, die Entwicklungen vorhersagen, wann und zwischen welchen Knoten eine neue Kante entsteht, die Interaktion, Kollaboration oder Einfluss zwischen zwei Entitäten bedeutet.
Bsp: Die Frage nach Kollaboration zwischen zwei Autoren die möglicherweise zusammen einen Artikel schreiben, dass dann im Falle dass es eintritt als Kante symbolisiert wird.
Gegeben ist eine Momentaufnahme (Snapshot) eines Graphen zu einem bestimmten Zeitpunkt t. Gesucht wird die Vorhersage der Kanten, die bis zum Zeitpunkt t' > t wahrscheinlich hinzugefügt werden.
Hierzu werden Strukturinformationen genutzt durch bestimmte Algorithmen, die das Ähnlichkeitsmaß zwischen x und y basierend auf dem Netzwerk berechnen. Die Algorithmen lassen sich in zwei Kategorien unterscheiden:
- die, die die Wahrscheinlichkeit, dass zwei Knoten eine Kante bilden, über die gemeinsamen Nachbarn der beiden Knoten berechnet (Nutzung von Nachbarschaftsinformationen)
und/oder
- die, die die kürzesten Wege zwischen den beiden Knoten zur Berechnung hernehmen (Nutzung von Pfadinformationen).
- oder beide davon.
Welches sind die Link-Prediciton Algorithmen, welche Nachbarschaftsinformationen nutzen?
- Common Neighbours (gemeinsame Nachbarn)
- Jaccard-Koeffizient
- Preferential Attachment
Welches sind die Link-Prediciton Algorithmen, welche Pfadinformationen nutzen?
- Kürzester Pfad
- Katz
- SimRank
