Integer programming models for detecting graph bipartitions with structural requirements

Chrysafis Vogiatzis, Jose L. Walteros

Research output: Contribution to journalArticle

Abstract

The graph bipartitioning problem consists of dividing a graph into two disjoint subgraphs, such that each node is highly similar to others in the same subgraph, but also different from members of the other subgraph, according to some homogeneity criterion. This problem has received significant attention over the last few years because of its applicability in areas as diverse as data classification, image segmentation, and social network analysis. In this article we study a variation of the graph bipartitioning problem in which, in addition to considering homogeneity criteria for generating the partition, we also ensure that one of the subgraphs satisfies a set of predefined structural properties—that is, such a subgraph is required to induce a given motif. We focus our attention on imposing structural constraints that force one of the subgraphs to induce stars, cliques, and clique relaxations (quasi-cliques) and discuss some specific applications for such particular cases. We tackle this problem by modeling it as a general fractional programming optimization problem and study several solution approaches. Moreover, we discuss additional algorithmic enhancements to tackle some of the aforementioned cases, and provide two greedy algorithms for the specific cases of induced cliques and stars, showing the approximation ratio for induced stars. Finally, we test the quality of our approach by solving a collection of several real-life and randomly generated instances with various configurations, analyzing the benefits of the proposed models, as well as possible further extensions.

Original languageEnglish (US)
Pages (from-to)432-450
Number of pages19
JournalNetworks
Volume71
Issue number4
DOIs
StatePublished - Jun 2018
Externally publishedYes

Keywords

  • clique relaxations
  • data classification
  • graph partitioning
  • normalized cut

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Integer programming models for detecting graph bipartitions with structural requirements'. Together they form a unique fingerprint.

  • Cite this