An efficient semi-supervised community detection framework in social networks

PLoS One. 2017 May 23;12(5):e0178046. doi: 10.1371/journal.pone.0178046. eCollection 2017.

Abstract

Community detection is an important tasks across a number of research fields including social science, biology, and physics. In the real world, topology information alone is often inadequate to accurately find out community structure due to its sparsity and noise. The potential useful prior information such as pairwise constraints which contain must-link and cannot-link constraints can be obtained from domain knowledge in many applications. Thus, combining network topology with prior information to improve the community detection accuracy is promising. Previous methods mainly utilize the must-link constraints while cannot make full use of cannot-link constraints. In this paper, we propose a semi-supervised community detection framework which can effectively incorporate two types of pairwise constraints into the detection process. Particularly, must-link and cannot-link constraints are represented as positive and negative links, and we encode them by adding different graph regularization terms to penalize closeness of the nodes. Experiments on multiple real-world datasets show that the proposed framework significantly improves the accuracy of community detection.

MeSH terms

  • Animals
  • Books
  • Datasets as Topic
  • Dolphins
  • Economics
  • Football
  • Humans
  • Internet
  • Machine Learning*
  • Martial Arts
  • Politics
  • Social Behavior*
  • United Kingdom
  • United States

Grants and funding

This work was supported by Natural Science Foundation of Jiangsu Province, China (No. BK20140073), the website is http://www.nsfc.gov.cn/. The author Y Gong received the funding. The funder had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.