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

Mariam Haroutunian (National Academy of Sciences of the Republic of Armenia, Armenia)

Karen Mkhitaryan (National Academy of Sciences of the Republic of Armenia, Armenia)

Josiane Mothe (Universite de Toulouse, France)

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 x² 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.

Keywords: f-divergences, community detection, evaluation measure

Categories: E.4