Integer programming models for detecting graph bipartitions with structural requirements
Integer programming models for detecting graph bipartitions with structural requirements
复制标题
DOI：
10.1002/net.21786
复制
发表时间：
2018-06
期刊：
影响因子：
2.1
通讯作者：
Chrysafis Vogiatzis;J. Walteros
中科院分区：
文献类型：
--
作者：
Chrysafis Vogiatzis;J. Walteros
图的二分问题包括将图划分为两个不相交的子图，使得每个节点与同一子图中的其他节点高度相似，但也不同于另一个子图的成员，根据某种同质性标准。在过去的几年里，这个问题受到了极大的关注，因为它在数据分类，图像分割和社交网络分析等不同领域的适用性。在这篇文章中，我们研究了一个变化的图bipartitioning问题，其中，除了考虑同质标准生成的分区，我们还确保其中一个子图满足一组预定义的结构属性，也就是说，这样的子图是需要诱导一个给定的主题。我们把注意力集中在施加结构约束，迫使其中一个子图诱导恒星，集团和集团松弛（准集团），并讨论了一些特定的应用程序，这种特殊情况下。我们通过将其建模为一般分式规划优化问题来解决这个问题，并研究了几种解决方法。此外，我们讨论了额外的算法增强，以解决上述一些情况下，并提供两个贪婪算法的特定情况下，诱导集团和明星，显示诱导明星的近似比。最后，我们通过解决一组具有各种配置的真实的随机生成的实例来测试我们的方法的质量，分析所提出的模型的好处，以及可能的进一步扩展。© 2017 Wiley Periodicals，Inc.网络，第71卷（4），432-450 2018
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. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 432–450 2018