title: Active link selection for efficient semi-supervised community detection.
abstract: Several semi-supervised community detection algorithms have been proposed recently to improve the performance of traditional topology-based methods. However, most of them focus on how to integrate supervised information with topology information; few of them pay attention to which information is critical for performance improvement. This leads to large amounts of demand for supervised information, which is expensive or difficult to obtain in most fields. For this problem we propose an active link selection framework, that is we actively select the most uncertain and informative links for human labeling for the efficient utilization of the supervised information. We also disconnect the most likely inter-community edges to further improve the efficiency. Our main idea is that, by connecting uncertain nodes to their community hubs and disconnecting the inter-community edges, one can sharpen the block structure of adjacency matrix more efficiently than randomly labeling links as the existing methods did. Experiments on both synthetic and real networks demonstrate that our new approach significantly outperforms the existing methods in terms of the efficiency of using supervised information. It needs ~13% of the supervised information to achieve a performance similar to that of the original semi-supervised approaches.
authors.affiliation: 1] State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China [2] School of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China.
authors.forename: Liang
authors.initials: L
authors.lastname: Yang
authors.affiliation: School of Computer Science and Technology, Tianjin University, Tianjin 300072, China.
authors.forename: Di
authors.initials: D
authors.lastname: Jin
authors.affiliation: School of Computer Science and Technology, Tianjin University, Tianjin 300072, China.
authors.forename: Xiao
authors.initials: X
authors.lastname: Wang
authors.affiliation: 1] State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China [2] School of Computer Science and Technology, Tianjin University, Tianjin 300072, China.
authors.forename: Xiaochun
authors.initials: X
authors.lastname: Cao
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical