Paper Notes: Empirical Comparison of Algorithms for Network Community Detection

Paper title: Empirical Comparison of Algorithms for Network Community Detection

Author: Jure Leskovec, Kevin J.Lang, Michael W.Mahoney

Conference: WWW 2010, Raleigh, North Carolina, USA

Year: 2010

This paper explores a range of community detection methods to compare them and to understand better the performance and biases of various algorithms on different kinds of networks. Two representative graph partitioning algorithms, a spectral-based method Local Spectral and a flow-based algorithm Metis+MQI, are studied to compare structural properties of clusters extracted.  The results are: Local Spectral tend to find more compact clusters to compensate for their worst conductance scores, while Metis+MQI can better find low-conductance cuts of the network but suffer from the problem of internal disconnected clusters.

On the other hand, 12 common objective functions to formalize the concept of community quality are also evaluated. Although many of them tend to exhibit similar qualitative behavior, with small clusters achieving the best scores, several quality metrics such as the commonly-used modularity behave in qualitatively different ways (For all diverse classes of graphs modularity and other single-criterion objectives behave in qualitatively similar ways while conductance as well as other bi-criterion objectives has qualitatively different types of behaviors for very different types of graphs).