关键词: 复杂网络, 重叠社区发现, 半监督, 对偶约束, PC-GCE

Abstract: In the research of finding overlapping community in complex networks, one of the ways to improve accuracy is by harnessing additional background information (e.g. from domain experts), which can be used as a source of constraints to guide the community detection process. In this paper, the potential of semi-supervised strategies to improve algorithms for finding overlapping communities in networks is explored. We introduce constraints that must link and cannot link into the initialization phase of the process and in the subcommunity extension process, and propose an approach named PC-GCE(Pairwise Constrained Greedy Clique Expansion) for finding overlapping communities by using a limited number of pairwise constraints and combing greedy strategies. A comparative experiment is conducted between the simulated network data and the current unconstrained locally extended overlapping community discovery algorithm (GCE), experimental results show that the PC-GCE can achieve better performance than GCE on finding overlapping communities, and as the increasing numbers of pairwise constraints, PC-GCE shows greater performance in the finding accuracy.

Key words: complex network, overlapping community finding, semi-supervise, pairwise constraints, pairwise constrained greedy clique expansion