Istituto di Scienza e Tecnologie dell'Informazione     
Rossetti G., Pappalardo L., Rinzivillo S. A novel approach to evaluate community detection algorithms on ground truth. In: CompleNet 2016 - Complex Networks VII. Proceedings of the 7th Workshop on Complex Networks (Dijon, France, 23-25 March 2016). Proceedings, pp. 133 - 144. Hocine Cherifi, Bruno Gonçalves, Ronaldo Menezes, Roberta Sinatra (eds.). (Studies in Computational Intelligence, vol. 644). Springer, 2016.
Evaluating a community detection algorithm is a complex task due to the lack of a shared and universally accepted definition of community. In literature, one of the most common way to assess the performances of a community detection algorithm is to compare its output with given ground truth communities by using computationally expensive metrics (i.e., Normalized Mutual Information). In this paper we propose a novel approach aimed at evaluating the adherence of a community partition to the ground truth: our methodology provides more information than the state-of-the-art ones and is fast to compute on large-scale networks. We evaluate its correctness by applying it to six popular community detection algorithms on four large-scale network datasets. Experimental results show how our approach allows to easily evaluate the obtained communities on the ground truth and to characterize the quality of community detection algorithms.
URL: http://link.springer.com/chapter/10.1007%2F978-3-319-30569-1_10
DOI: 10.1007/978-3-319-30569-1_10
Subject Complex Networks
Community Discovery

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional