Co-author(s) :

Mkhitaryan Karen ; Mothe Josiane

Abstract:

Community detection is a research area from network science dealing with the investigation of complex networks such as social or biological networks, aiming to identify subgroups (communities) of entities (nodes) that are more closely related to each other inside the community than with the remaining entities in the network. Various community detection algorithms have been developed and used in the literature however evaluating community structures that have been automatically detected is a challenging task due to varying results in different scenarios. Current evaluation measures that compare extracted community structures with the reference structure or ground truth suffer from various drawbacks; some of them having been point out in the literature. Information theoretic measures form a fundamental class in this domain and have recently received increasing interest. However even the well employed measures (NVI and NID) also share some limitations, particularly they are biased toward the number of communities in the network. The main contribution of this paper is to introduce a new measure that overcomes this limitation while holding the important properties of measures. We review the mathematical properties of our measure based on χ 2 divergence inspired from f-divergence measures in information theory. Theoretical properties as well as experimental results in various scenarios show the superiority of the proposed measure to evaluate community detection over the ones from the literature.

Date submitted:

26.12.2018

Date accepted:

30.5.2019

Identifier:

oai:noad.sci.am:136213

DOI:

10.3217/jucs-025-08-0887

Journal or Publication Title:

Journal of Universal Computer Science

Volume:

25

Number:

8

URL:

click here to follow the link

Affiliation:

Institute for Informatics and Automation Problems of NAS RA ; Toulouse Institute of Computer Science Research, Universit´e de Toulouse

Year:

2019