OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

A New Information-Theoretical Distance Measure for Evaluating Community Detection Algorithms

Haroutunian, Mariam and Mkhitaryan, Karen and Mothe, Josiane A New Information-Theoretical Distance Measure for Evaluating Community Detection Algorithms. (2019) Journal of Universal Computer Science, 25 (8). 887-903. ISSN 0948-695X

[img]
Preview
(Document in English)

PDF (Publisher's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
777kB

Official URL: http://www.jucs.org/jucs_25_8/a_new_information_theoretical

Abstract

Community detection is a research area from network science dealing withthe investigation of complex networks such as social or biological networks, aimingto identify subgroups (communities) of entities (nodes) thatare more closely relatedto each other inside the community than with the remaining entities in the network.Various community detection algorithms have been developed and used in the literaturehowever evaluating community structures that have been automatically detected isa challenging task due to varying results in different scenarios.Current evaluationmeasures that compare extracted community structures with the reference structure orground truth suffer from various drawbacks; some of them having beenpoint out in theliterature. Information theoretic measures form a fundamental classin this domain andhave recently received increasing interest. However even the well employed measures(NVI and NID) also share some limitations, particularly they are biased toward thenumber of communities in the network. The main contribution ofthis paper is tointroduce a new measure that overcomes this limitation while holding the importantproperties of measures. We review the mathematical properties of our measure based on¿2divergence inspired fromf-divergence measures in information theory. Theoreticalproperties as well as experimental results in various scenarios show the superiority of theproposed measure to evaluate community detection over the ones from the literature.

Item Type:Article
HAL Id:hal-02419470
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > National Academy of Sciences of the Republic of Armenia (ARMENIA)
Laboratory name:
Statistics:download
Deposited On:02 Dec 2019 09:04

Repository Staff Only: item control page