Mining Structure from Graphs

Question 1

Nenn Similarity measures für Clustering Graphs

Answer 1

• Geodesic distances
• Structural Similarity

Question 2

Was sind geodesic distances?

Answer 2

distance along curved spaces
* May be approximated by adding many short straight
segments, using the Euclidean distance for each of these

Question 3

Wie berechnet man die geodesic distance in einem Graphen?

Answer 3

Question 4

Was ist die Eccentricity von einem Knoten v?

Answer 4

Question 5

Was ist ein peripheral vertex?

Answer 5

Question 6

Was ist der Radius von einem Graphen?

Answer 6

Question 7

Was ist der Diameter eines Graphen?

Answer 7

Question 8

Beschreib Graph Clustering über Sparset Cut

Answer 8

Trennen von einem Graphen in Subgraphen

Question 9

Wie kann man eine Entscheidung für einen Cut beim Graph Clustering über Sparsest Cut treffen? Was ist eine gut Methode dafür?

Answer 9

• Bestimmen der Größe eiens Cuts über die Anzahl der Kanten.
• Min-cut (not good partition)
• Besser: Sparsity

Question 10

Was ist Sparsity?

Answer 10

Methode um eine Entscheidung für den Cut bei Graph Clustering zu wählen

size of cut = anzahl an subgraphen

Question 11

Wann ist ein cut sparsest?

Answer 11

A cut is sparsest if its sparsity is not greater than that of any other cut

Question 12

Was ist modularity beim Graphclustering?

Answer 12

The modularity of a clustering assesses the quality of the clustering

Question 13

Wie berechnet man die modularity?

Answer 13

Question 14

Challenges of Finding Good Cuts

Was sind Herausforderungen für Graph Clustering?

Answer 14

Question 15

Welche Ansätze gibt es für Graph Clustering?

Answer 15

1. Methods specifically designed for clustering graphs
   -> Search the graph to find well-connected components as clusters
2. Using generic clustering methods for high-dimensional data
   -> Extract a similarity/affinity matrix

Question 16

Wie bestimmt man die structural similarity?

Answer 16

Question 17

SCAN: Structural Clustering Algorithm for Networks

Zwischen welchen Individuals unterscheidet man?

Answer 17

• Individuals in a tight social group, or clique
• Individuals who are hubs
• Individuals who are outliers

Question 18

SCAN: Structural Clustering Algorithm for Networks

Beschreib Individuals in a tight social group, or clique

Answer 18

Individuals in a tight social group, or clique, know many of the same people, regardless of the size of the group

Question 19

SCAN: Structural Clustering Algorithm for Networks

Beschreib Individuals who are hubs

Answer 19

Individuals who are hubs know many people in different groups but belong to no single group. E.g., politicians bridge multiple groups

Question 20

SCAN: Structural Clustering Algorithm for Networks

Beschreib Individuals who are outliers

Answer 20

Individuals who are outliers reside at the margins of society. E.g., hermits know few people and belong to no group

Question 21

Was bedeutet ein Wert von 1 für die Structural Similarity?

Answer 21

Die Nachbarschaft zweier Knoten überdecken sich komplett

Question 22

Wie ist eine epsilon-neighborhood definiert?

Answer 22

Question 23

Wie ist ein Vertex-CORE definiert?

Answer 23

Question 24

Wenn epsilon größer wird, wie verändern sich die Clustergrößen?

Answer 24

Sie werden kleiner

Question 25

Wenn mü größer wird, wie verändern sich die Cluster?

Answer 25

Sie haben eine höhere minimale Clustergröße -> ergo mehrere Outliers (Knoten, die keine Cluster werden können)

Question 26

Wie ist `direct structure reachable` definiert?

Answer 26

Question 27

Was ist eine transitive closure?

Answer 27

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

Question 28

Wie ist `structure reachable` definiert?

Answer 28

Question 29

Wie ist structure connected definiert?

Answer 29

Question 30

Wie ist ein `structure-connected cluster C` definiert?

Answer 30

Question 31

Was ist Chinese Whispers?

Answer 31

Question 32

Beschreib den Chinese Whispers Algorithm

Answer 32

## Footnote selction by majority vote

Question 33

Definiere die Energy Function für Chinese Whispers. Was passiert bei einem Update einer Klasse von einem Knoten?

Answer 33

Question 34

Wozu führt das globale Minimum der Energy Function bei Chinese Whispers?

Answer 34

Dazu, dass alle Knoten zu einer Klasse gehören

Question 35

Wie kann man verhindern, dass Chinese Whispers dazu führt, dass alle Knoten der gleichen Klasse angehören?

Answer 35

Mit negativen Gewichten

Question 36

Was ist spectral clustering?

Answer 36

Question 37

Was ist eine affinity matrix? Welche Eigenschaften hat sie?

Answer 37

