## 2 Network Community Detection
### Community Evaluation  
Several measures for quantifying the quality of communities have been proposed:  
* Modularity: The notion of modularity is the most popular for network community detection purposes. The modularity index assigns high scores to communities whose internal edges are more than that expected in a random network model, which preserves the degree distribution of the given network.
* Internal density: Density is defined by the number of edges (\(m_{s}\)) in subset \(S\) divided by the total number of possible edges between all nodes \((n_{s}(n_{s}-1)/2)\). The \"2\" is there to cancel out duplicated edges. Internal density \(=m_{s}/(n_{s}(n_{s}-1)/2)\).
* Edges inside: This is somewhat useless by itself, since it is not related to any other attributes of subset \(S\); the total number of edges (\(m_{s}\)) present in subset \(S\). Edges inside \(=m_{s}\).
* Average degree: This is the average internal degree across all nodes (\(n_{s}\)) in subset \(S\). Average degree \(=2m_{s}/n_{s}\).
* The fraction over the median degree: This determines the number of nodes that have an internal degree greater than the median degree of nodes in subset \(S\).
* Triangle Participation Ratio: The best measure for density, cohesiveness, and clustering within the goodness scales. Robust under random and expand perturbations. The fraction of nodes in \(S\) that belong to a triad. TPR = (number of nodes belonging to a triad)\(/n\).  
* Expansion: This measure of separability gives the average number of external connections (\(c_{s}\)) per node (\(n_{s}\)) in subset \(S\) with graph \(G\). It can be thought of as the external degree. Expansion \(=c_{s}/(n_{s}(n-n_{s}))\).
* Cut ratio: This metric is a measure of separability and can be thought of as external density. It is the fraction of external edges (\(c_{s}\)) of subset Sout of the total number of possible edges in graph \(G\).
* Conductance: This is the ratio of edges inside the cluster to the number of edges leaving the cluster (captures the surface area to volume ratio). It measures best in separability (goodness scale), measuring well-separated non-overlapping communities. It is robust under node swap and shrink perturbation. Community-like sets of nodes have lower conductance.
* Normalized cut: This represents how well subset \(S\) is separated from graph \(G\). It sums up the fraction of external edges over all edges in subset \(S\) (conductance) with the fraction of external edges over all non-community edges.
* Maximum out degree fraction: This metric first finds the fraction of external connections to internal connections for each node (\(n_{s}\)) in \(S\). It then returns the fraction with the highest value.
* Average out degree fraction: This is the sum of the individual fraction of edges outside of the community over the total connections of a node in subset \(S\). It is then divided by the total number of nodes (\(n_{s}\)) in subset \(S\).
* Flake out degree fraction: This is a fraction of the number of nodes that have fewer internal connections than external connections to the number of nodes (\(n_{s}\)) in subset \(S\).  
There are several other measures of quality determination for a network community. However, the most widely-used measures are modularity and conductance. The majority of the algorithms are developed using either of the measures as their optimization criteria.