USI-AUC: An evaluation criterion of community detection based on a novel link-prediction method

Article type: Research Article

Authors: Wu, Yiteng^a | Yu, Hongtao^{a; *} | Zhang, Jianpeng^{a; b} | Liu, Shuxin^a | Huang, Ruiyang^a | Li, Peng^a

Affiliations: [a] National Digital Switching System Engineering and Technological R&D Center, Zhengzhou, Henan 450002, China | [b] , 5600 MB Eindhoven, The Netherlands

Correspondence: [*] Corresponding author: Hongtao Yu, National Digital Switching System Engineering and Technological R&D Center, Zhengzhou, Henan 450002, China. E-mail: hunter_yxq@126.com.

Abstract: Modularity Evaluation (ME) is usually used in community detection for evaluating the disjoint and overlapping communities. In this paper, two obvious defects of ME are revealed and proved, including the non-decreasing contribution of isolated nodes to modularity and lacking of appropriate measures on overlapping community. We also propose a new evaluation criterion, the USI-AUC, which is the Area Under the Curve (AUC), originated from link-prediction of Uniform-Structure-Information (USI) model. We test the new criterion on various datasets, and find that such criterion can avoid the issues exposed in ME.

Keywords: Evaluation of communities, modularity evaluation, USI model, link prediction, USI-AUC criterion

DOI: 10.3233/IDA-173400

Journal: Intelligent Data Analysis, vol. 22, no. 2, pp. 439-462, 2018