Mining Structure from Graphs Flashcards
Nenn Similarity measures für Clustering Graphs
- Geodesic distances
- Structural Similarity
Was sind geodesic distances?
distance along curved spaces
* May be approximated by adding many short straight
segments, using the Euclidean distance for each of these
Wie berechnet man die geodesic distance in einem Graphen?
Was ist die Eccentricity von einem Knoten v?
Was ist ein peripheral vertex?
Was ist der Radius von einem Graphen?
Was ist der Diameter eines Graphen?
Beschreib Graph Clustering über Sparset Cut
Trennen von einem Graphen in Subgraphen
Wie kann man eine Entscheidung für einen Cut beim Graph Clustering über Sparsest Cut treffen? Was ist eine gut Methode dafür?
- Bestimmen der Größe eiens Cuts über die Anzahl der Kanten.
- Min-cut (not good partition)
- Besser: Sparsity
Was ist Sparsity?
Methode um eine Entscheidung für den Cut bei Graph Clustering zu wählen
size of cut = anzahl an subgraphen
Wann ist ein cut sparsest?
A cut is sparsest if its sparsity is not greater than that of any other cut
Was ist modularity beim Graphclustering?
The modularity of a clustering assesses the quality of the clustering
Wie berechnet man die modularity?
Challenges of Finding Good Cuts
Was sind Herausforderungen für Graph Clustering?
Welche Ansätze gibt es für Graph Clustering?
- Methods specifically designed for clustering graphs
-> Search the graph to find well-connected components as clusters - Using generic clustering methods for high-dimensional data
-> Extract a similarity/affinity matrix
Wie bestimmt man die structural similarity?
SCAN: Structural Clustering Algorithm for Networks
Zwischen welchen Individuals unterscheidet man?
- Individuals in a tight social group, or clique
- Individuals who are hubs
- Individuals who are outliers
SCAN: Structural Clustering Algorithm for Networks
Beschreib Individuals in a tight social group, or clique
Individuals in a tight social group, or clique, know many of the same people, regardless of the size of the group
SCAN: Structural Clustering Algorithm for Networks
Beschreib Individuals who are hubs
Individuals who are hubs know many people in different groups but belong to no single group. E.g., politicians bridge multiple groups
SCAN: Structural Clustering Algorithm for Networks
Beschreib Individuals who are outliers
Individuals who are outliers reside at the margins of society. E.g., hermits know few people and belong to no group
Was bedeutet ein Wert von 1 für die Structural Similarity?
Die Nachbarschaft zweier Knoten überdecken sich komplett
Wie ist eine epsilon-neighborhood definiert?
Wie ist ein Vertex-CORE definiert?
Wenn epsilon größer wird, wie verändern sich die Clustergrößen?
Sie werden kleiner
Wenn mü größer wird, wie verändern sich die Cluster?
Sie haben eine höhere minimale Clustergröße -> ergo mehrere Outliers (Knoten, die keine Cluster werden können)
Wie ist direct structure reachable definiert?
Was ist eine transitive closure?
Die transitive Hülle einer Relation R auf einer Menge X ist die kleinste transitive Relation, die R enthält
* In der Graphentheorie: Sie kann als Datenstruktur verstanden werden, die Erreichbarkeitsfragen in einem Graphen beantwortet. Sie zeigt, ob man von einem Knoten zu einem anderen über einen oder mehrere Schritte gelangen kann
Wie ist structure reachable definiert?
Wie ist structure connected definiert?
Wie ist ein structure-connected cluster C definiert?
Was ist Chinese Whispers?
Beschreib den Chinese Whispers Algorithm
selction by majority vote
Definiere die Energy Function für Chinese Whispers. Was passiert bei einem Update einer Klasse von einem Knoten?
Wie kann man verhindern, dass Chinese Whispers dazu führt, dass alle Knoten der gleichen Klasse angehören?
Mit negativen Gewichten
Was ist spectral clustering?
Was ist eine affinity matrix? Welche Eigenschaften hat sie?
Beschreib die Idee des Spectral Clusterings anhand von affinity matrizen
Wie berechnet man die Affinity Matrix bei gegebenen Datenpunkten?
Wie normalisiert man eine affinity matrix?
Wie berechnet man die Matrix D zum normalisieren einer affinity matrix?
Spectral Clustering Algorithm
Was tut man im Anschluss mit der Matrix L, der normalisierten affinity matrix?
Spectral Clustering Algorithm
Nachdem man die Matrix X mit den k Eigenvektoren als Spalten bestimmt hat, was muss man als nächstes tun?
Spectral Clustering Algorithm
Wie geht man vor, nachdem man Renormalisiert hat?
Man wendet zum Beispiel k-means an, um cluster zu bilden
Spectral Clustering
Is the Davies-Bouldin index a good measure
for these kinds of clusters?
No! It compares distances of points to mean versus distances between means (in this example, means are all same!)
Spectral Clustering: Choice of k
Welche Heuristik wird genutzt, um das optimale k zu finden?
Was bedeutet folgendes?
Was bedeutet folgendes?
Wodurch kann ein semantisches Netzwerk für knowledge representation- and programming languages repräsentiert werden?
by a set of triplets
Was ist die Matching rule für eine query Q that matches a database D?
Was sind Probabilistic Graphical Models?
Modelling of observations and their relationships
Beschreib Bayes Theorem
Was ist ein Bayesian Belief Network?
Beschreib “Conditional Independence” in Bayesian Belief Network
Beschreib “Explaining away” in Bayesian Belief Network
Was lösen Bayesian Networks im Bezug auf Aufwand?
Wie werden Bayesian Networks konstruiert?
Wie trainiert man Bayesian Networks?
