Detecting clusters or communities in large real-world graphs such as largesocial or information networks is a problem of considerable interest. Inpractice, one typically chooses an objective function that captures theintuition of a network cluster as set of nodes with better internalconnectivity than external connectivity, and then one applies approximationalgorithms or heuristics to extract sets of nodes that are related to theobjective function and that "look like" good communities for the application ofinterest. In this paper, we explore a range of network community detectionmethods in order to compare them and to understand their relative performanceand the systematic biases in the clusters they identify. We evaluate severalcommon objective functions that are used to formalize the notion of a networkcommunity, and we examine several different classes of approximation algorithmsthat aim to optimize such objective functions. In addition, rather than simplyfixing an objective and asking for an approximation to the best cluster of anysize, we consider a size-resolved version of the optimization problem.Considering community quality as a function of its size provides a much finerlens with which to examine community detection algorithms, since objectivefunctions and approximation algorithms often have non-obvious size-dependentbehavior.
[1004.3539] Empirical Comparison of Algorithms for Network Community Detection