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-01-11T16:11:42Z
dc.date.available2017-01-11T16:11:42Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16151
dc.descriptionin Springer series Lecture Notes in Computer Science, Vol 9486en
dc.language.isoenen
dc.subjectPartitionen
dc.subjectApproximationen
dc.subjectGraph theoryen
dc.subjectComplexityen
dc.subjectGraph partitioningen
dc.subjectCommunity structureen
dc.subjectClusteringen
dc.subjectSocial networksen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleNew Insight into 2-Community Structures in Graphs with Applications in Social Networksen
dc.typeCommunication / Conférence
dc.description.abstractenWe investigate the structural and algorithmic properties of 2-community structure in graphs introduced by Olsen [13]. A 2-community structure is a partition of vertex set into two parts such that for each vertex of the graph number of neighbours in/outside own part is in correlation with sizes of parts. We show that every 3-regular graph has a 2-community structure which can be found in polynomial time, even if the subgraphs induced by each partition must be connected. We introduce a concept of a 2-weak community and prove that it is NP-complete to find a balanced 2-weak community structure in general graphs even with additional request of connectivity for both parts. On the other hand, the problem can be solved in polynomial time in graphs of degree at most 3.en
dc.identifier.citationpages236-250en
dc.relation.ispartoftitleCombinatorial Optimization and Applicationsen
dc.relation.ispartofeditorLu, Zaixin
dc.relation.ispartofeditorKim, Donghyun
dc.relation.ispartofeditorWu, Weili
dc.relation.ispartofeditorLi, Wei
dc.relation.ispartofeditorDu, Ding-Zhu
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2015-12
dc.relation.ispartofpages810en
dc.relation.ispartofurl10.1007/978-3-319-26626-8en
dc.contributor.countryeditoruniversityotherOther
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-26625-1en
dc.relation.conftitle9th International Conference, COCOA 2015en
dc.relation.confdate2015-12
dc.relation.confcityHouston, TXen
dc.relation.confcountryUnited Statesen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-26626-8_18en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-01-11T15:58:18Z
hal.identifierhal-01432509*
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