Cheng Jianjun, Leng Mingwei, Li Longjie, Zhou Hanhai, Chen Xiaoyun
School of Information Science and Engineering, Lanzhou University, Lanzhou, Gansu Province, China.
PLoS One. 2014 Oct 17;9(10):e110088. doi: 10.1371/journal.pone.0110088. eCollection 2014.
Community structure detection is of great importance because it can help in discovering the relationship between the function and the topology structure of a network. Many community detection algorithms have been proposed, but how to incorporate the prior knowledge in the detection process remains a challenging problem. In this paper, we propose a semi-supervised community detection algorithm, which makes full utilization of the must-link and cannot-link constraints to guide the process of community detection and thereby extracts high-quality community structures from networks. To acquire the high-quality must-link and cannot-link constraints, we also propose a semi-supervised component generation algorithm based on active learning, which actively selects nodes with maximum utility for the proposed semi-supervised community detection algorithm step by step, and then generates the must-link and cannot-link constraints by accessing a noiseless oracle. Extensive experiments were carried out, and the experimental results show that the introduction of active learning into the problem of community detection makes a success. Our proposed method can extract high-quality community structures from networks, and significantly outperforms other comparison methods.
社区结构检测非常重要，因为它有助于发现网络的功能与拓扑结构之间的关系。已经提出了许多社区检测算法，但如何在检测过程中纳入先验知识仍然是一个具有挑战性的问题。在本文中，我们提出了一种半监督社区检测算法，该算法充分利用必须链接和不能链接约束来指导社区检测过程，从而从网络中提取高质量的社区结构。为了获得高质量的必须链接和不能链接约束，我们还提出了一种基于主动学习的半监督组件生成算法，该算法逐步为所提出的半监督社区检测算法主动选择具有最大效用的节点，然后通过访问无噪声预言机生成必须链接和不能链接约束。进行了大量实验，实验结果表明将主动学习引入社区检测问题取得了成功。我们提出的方法可以从网络中提取高质量的社区结构，并且明显优于其他比较方法。
