Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina*
hal.structure.identifier
dc.contributor.authorChlebíková, Janka*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPontoizeau, Thomas*
dc.date.accessioned2017-03-03T13:57:23Z
dc.date.available2017-03-03T13:57:23Z
dc.date.issued2018
dc.identifier.issn0178-4617
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16286
dc.language.isoenen
dc.subjectGraph theory
dc.subjectComplexity
dc.subjectGraph partitioning
dc.subjectCommunity structure
dc.subjectClustering
dc.subjectSocial networks
dc.subjectApproximation
dc.subject.ddc511; 003en
dc.titleStructural and algorithmic properties of 2-community structures
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversity of Portsmouth
dc.description.abstractenWe investigate the structural and algorithmic properties of 2-community structures in graphs introduced recently by Olsen (Math Soc Sci 66(3):331–336, 2013). A 2-community structure is a partition of a vertex set into two parts such that for each vertex the numbers of neighbours in/outside its own part and the sizes of the parts are correlated. We show that some well studied graph classes as graphs of maximum degree 3, minimum degree at least |V|−3, trees and also others, have always a 2-community structure. Furthermore, a 2-community structure can be found in polynomial time in all these classes, even with additional request of connectivity in both parts. We introduce a concept of a weak 2-community and prove that in general graphs it is NP-complete to find a balanced weak 2-community structure with or without request for connectivity in both parts. On the other hand, we present a polynomial-time algorithm to solve the problem (without the condition for connectivity of parts) in graphs of degree at most 3.
dc.relation.isversionofjnlnameAlgorithmica
dc.relation.isversionofjnlvol80
dc.relation.isversionofjnlissue6
dc.relation.isversionofjnldate2018
dc.relation.isversionofjnlpages180-1908
dc.relation.isversionofdoi10.1007/s00453-017-0283-7
dc.contributor.countryeditoruniversityotherOther
dc.relation.isversionofjnlpublisherSpringer
dc.subject.ddclabelPrincipes généraux des mathématiques; Recherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2019-12-10T01:52:48Z
hal.identifierhal-01482319*
hal.version1*
hal.update.actionupdateFiles*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record