Effective Semi-Supervised Community Detection Via Multi-Variance Mixed Gaussian Generative Model

Due to the demand for performance improvement and the existence of prior information,semi-supervised community detection with pairwise constraint becomes a hot topic in complex network analysis.Most existing methods only successfully encode the must-link constraints,but cannot further improve the performance using cannot-link constraints.In this paper to understand the roles of cannot-link constraints and further improve the effectiveness of semi-supervised algorithm,we consider the generative process of the network topology,must-link and cannot-link constraints.By finding that network topology and pairwise constraints are generated with different degree of confidence,we describe this process as a Multi-variance Mixed Gaussian(MMGG)Model and solve it using weighted nonnegative matrix factorization.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 if either of them is available,both must-link and cannot-link are very important if both of them are available.To the best of our knowledge,this is the first work on discovering and exploring the important role of cannot-link constraints in semi-supervised community detection.