Conductance

Conductance is a way to measure the quality of a community. By an empirical definition of communities, a good community should have more internal links and less externals links.

From this intuition, the Conductance of a cut $(S,{\bar {S}})$ in a graph is defined as:

$\varphi (S)={\frac {\sum _{i\in S,j\in {\bar {S}}}a_{ij}}{\min(a(S),a({\bar {S}}))}}$

where the $a_{ij}$ are the entries of the adjacency matrix for G, so that

$a(S)=\sum _{i\in S}\sum _{j\in V}a_{ij}$

is the total number (or weight) of the edges incident with S.