Overcoming Resolution Limits in MDL Community Detection

A popular approach to community detection in networks is to search for partitions that maximize modularity [7]. However, recent work has identified two important limitations of modularity as a community quality criterion: a resolution limit; and a bias towards finding equal-sized communities. Compression-based approaches that search for partitions that minimize description length are a recent alternative to modularity. This paper shows that two compressionbased algorithms are themselves subject to a resolution limit, identifies the aspect of each approach that is responsible for the resolution limit, proposes a variant, SGE (Sparse Graph Encoding), that addresses this limitation, and demonstrates on three artificial data sets that (1) SGE does not exhibit a resolution limit on graphs in which other approaches do, and that (2) modularity and the compression-based algorithms, including SGE, behave similarly on graphs not subject to the resolution limit.