Abstract: Link model is able to model community detection problem on networks. Compared with other similar models including symmetric models and conditional models, PPL (Popularity and Productivity Link) deals more types of networks, and detects communities more accurately. But PPL is an unsupervised model, and works badly when the network structure is unclear. In addition, PPL is not able to utilize priors that are easily captained. In order to improve its performance by using as less as possible, an Active Node Prior Learning (ANPL) algorithm was provided. ANPL selected the highest utility and easily labeled pairwise constraints, and generated automatically more informative labeled nodes based on the labeled pairwise constraints. Based on the PPL model,a Semi-supervised PPL (SPPL) model was proposed for community detection, which combined the topology of network and node labels learned from the ANPL algorithm. Experiments on synthetic and real networks demonstrate that using node priors from the ANPL algorithm and the topology of a network, SPPL model excels to unsupervised PPL model and popular semi-supervised community detection models based on Non-negative Matrix Factorization (NMF).

Key words: semi-supervised community detection, active learning, link model, Expectation Maximization (EM) algorithm, constrained prior

摘要： 链接模型可对网络的社区发现问题建模，相比具有相同目标的对称模型和条件模型，PPL模型处理网络类型更多、社区发现准确率更高。但PPL模型是一个无监督模型，在网络社区结构不清晰时效果不佳，且不能利用易获取的先验信息。为使用尽可能少的先验，获得社区发现链接模型性能较大的提升，提出了一个主动节点先验学习（ANPL）算法，该算法主动选择效用高、易标记的成对约束进行标记，基于标记的约束对自动生成信息量更大的标记节点集合。基于PPL模型设计了一个融合网络拓扑结构和标记节点先验的半监督社区发现（SPPL）模型，并给出模型用于半监督社区发现的参数估计算法。人工网络和实际网络上的实验结果表明，利用ANPL获得的标记节点先验和网络拓扑结构，SPPL模型的社区发现准确率高于无监督PPL模型及当前流行的基于非负矩阵分解（NMF）的半监督社区发现模型。

关键词: 半监督社区发现, 主动学习, 链接模型, 最大期望算法, 约束先验