A Comparative Analysis of Community Detection Algorithms on Artificial Networks

By Zhao Yang, René Algesheimer, Claudio J. Tessone. Scientific Reports, 2016

793 citations recorded by the source corpus.

Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms’ computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm’s predicting power and the effective computing time.

Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/fb163d68fae1af914e177e46b779542b9d816c08

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Exploratory graph analysis: A new approach for estimating the number of dimensions in psychological research (2016, background): “However, Yang, Algesheimer and Tessone [69] investigated the accuracy of community detection algorithms for very large undirected weighted networks (with more than 1,000 nodes),”
From Louvain to Leiden: guaranteeing well-connected communities (2018, methodology): “It was found to be one of the fastest and best performing algorithms in comparative analyses 11,12 , and it is one of the most-cited works in the community detection literature.”