TY - JOUR
T1 - Integer programming models for detecting graph bipartitions with structural requirements
AU - Vogiatzis, Chrysafis
AU - Walteros, Jose L.
N1 - Funding Information:
Received November 2016; accepted September 2017 Correspondence to: C. Vogiatzis; e-mail: chrysafis.vogiatzis@ndsu.edu Contract grant sponsor: National Science Foundation, Division of Civil, Mechanical and Manufacturing Innovation; Contract grant number: 1635611 Contract grant sponsor: Air Force Research Laboratory Mathematical Modeling and Optimization Institute DOI 10.1002/net.21786 Published online 25 October 2017 in Wiley Online Library (wileyonlinelibrary.com). © 2017 Wiley Periodicals, Inc.
Publisher Copyright:
© 2017 Wiley Periodicals, Inc.
PY - 2018/6
Y1 - 2018/6
N2 - 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.
AB - 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.
KW - clique relaxations
KW - data classification
KW - graph partitioning
KW - normalized cut
UR - http://www.scopus.com/inward/record.url?scp=85046441372&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85046441372&partnerID=8YFLogxK
U2 - 10.1002/net.21786
DO - 10.1002/net.21786
M3 - Article
AN - SCOPUS:85046441372
SN - 0028-3045
VL - 71
SP - 432
EP - 450
JO - Networks
JF - Networks
IS - 4
ER -