Modularity Clustering

Method: define modularity score that we aim to maximise

Characteristic idea: compare communities to a random baseline graph that shares some properties with the actual graph, such as the number of edges and the degree of the nodes

1. Compute the number of edges within a community, then subtract the expected number of edges as per the baseline model (A_{ij}-P_{ij})
2. A_{ij}=1: if edge is between i,j
A_{ij}=1: if there is no edge

Modularity score: \text{edges in community 1}-\text{baseline expected edges in community 1}+\text{edges in community 2}-\text{baseline expected edges in community 2}
If score is large, then community is dense

1. Start with some partitioning, then move nodes between the groups to see if it improves the score
2. Use eigenvectors