# Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

### Graph Clustering: Sparsest Cut

• G = (V,E). The cut set of a cut is the set of edges {(u, v) ∈ E | u ∈ S, v ∈ T } and S and T are in two partitions • Size of the cut: # of edges in the cut set
• Min-cut (e.g., C1) is not a good partition
• A better measure: Sparsity:

φ=the size of the cut / min{|S|,|T|}

• A cut is sparsest if its sparsity is not greater than that of any other cut
• Ex. Cut C2 = ({a, b, c, d, e, f, l}, {g, h, i, j, k}) is the sparsest cut
• For k clusters, the modularity o a clustering assesses the quality of the clustering:

$Q=\sum_{i=1}^{k}(\frac{l_{i}}{|E|}-(\frac{d_{i}}{2|E|})^{2})$

li: # edges between vertices in the i-th cluster

di: the sum of the degrees of the vertices in the i-th cluster

• The modularity of a clustering of a graph is the difference between the fraction of all edges that fall into individual clusters and the fraction that would do so if the graph vertices were randomly connected
• The optimal clustering of graphs maximizes the modularity   Speaker notes:

## Content Tools

### Sources

There are currently no sources for this slide.