Structural and algorithmic properties of 2-community structures

Janka Chlebikova, Cristina Bazgan, Thomas Pontoizeau

Research output: Contribution to journalArticlepeer-review

82 Downloads (Pure)

Abstract

We 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|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.
Original languageEnglish
Pages (from-to)1890-1908
Number of pages19
JournalAlgorithmica
Volume80
Issue number6
Early online date6 Feb 2017
DOIs
Publication statusPublished - 1 Jun 2018

Keywords

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

Fingerprint

Dive into the research topics of 'Structural and algorithmic properties of 2-community structures'. Together they form a unique fingerprint.

Cite this