PUMA
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.
 
 
Abstract
(English)
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
Classification
G.2.2 DISCRETE MATHEMATICS. Graph Theory


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