Benchmark graphs and evaluation of community detection algorithms

 

SUNE LEHMANN

INSTITUTE FOR QUANTITATIVE SOCIAL SCIENCE, HARVARD

 

In recent years, a proliferation of community detection algorithms has occurred, and so it has become important to develop testing procedures to evaluate performance and accuracy in a fair and unbiased manner. Many current tests consist of benchmarks graphs with artificially enforced community structure, coupled with performance measures such as mutual information between designed and detected structure. We show that this general approach can be problematic, in particular with respect to testing disparate community methods. Further, benchmark tests often fail to reproduce features present in real networks (for example clustering), which may cause performance estimated on benchmark graphs to correlate poorly with real-world performance. We propose an alternative testing method based on real world meta-data.