Yang, Liang, Ge, Meng, Jin, Di, He, Dongxiao, Fu, Huazhu, Wang, Jing and Cao, Xiaochun (2017) Exploring the roles of cannot-link constraint in community detection via multi-variance mixed Gaussian generative model. PLoS One, 12 (7):e0178029. ISSN 1932-6203 (Online) (doi:10.1371/journal.pone.0178029)

Preview

PDF (Open Access Article) 30503 WANG_Exploring_The_Roles_Of_Cannot-link_Constraint_In_Community_Detection_(OA)_2017.pdf - Published Version Available under License Creative Commons Attribution. Download (5MB) | Preview

Abstract

Due to the demand for performance improvement and the existence of prior information, semi-supervised community detection with pairwise constraints becomes a hot topic. Most existing methods have been successfully encoding the must-link constraints, but neglect the opposite ones, i.e., the cannot-link constraints, which can force the exclusion between nodes. In this paper, we are interested in understanding the role of cannot-link constraints and effectively encoding pairwise constraints. Towards these goals, we define an integral generative process jointly considering the network topology, must-link and cannot-link constraints. We propose to characterize this process as a Multi-variance Mixed Gaussian Generative (MMGG) Model to address diverse degrees of confidences that exist in network topology and pairwise constraints and formulate it as a weighted nonnegative matrix factorization problem. The experiments on artificial and real-world networks not only illustrate the superiority of our proposed MMGG, but also, most importantly, reveal the roles of pairwise constraints. That is, though the must-link is more important than cannot-link when either of them is available, both must-link and cannot-link are equally important when both of them are available. To the best of our knowledge, this is the first work on discovering and exploring the importance of cannot-link constraints in semi-supervised community detection.

Item Type:	Article
Uncontrolled Keywords:	community detection, semi-supervised learning
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/30503

Actions (login required)

View Item

Downloads