Question 38

Beschreib die Idee des Spectral Clusterings anhand von affinity matrizen

Answer 38

Question 39

Wie berechnet man die Affinity Matrix bei gegebenen Datenpunkten?

Answer 39

Question 40

Wie normalisiert man eine affinity matrix?

Answer 40

Question 41

Wie berechnet man die Matrix D zum normalisieren einer affinity matrix?

Answer 41

Question 42

# Spectral Clustering Algorithm Was tut man im Anschluss mit der Matrix L, der normalisierten affinity matrix?

Answer 42

Question 43

# Spectral Clustering Algorithm Nachdem man die Matrix X mit den k Eigenvektoren als Spalten bestimmt hat, was muss man als nächstes tun?

Answer 43

Question 44

# Spectral Clustering Algorithm Wie geht man vor, nachdem man Renormalisiert hat?

Answer 44

Man wendet zum Beispiel k-means an, um cluster zu bilden

Question 45

# Spectral Clustering: Choice of σ Wozu führt ein höheres Sigma?

Answer 45

Dass weiter entfernte Datenpunkte trotzdem noch der gleichen Klasse zugeordnet werden

Question 46

# Spectral Clustering Is the Davies-Bouldin index a good measure for these kinds of clusters?

Answer 46

No! It compares distances of points to mean versus distances between means (in this example, means are all same!)

Question 47

# Spectral Clustering: Choice of k Welche Heuristik wird genutzt, um das optimale k zu finden?

Answer 47

Question 48

Was bedeutet folgendes?

Answer 48

Question 49

Was bedeutet folgendes?

Answer 49

Question 50

Wodurch kann ein semantisches Netzwerk für knowledge representation- and programming languages repräsentiert werden?

Answer 50

by a set of triplets

Question 51

Was ist die Matching rule für eine query Q that matches a database D?

Answer 51

Question 52

Wie funktioniert Classification and information retrieval in semantic networks?

Answer 52

by query matching

Question 53

Was sind Probabilistic Graphical Models?

Answer 53

Modelling of observations and their relationships

Question 54

Beschreib Bayes Theorem

Answer 54

Question 55

Was ist ein Bayesian Belief Network?

Answer 55

Question 56

Beschreib “Conditional Independence” in Bayesian Belief Network

Answer 56

Question 57

Beschreib “Explaining away” in Bayesian Belief Network

Answer 57

Question 58

Was lösen Bayesian Networks im Bezug auf Aufwand?

Answer 58

Question 59

Nenn die Types of Reasoning in Bayesian Networks

Answer 59

* Diagnostic (from symptoms to causes) * Predictive (resoning from new info to new beliefs) * inter-causal (explaining away) * conditional independence

Question 60

Wie werden Bayesian Networks konstruiert?

Answer 60

Question 61

Wie trainiert man Bayesian Networks?

Answer 61

Question 62

Was besagt das Maximum likelihood principle?

Answer 62

favors Bayesian networks that maximize the probability of observing the given data set

Question 63

Was ist die Markovian assumption?

Answer 63

Each variable becomes independent of its non-effects once its direct causes are known

Question 64

The Chinese Whispers algorithm visits every node exactly once. Stimmt das?

Answer 64

Nein

Question 65

Which of the following statements about distance measures in graphs are correct? 1. The diameter of a graph is the maximum eccentricity of all vertices in a graph. 2. The cut set contains all the sets which are the result of a cut. 3. The eccentricity a vertex v is the largest geodesic distance between v and any other vertice in the graph. 4. The radius of a graph is the largest distance between any pair of vertices in a graph.

Answer 65

1 und 3

Question 66

Which of the following statements about spectral clustering are correct? 1. Spectral clustering uses k-means in eigenvector space to cluster the data. 2. The parameter 𝜎 is a neighborhood parameter for some given data point. 3. Only convex clusters can be detected. 4. The number of clusters is determined by the algorithm.

Answer 66

1 und 2

Question 67

Which of the following statements about semantic networks are correct? 1. Edges in a semantic network describe concepts and individuals. 2. Domain-specific rules have to be defined by axiomization. 3. ISA and INSTANCE are well-defined in all contexts. 4. Relations between relations can be expressed with semantic networks.

Answer 67

2 und 3

Question 68

Which of the statements about the SCAN algorithm are correct? 1. Smaller 𝜖 lead to larger clusters. 2. Some vertices may not be assigned to any cluster. 3. The number of clusters has to be chosen at initialization stage. 4. A node is part of its own neighborhood.

Answer 68

1, 2 und 4

Question 69

Which of the statements about the Chinese Whispers algorithm are correct? 1. The algorithm has no optimization parameters. 2. The algorithm is deterministic. 3. The algorithm has linear runtime complexity. 4. The algorithm converges to a global minimum.

Answer 69

1 und 3