Data-driven intelligent systems > Mining Structure from Graphs > Flashcards

Mining Structure from Graphs Flashcards

(69 cards)

Study These Flashcards
1
Q

Nenn Similarity measures für Clustering Graphs

A
  • Geodesic distances
  • Structural Similarity
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Was sind geodesic distances?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Wie berechnet man die geodesic distance in einem Graphen?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Was ist die Eccentricity von einem Knoten v?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Was ist ein peripheral vertex?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Was ist der Radius von einem Graphen?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Was ist der Diameter eines Graphen?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Beschreib Graph Clustering über Sparset Cut

A

Trennen von einem Graphen in Subgraphen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A
  • Bestimmen der Größe eiens Cuts über die Anzahl der Kanten.
  • Min-cut (not good partition)
  • Besser: Sparsity
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Was ist Sparsity?

A

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

size of cut = anzahl an subgraphen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Wann ist ein cut sparsest?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Was ist modularity beim Graphclustering?

A

The modularity of a clustering assesses the quality of the clustering

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Wie berechnet man die modularity?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Challenges of Finding Good Cuts

Was sind Herausforderungen für Graph Clustering?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Wie bestimmt man die structural similarity?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

SCAN: Structural Clustering Algorithm for Networks

Zwischen welchen Individuals unterscheidet man?

A
  • Individuals in a tight social group, or clique
  • Individuals who are hubs
  • Individuals who are outliers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

SCAN: Structural Clustering Algorithm for Networks

Beschreib Individuals in a tight social group, or clique

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

SCAN: Structural Clustering Algorithm for Networks

Beschreib Individuals who are hubs

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

SCAN: Structural Clustering Algorithm for Networks

Beschreib Individuals who are outliers

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

Die Nachbarschaft zweier Knoten überdecken sich komplett

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Wie ist eine epsilon-neighborhood definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Wie ist ein Vertex-CORE definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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

A

Sie werden kleiner

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
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)
26
Wie ist `direct structure reachable` definiert?
27
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
28
Wie ist `structure reachable` definiert?
29
Wie ist structure connected definiert?
30
Wie ist ein `structure-connected cluster C` definiert?
31
Was ist Chinese Whispers?
32
Beschreib den Chinese Whispers Algorithm
## Footnote selction by majority vote
33
Definiere die Energy Function für Chinese Whispers. Was passiert bei einem Update einer Klasse von einem Knoten?
34
Wozu führt das globale Minimum der Energy Function bei Chinese Whispers?
Dazu, dass alle Knoten zu einer Klasse gehören
35
Wie kann man verhindern, dass Chinese Whispers dazu führt, dass alle Knoten der gleichen Klasse angehören?
Mit negativen Gewichten
36
Was ist spectral clustering?
37
Was ist eine affinity matrix? Welche Eigenschaften hat sie?
38
Beschreib die Idee des Spectral Clusterings anhand von affinity matrizen
39
Wie berechnet man die Affinity Matrix bei gegebenen Datenpunkten?
40
Wie normalisiert man eine affinity matrix?
41
Wie berechnet man die Matrix D zum normalisieren einer affinity matrix?
42
# Spectral Clustering Algorithm Was tut man im Anschluss mit der Matrix L, der normalisierten affinity matrix?
43
# Spectral Clustering Algorithm Nachdem man die Matrix X mit den k Eigenvektoren als Spalten bestimmt hat, was muss man als nächstes tun?
44
# Spectral Clustering Algorithm Wie geht man vor, nachdem man Renormalisiert hat?
Man wendet zum Beispiel k-means an, um cluster zu bilden
45
# Spectral Clustering: Choice of σ Wozu führt ein höheres Sigma?
Dass weiter entfernte Datenpunkte trotzdem noch der gleichen Klasse zugeordnet werden
46
# 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!)
47
# Spectral Clustering: Choice of k Welche Heuristik wird genutzt, um das optimale k zu finden?
48
Was bedeutet folgendes?
49
Was bedeutet folgendes?
50
Wodurch kann ein semantisches Netzwerk für knowledge representation- and programming languages repräsentiert werden?
by a set of triplets
51
Was ist die Matching rule für eine query Q that matches a database D?
52
Wie funktioniert Classification and information retrieval in semantic networks?
by query matching
53
Was sind Probabilistic Graphical Models?
Modelling of observations and their relationships
54
Beschreib Bayes Theorem
55
Was ist ein Bayesian Belief Network?
56
Beschreib “Conditional Independence” in Bayesian Belief Network
57
Beschreib “Explaining away” in Bayesian Belief Network
58
Was lösen Bayesian Networks im Bezug auf Aufwand?
59
Nenn die Types of Reasoning in Bayesian Networks
* Diagnostic (from symptoms to causes) * Predictive (resoning from new info to new beliefs) * inter-causal (explaining away) * conditional independence
60
Wie werden Bayesian Networks konstruiert?
61
Wie trainiert man Bayesian Networks?
62
Was besagt das Maximum likelihood principle?
favors Bayesian networks that maximize the probability of observing the given data set
63
Was ist die Markovian assumption?
Each variable becomes independent of its non-effects once its direct causes are known
64
The Chinese Whispers algorithm visits every node exactly once. Stimmt das?
Nein
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.
1 und 3
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.
1 und 2
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.
2 und 3
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.
1, 2 und 4
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.
1 und 3
Data-driven intelligent systems
flashcards
Decks in class (18)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions