Lagrangian constrained community detection

Mohadeseh Ganj, James Bailey, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

4 Citations (Scopus)


Semi-supervised or constrained community detection incorporates side information to find communities of interest in complex networks. The supervision is often represented as constraints such as known labels and pairwise constraints. Existing constrained community detection approaches often fail to fully benefit from the available side information. This results in poor performance for scenarios such as: when the constraints are required to be fully satisfied, when there is a high confidence about the correctness of the supervision information, and in situations where the side information is expensive or hard to achieve and is only available in a limited amount. In this paper, we propose a new constrained community detection algorithm based on Lagrangian multipliers to incorporate and fully satisfy the instance level supervision constraints. Our proposed algorithm can more fully utilise available side information and find better quality solutions. Our experiments on real and synthetic data sets show our proposed LagCCD algorithm outperforms existing algorithms in terms of solution quality, ability to satisfy the constraints and noise resistance.

Original languageEnglish
Title of host publicationThe Thirty-Second AAAI Conference on Artificial Intelligence
EditorsSheila McIlraith, Kilian Weinberger
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages8
ISBN (Electronic)9781577358008
Publication statusPublished - 2018
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2018 - New Orleans, United States of America
Duration: 2 Feb 20187 Feb 2018
Conference number: 32nd


ConferenceAAAI Conference on Artificial Intelligence 2018
Abbreviated titleAAAI 2018
CountryUnited States of America
CityNew Orleans
Internet address

Cite this