05 SNA Graph Clustering

Question 1

State the central paradigm for formulating a quality measure for clustering (target
function for optimization)! (in words)

Answer 1

Objective function A (g) -> R that formalizes the clustering paradigm in a special
way

Question 2

Coverage is defined as:

State a main disadvantage of using f(C) = γ(C) in a quality measure for clustering

Answer 2

• Only accumulated intra cluster density is measured
• Monotonic behaviour of coverage -> coverage is not a good sole quality index

Question 3

Explain the pragmatics of the following two conductance-based quality measures! (1-2
sentences each)

Answer 3

• First measure: If the measure is small, at least one of the clusters (more precisely: the induced subgraph) contains at least one bottleneck -> this cluster is too coarse -> use minimum conductance cut to cut this cluster in “halves”
• Second measure: If the measure is small, at least one of the clusters (more precisely: the induced subgraph) has many connections to outside -> the clustering is too fine -> merge clusters

Question 4

Explain the pragmatics of the quality measure Performance!

Answer 4

• Count „correctly classified pairs of nodes”.
• Correctly classified: s r and connected by edge (f counts the number of
  edges within clusters) OR not same cluster and not connected by edge (g counts the number of non-existent edges between clusters)
• Calculating maximum of f+g is NP-hard (would be optimal clustering)

Question 5

In case a density measure π on graphs is available, a quality function can be constructed
by pessimistically setting
What are analogous expressions for average case and best case (optimistic view)?

Answer 5

Question 6

In case a density measure π on graphs is available, a quality function can be constructed
by pessimistically setting
Suggest a simple density measure π on graphs!

Answer 6

Question 7

Informally explain the difference between Linkage-based (Agglomerative) and Splittingbased (Divisive) hierarchical clustering! (1-2 sentences)

Answer 7

‡ Linkage (Agglomeration): Iteratively coarsens a given clustering by merging two
clusters until 1-clustering is reached (“bottum up”)
‡ Splitting (Division): Iteratively refines a given clustering by splitting one cluster
until singleton clustering is reached(“top down”)

Question 8

Explain the difference between Complete Linkage and Single Linkage by stating the local
cost functions for both cases and giving 1 sentence of explanation!

Answer 8

Single Linkage defines the local merging cost by looking at the distance between
the closest elements in between the respective clusters, complete link defines the
local merging cost by looking at the distance between the farthest elements in
between clusters

Question 9

What is the benefit of a cut-function when using Splitting-based (Divisive) hierarchical
clustering? (1-2 sentences)

Answer 9

Cut function avoids having to test all possible split

Question 10

Newman ± Girvan method: Explain Modularity! (2-3 sentences)

Answer 10

Tre is the fraction of edges within communities, e is the fraction of edges between
communities. The ultimate goal is to have many edges within communities, but
few between them. Modularity tells us how well we achieved that goal