Header

UZH-Logo

Maintenance Infos

A Comparative Analysis of Community Detection Algorithms on Artificial Networks


Yang, Zhao; Algesheimer, René; Tessone, Claudio J (2016). A Comparative Analysis of Community Detection Algorithms on Artificial Networks. Scientific Reports, 6:30750.

Abstract

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.

Abstract

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.

Statistics

Citations

7 citations in Web of Science®
18 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

31 downloads since deposited on 17 Nov 2016
23 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Business Administration
Dewey Decimal Classification:330 Economics
Language:English
Date:1 August 2016
Deposited On:17 Nov 2016 13:15
Last Modified:08 Dec 2017 20:51
Publisher:Nature Publishing Group
ISSN:2045-2322
Free access at:PubMed ID. An embargo period may apply.
Publisher DOI:https://doi.org/10.1038/srep30750
PubMed ID:27476470
Other Identification Number:merlin-id:14017

Download

Download PDF  'A Comparative Analysis of Community Detection Algorithms on Artificial Networks'.
Preview
Content: Published Version
Filetype: PDF
Size: 5MB
View at publisher
Licence: Creative Commons: Attribution 4.0 International (CC BY 4.0)