New insight into 2-community structures in graphs with applications in social networks

Cristina Bazgan, Janka Chlebikova, Thomas Pontoizeau

Research output: Chapter in Book/Report/Conference proceedingConference contribution

69 Downloads (Pure)

Abstract

We investigate the structural and algorithmic properties of 2-community structure in graphs introduced by Olsen [A general view on computing communities, Mathematical Social Sciences 66(3):331--336, 2013]. 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.
Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications
Subtitle of host publication9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings
EditorsZaixin Lu, Donghyun Kim, Weili Wu, Wei Li, Ding-Zhu Du
PublisherSpringer
Chapter18
Pages236-250
Number of pages15
ISBN (Electronic)978-3-319-26626-8
ISBN (Print)978-3-319-26625-1
DOIs
Publication statusPublished - 9 Dec 2015
EventThe 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015) - Texas, Houston, United States
Duration: 18 Dec 201520 Dec 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9486
ISSN (Print)0302-9743

Conference

ConferenceThe 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015)
Country/TerritoryUnited States
CityHouston
Period18/12/1520/12/15

Keywords

  • graph theory
  • complexity theory
  • graph partitioning
  • community structure
  • clustering
  • social networks

Fingerprint

Dive into the research topics of 'New insight into 2-community structures in graphs with applications in social networks'. Together they form a unique fingerprint.

Cite this