Detecting Communities

Question 1

What is a graph partitioning problem?

Answer 1

Detecting two communities

Question 2

Name the various methods used to solve for graph partitioning

Answer 2

Girvan-Newman algorithm - exploits betweenness centrality
Minimum cut - optimal division
Modularity Maximization - identify communities by varying the division
Hierarchical Clustering
Generative Model
What do we use? Laplacian

Question 3

How do we find the partition to a Laplacian Network?

Answer 3

The partition is determined by the eigenvector associated with the first non-trivial eigenvalue

Question 4

How do we find the partition to a Laplacian Network?

Answer 4

The partition is determined by the eigenvector associated with the first non-trivial eigenvalue

Question 5

How do we find the optimal solution for cut size (R)?

Answer 5

1. Create a vector, s, in which if an element is part of group 1, it equals +1, in group 2 it equals -1.
2. Using calc identities, we can reduce it such that the goal is to find an s that minimizes r

Question 6

What is the first constraint on the vector s when optimizing?

Answer 6

1.The possible vector s must lie on any of the vertices of the hypercube, abs(s) = sqrt(n) where n is the number of dimensions

Question 7

What is the second constraint on the vector s when optimizing?

Answer 7

2. The summation of the s elements must equal the difference between the number of nodes in each community (n1 - n2).

Question 8

R (the cut size) is proportional to one of the eigenvalues in the matrix. How do we minimize R then?

Answer 8

Choose the smallest non-trivial eigenvalue which is lamba_2.