A declarative approach to constrained community detection

Mohadeseh Ganji, James Bailey, Peter J. Stuckey

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

8 Citations (Scopus)

Abstract

Community detection in the presence of prior information or preferences on solution properties is called semi-supervised or constrained community detection. The task of embedding such existing kinds of knowledge effectively within a community discovery algorithm is challenging. Indeed existing approaches are not flexible enough to incorporate a variety of background information types. This paper provides a framework for semi-supervised community detection based on constraint programming modelling technology for simultaneously modelling different objective functions such as modularity and a comprehensive range of constraint types including community level, instance level, definition based and complex logic constraints. An advantage of the proposed framework is that, using appropriate solvers, optimality can be established for the solutions found. Experiments on real and benchmark data sets show strong performance and flexibility for our proposed framework.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication23rd International Conference, CP 2017 Melbourne, VIC, Australia, August 28 – September 1, 2017 Proceedings
EditorsJ.Christopher Beck
Place of PublicationCham Switzerland
PublisherSpringer
Pages477-494
Number of pages18
ISBN (Electronic)9783319661582
ISBN (Print)9783319661575
DOIs
Publication statusPublished - 2017
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2017 - Melbourne, Australia
Duration: 28 Aug 20171 Sep 2017
Conference number: 23rd
http://cp2017.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10416
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2017
Abbreviated titleCP 2017
CountryAustralia
CityMelbourne
Period28/08/171/09/17
OtherThe International Conference on Principles and Practice of Constraint Programming will take place in Melbourne, Australia alongside SAT 2017 and ICLP 2017 from August 28th to September 1st, 2017 which is the week immediately following IJCAI 2017.
Internet address

Cite this

Ganji, M., Bailey, J., & Stuckey, P. J. (2017). A declarative approach to constrained community detection. In J. C. Beck (Ed.), Principles and Practice of Constraint Programming : 23rd International Conference, CP 2017 Melbourne, VIC, Australia, August 28 – September 1, 2017 Proceedings (pp. 477-494). (Lecture Notes in Computer Science ; Vol. 10416 ). Springer. https://doi.org/10.1007/978-3-319-66158-2_31